WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Punkt in Dreieck? (131Mio. Punkte und 17Tsd. Dreiecke Prüfe

 

Chry89
Forum-Newbie

Forum-Newbie


Beiträge: 2
Anmeldedatum: 14.06.23
Wohnort: Berlin
Version: R2022a
     Beitrag Verfasst am: 14.06.2023, 14:16     Titel: Punkt in Dreieck? (131Mio. Punkte und 17Tsd. Dreiecke Prüfe
  Antworten mit Zitat      
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!

Viele Grüße
C.
Private Nachricht senden Benutzer-Profile anzeigen


Harald
Forum-Meister

Forum-Meister


Beiträge: 24.453
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 14.06.2023, 17:40     Titel:
  Antworten mit Zitat      
Hallo,

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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Chry89
Themenstarter

Forum-Newbie

Forum-Newbie


Beiträge: 2
Anmeldedatum: 14.06.23
Wohnort: Berlin
Version: R2022a
     Beitrag Verfasst am: 15.06.2023, 10:29     Titel:
  Antworten mit Zitat      
Hallo Harald,

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? Smile


Code:
clear all
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

Download
 Dateiname:  raw_data.mat
 Dateigröße:  10.76 KB
 Heruntergeladen:  98 mal
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.453
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 15.06.2023, 17:32     Titel:
  Antworten mit Zitat      
Hallo,

ich würde distribution vorbelegen:
Code:
distribution = zeros(size(T_tri,3), 2);


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
 


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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

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
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

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.