Schnittpunkte von Ebenen schnell finden
-
Hi.
Ich habe n Ebenen, die irgendwo im 3D Raum liegen und durch ihre Normalen, sowie ihrem Abstand zum Nullpunkt gekennzeichnet sind. Ich suche jetzt die Schnittpunkte von je 3 dieser Ebenen, bin allerdings nur an den Schnittpunkten interessiert, die in einem vorher bekannten Raumbereich liegen.
Die Schnittpunkte zu berechnen ist kein Problem. Man stellt jeweils fuer die 3 Ebenen die Ebenengleichungen auf und loest das resultierende Gleichungssystem. Wenn ich das aber fuer jede Untermenge mit jeweils 3 Ebenen mache, dann skaliert der Algorithmus zum Berechnen aller gesuchten Schnittpunkte mit n^3.
Ich frage mich, ob man da einen schnelleren Algorithmus designen kann, wenn man den Raumbereich, in dem die Schnittpunkte liegen duerfen vorher kennt. Nehmen wir als Raumbereich mal die Einheitssphaere rund um den Ursprung. Dann kann ich schon mal jede Ebene aus der Betrachtung herausnehmen, deren Abstand vom Ursprung groesser als 1 ist. In meinem Fall reduziert das die Anzahl der Ebenen leider gar nicht. Ich hoffe aber irgendwie, dass man unter der Einschraenkung des Raumbereichs (auf die Einheitssphaere) nach der Wahl von zwei Ebenen fuer die dritte Ebene die Moeglichkeiten fuer die Normale und Distanz zum Ursprung einschraenken kann. Die Idee ist dann, die Ebenen im Vorfeld in eine Datenstruktur einzuordnen, in der man in O(1) oder O(log(n)) oder so an die Ebenen herankommt, fuer die die Einschraenkung gilt.
Hat da jemand eine Idee?
Danke schon mal fuer jeden konstruktiven Beitrag!
-
Vermutlich ist es sinnvoll, die Schnittgerade der ersten beiden Ebenen zu berechnen. Das ist ja kein Problem und gibt einem einige weitere Anhaltspunkte. Man kann dann auch wieder Ebenen(-Paare) wegschmeißen, nämlich dann, wenn die Schnittgerade zu weit entfernt vom Ursprung liegt.