Verfasst am: 14.06.2023, 13:16
Titel: Punkt in Dreieck? (131Mio. Punkte und 17Tsd. Dreiecke Prüfe
Hallo liebe GoMatlab-Community,
(Kurzform:
Ich suche eine "schnelle"/rechengünstige Lösung für die Frage:
Ist Punkt(m,1:3)=(x, y, z) in Dreieck(:,:,n)=(x y z;x y z;x y z) vorhanden?, mit m=1-131000000 & n=1-17500)
bisher war ich stiller Mitleser und ich konnte auf die Lösung bestehender Probleme zurückgreifen, wofür ich sehr dankbar bin. Das scheint jetzt anders zu sein, jedenfalls konnte ich nichts finden, dass mir bei meiner Lösung half.
Worum geht es?
Ich habe Simulationsergebnisse in Form einer Matrix (Partikelkoordinaten, Partikelmassen, usw.) und die jeweiligen Eckpunkte meiner Wanddreiecke (x, y, z - Paare; diese umschreiben meine simulierte Geometrie).
Meine bisherige Idee sieht vor, dass ich Prüfe, ob die Kontaktpunkte jeweils in einem der Dreiecke liegen; wenn ja: z.B. Aufsummieren der Massen, sodass ich im Anschluss die Gesamtmasse der aufgetroffenen Partikel für jedes Dreieck habe.
Nun ist meine Ergebnissmatrix allerdings (131e+6) x 7 und die Wandmatrix 3 x 3 x (17.5e+3) groß.
Ansätze:
1. Punkt in Dreieck?
Aufprallpunkt P=(x,y,z); Eckpunkte des Dreiecks A, B, C (x,y,z)
0A + AB*r + AC*s = 0P
für 0<r<1 ; 0<s<1 und 0<r+s<1 liegt der Punkt im Dreieck.
1. Idee: x = A\b (hiermit komme ich nicht an r und s einzeln, muss aber beides prüfen)
2. Idee: solve (hier müsste ich zwei Schleifen ablaufen, was viel zu lange dauern würde)
Damit kommt beides nicht in Frage.
2. IsInterior/inShape/tsearchn?
Da ich eigentlich alle Informationen habe, sollte eine Funktion der einfachste und vor allem schnellste Weg sein.
Mit inpolygon komme ich nciht weit, da ich mich im 3D-Raum befinde.
Bei allen anderen Funktionen wird vorher eine Triangulation benötigt oder ist in der FUnktion enthalten (ich weiß ja schon, welche Dreiecke zusammengehören und will das nicht neu eingeteilt kriegen).
Habt ihr vielleicht eine Idee/einen Funktionsvorschlag, den ich übersehen habe? Ich bin langsam wirklich verzweifelt und für jeden Input sehr dankbar
Vielen Dank im Vorraus!
ich würde es mit A\b versuchen. Du kannst ja aus dem Ergebnis r und s extrahieren und damit weiterarbeiten.
Poste bitte mal Beispieldaten (131 Punkte statt 131 Mio. Punkte reichen, ebenso 17 Dreiecke statt 17500) und wie du die \ - Idee damit soweit umsetzen würdest. Dann können wir ggf. weitersehen.
Bitte dann auch sagen, wieviel verfügbaren Arbeitsspeicher du hast:
memory
Grüße,
Harald
_________________
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
dank deines Denkanstoßes zu x=A\b habe ich das Problem jetzt wohl gelöst gekriegt, trotzdem läuft der ganze Spaß noch ziemlich lang. Ich bin mir darüber im Klaren, dass es sehr große Datensätze sind, aber vielleicht hat noch jemand einen wertvollen Optimierungs-Tipp?
Code:
clearall load raw_data
A=zeros(3,2);
for k=1:size(T_tri,3) % OP = OA + r * AB + s * AC % AB*r + AC*s = OP-OA
OA=T_tri(1,:,k)';
OB=T_tri(2,:,k)';
OC=T_tri(3,:,k)';
AB=OB-OA;
AC=OC-OA;
%A * x = b
b=Pt-OA;
A(:,1)=AB;
A(:,2)=AC;
x=A\b;
[rows,cols,vals]=find(x(1,:) >= 0 & x(1,:) <= 1 & x(2,:) >= 0 & x(2,:) <= 1 & x(1,:)+x(2,:) >= 0 & x(1,:)+x(2,:) <= 1);
distribution(k,1)=sum(resu(cols,4));
distribution(k,2)=size(cols,2);
disp(['Triangle ',num2str(k), ' of ',num2str(size(T_tri,3)), 'is analysed.']) end
Es werden nicht alle Dreiecke mit Punkten beschrieben, aber das Prinzip sollte klar werden (denke ich).
Vielen Dank schon mal!!
Liebe Grüße
C.
Lokal:
Maximum possible array: 36315 MB (3.808e+10 bytes) *
Memory available for all arrays: 36315 MB (3.808e+10 bytes) *
Memory used by MATLAB: 6617 MB (6.938e+09 bytes)
Physical Memory (RAM): 16338 MB (1.713e+10 bytes)
Server:
Maximum possible array: 251603 MB (2.638e+11 bytes) *
Memory available for all arrays: 251603 MB (2.638e+11 bytes) *
Memory used by MATLAB: 1683 MB (1.764e+09 bytes)
Physical Memory (RAM): 262005 MB (2.747e+11 bytes)
raw_data.mat
Beschreibung:
Rohdaten: Eckpunkte der Wanddreiecke = T_tri Koordinaten der Partikel-Wand-Kontakte = Pt Ergebnisvektor der Simulation = resu
Kannst du mal den Profiler über den Code laufen lassen (mit größeren Daten) und Bescheid geben, welche Zeilen die Bottlenecks sind? Ich würde vermuten, dass es dann x = A\b ist, aber besser sicher sein als vermuten.
Falls du Parallel Computing Toolbox hast, kannst du die for-Schleife parallelisieren. (for durch parfor ersetzen). Damit das dann läuft, musst du den Code etwas anpassen:
Code:
parfor k=1:size(T_tri,3) % OP = OA + r * AB + s * AC % AB*r + AC*s = OP-OA
OA=T_tri(1,:,k)';
OB=T_tri(2,:,k)';
OC=T_tri(3,:,k)';
AB=OB-OA;
AC=OC-OA;
%A * x = b
b=Pt-OA;
A = [AB, AC]; % <-- zwei Zeilen zusammengefasst
x=A\b;
[rows,cols,vals]=find(x(1,:) >= 0 & x(1,:) <= 1 & x(2,:) >= 0 & x(2,:) <= 1 & x(1,:)+x(2,:) >= 0 & x(1,:)+x(2,:) <= 1);
distribution(k,:)=[sum(resu(cols,4)), size(cols,2)]; % <-- zwei Zeilen zusammengefasst disp(['Triangle ',num2str(k), ' of ',num2str(size(T_tri,3)), 'is analysed.']) end
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS