Ebenen aus Punktwolke
-
Hallo,
ich hab eine Punktwolke(XYZ), bestehend aus ca. 2000000 Punkten. Ich möchte nun aus dieser Punktwolke alle darin enthaltenen Ebenen extrahieren. Wie geh ich das am besten an? Ich bin kein Mathematiker und wollte euch mal fragen welche Methode bzw welcher Algorithmus sich dafür am besten eignet.Ich hab mir eine C Programm geschrieben, welches die Punkte XYZ einliest und in einer Matrix speichert. Des Weiteren kann ich mit diesem Programm für jeden beliebigen Punkt seine Nachbarpunkte bestimmen...
Jetzt fehlt mir jedoch ein weiterer Anstoß um alle Ebenen bzw alle Punkte die eine Ebene bilden, aus dieser Punktwolke zu extrahieren.
Danke
Andi
-
dir ist schonklar, dass 3 Punkte immer eine ebene bilden? Es gibt also sehr sehr viele Möglichkeiten, aus 2 Millionen Punkten Ebenen bilden. Um aus Drei Punkten eine Ebene zu bestimmen, bietet es sich bspw. an, aus den drei Punkten zwei Vektoren zu machen das Kreuzprodukt zu berechnen. dieses ist die Ebenennormale. Dann kannst du mit der Normalenform die ebenegleichung aufstellen:
n * p = n*x
Genauerers dazu gibts auf wikipedia.
Vielleiht möchtest du aber auch nur eine Ebene aus allen Punkten machen, und diese Ebene so bauen, dass sie am besten in die Wolke passt? dann schau dir multilineare regression an, gibts auch was bei wikipedia für
-
Andi123 schrieb:
Hallo,
ich hab eine Punktwolke(XYZ), bestehend aus ca. 2000000 Punkten. Ich möchte nun aus dieser Punktwolke alle darin enthaltenen Ebenen extrahieren. Wie geh ich das am besten an? Ich bin kein Mathematiker und wollte euch mal fragen welche Methode bzw welcher Algorithmus sich dafür am besten eignet.Ich hab mir eine C Programm geschrieben, welches die Punkte XYZ einliest und in einer Matrix speichert. Des Weiteren kann ich mit diesem Programm für jeden beliebigen Punkt seine Nachbarpunkte bestimmen...
Jetzt fehlt mir jedoch ein weiterer Anstoß um alle Ebenen bzw alle Punkte die eine Ebene bilden, aus dieser Punktwolke zu extrahieren.
by the hammer
-
Du musst alle Ebenen einzeln berechnen da gibt es keinen weg dran vorbei einfach immer einen Punkt aendern und berechnen, bis alle moeglichen kombis durch sind.
for (int a=Punkt 1; a<Punkt.letzter; a++)
{
for (int b=Punkt 1; b<Punkt.letzter; b++)
{
for (int c=Punkt 1; c<Punkt.letzter; c++)
{
berechneEbeneAusPunkten (a,b,c); //natuerlich daran denken abzufragen ob alle Punkte unterschiedlich sind
}
}
}
Sso ungefaehr geht das dann. Vereinfachen geht nicht.
-
tarrox schrieb:
Sso ungefaehr geht das dann. Vereinfachen geht nicht.
bei dir würden allein bei drei punkten 3^3=27 ebenen herauskommen: aaa, aab, aac, aba, abb, abc, baa, ...
Das stimmt aber offensichtlich nicht, bei drei punkten darf nur eine Ebene herauskommen. Das Problem hier ist wie das "n personen schütteln sich die hände, so dass jeder jedem die hand geschüttelt hat; wie oft werden Hände geschüttelt?"-problem, bloß diesmal mit drei dimensionen. die Anzahl der möglichen ebenen sind die sog. Tetraederzahlen: http://de.wikipedia.org/wiki/Tetraederzahl
-
Heinzelotto schrieb:
tarrox schrieb:
Sso ungefaehr geht das dann. Vereinfachen geht nicht.
bei dir würden allein bei drei punkten 3^3=27 ebenen herauskommen: aaa, aab, aac, aba, abb, abc, baa, ...
Das stimmt aber offensichtlich nicht, bei drei punkten darf nur eine Ebene herauskommen. Das Problem hier ist wie das "n personen schütteln sich die hände, so dass jeder jedem die hand geschüttelt hat; wie oft werden Hände geschüttelt?"-problem, bloß diesmal mit drei dimensionen. die Anzahl der möglichen ebenen sind die sog. Tetraederzahlen: http://de.wikipedia.org/wiki/TetraederzahlHab extra noch geschrieben das man auf gleiche Punkte ueberpruefen soll (neben der Funktion), daher diese nicht berechenen, ist ja logisch^^.
-
tarrox schrieb:
Hab extra noch geschrieben das man auf gleiche Punkte ueberpruefen soll (neben der Funktion), daher diese nicht berechenen, ist ja logisch^^.
ok, das habe ich übersehen, aber selbst da würden zu viele berechnet werden, da bei dieser methode sowohl abc, acb, bac, bca, cab und cba gültig wären, obwohl das ein und dieselbe ebene ist
-
Heinzelotto schrieb:
ok, das habe ich übersehen, aber selbst da würden zu viele berechnet werden, da bei dieser methode sowohl abc, acb, bac, bca, cab und cba gültig wären, obwohl das ein und dieselbe ebene ist
Mist daran hab ich nicht gedacht... Naja muss man halt noch sicherstellen das der Punkt a vor dem Punkt b ist und der Punkt c nach dem Punkt b. Daher wenn man eine Liste mit Punkten hat der Punkt bei b einen groesseren Index hat als der Punkt a (und b<c). Damit sollte das Problem geloesst sein und man wirklich nur die benoetigten Ebenen erhaelt.
-
ich frage mich, wofür der Threadersteller das braucht, denn selbst mit der neuen methode bräuchte man immernoch 8000000000000000000 schleifendurchläufe, und das ist ziemlich viel
-
Ich vermute eher, dass gewisse Punktmengen näherungsweise Ebenen darstellen. Vermutlich läuft es auf einen Best-Fit-Algo hinaus, in dem zB aus 5000 Punkten eine Ebene erzeugt wird. Insgesamt reduziert sich dann die Anzahl möglicher Ebenen auf ein überschaubares Mass.Er will sicherlich nicht alle theoretisch erzeugbaren Ebenen finden, das ist irgendwie sinnlos. Da der Threadsteller sich aber offenbar zurückgezogen hat und die Antworten nicht liest, bzw. keine weiteren Infos ausspuckt, macht es eh keinen Sinn, hier weiter zu diskutieren.
-
Wenn es dem Ersteller darum geht, eine Ebene zu finden, die möglichst gut in die Punktmenge "reinpasst", dann sei er auf die kleinse Abstandsquadrat-Methode verwiesen ...