# Prüfen ob sich ein Punkt innerhalb einer Kugel befindet (Java3D,nicht-lineare GLS)



## cytom2k (1. Nov 2011)

Schönen Abend.

Hintergrund: Ich versuche momentan ein 3D Voronoi Diagramm von Atomstrukturen zu erstellen. Dazu braucht es zunächst eine Delaunay Triangulation , bei der es gerade hackt.

Problem: Es exisieren nun jeweils 4 Point3D - Punkte , die ein Tetraeder bilden. Im nächsten Iterationsschritt muss die Lagebeziehung zwischen einem Punkt und der Kugel , die durch die 4 Punkte des Tertraeders bestimmt wird , ermittelt werden. 
Das Prüfen ob der Punkt in der Umkugel steckt ist ja trivial , allerdings brauche ich den Mittelpunkt sowie den Radius eben der Kugel um die bestimmen zu können. 

Mathematisch lässt sich der Mittelpunkt und der radius durch ein nicht lineares Gleichungssystem bestimmen , indem man die 4 Punkte in eine Kugelgleichung einsetzt:

( xpi - xm )^2 + (ypi - ym )^2 + (zpi - zm )^2 = rm^2 
pi : Koordinate des Punktes i ( 1-4 )
m: Koordinate der Kugel 

Leider finde ich  keine Bibliothek , die mir das vorliegende nicht lineare GLS lösen könnte.


----------



## Marco13 (1. Nov 2011)

Hui, nur ein spontaner Gedanke: Wenn man den Radius der Kugel hat (wie hier) und weiß, dass der gesuchte Punkt von allen Punkten gleich weit weg ist, sollte sich doch was machen lassen...? (Vielleicht bin auch nur mal wieder zu naiv...  )


----------



## Andi_CH (2. Nov 2011)

Naive Ansätze sind nicht immer schlecht ;-)

Distanz von Punkt zum Zentrum < Kugelradius = innerhalb


----------



## Marco13 (2. Nov 2011)

Ich glaube, das eigentliche Problem ist weniger der Radius (siehe Wikipedia) sondern _der Mittelpunkt an sich_  Aber... irgendwie kann ich mir nicht vorstellen, dass man dafür unbedint ein nichtlineares Gleichungssystem lösen muss (kann mich aber auch täuschen...)


----------



## Andi_CH (2. Nov 2011)

Na ja, ich weiss nicht ob meine Mathekenntnisse ausreichen um den Wikipediaartikel zu verstehen. (Was im Moment sicher nicht ausreicht, ist die Zeit)

Naiv wie ich bin gehe ich davon aus, dass eine Kugel durch deren Mittelpunkt und Radius definiert ist.

Hm - es sind 4 Unbekannte (3 Zentrumskoordinaten und den Radius) also brauche ich 4 Gleichungen.
4 unterschiedliche Punkte auf der Kugeloberfläche reichen aus um das zu bestimmen.
IMO ist das Gleichungssystem quadratisch, aber auch das ist lösbar.

Ansatz2:

Wenn ich ausgehend vom Punkt P drei Distanzen zu einem Kreis berechne, kann ich aus dem Verhältnis der Längen zueinander und den Winkeln dazwischen schliessen ob ich innerhalb des Kreises liege oder nicht.
Das müsste IMO mit einer Kugel und einer Distanz mehr auch gehen.


----------



## cytom2k (8. Nov 2011)

Zugegeben Java ist was das Angebot an Mathematik Hilfsmitteln angeht eher schlecht. Die Mathematik Bibliotheken die ein nicht-lineares GLS lösen könnten scheinen allerdings kompliziert zu sein.

Bei meinem Problem bin ich auf ein interressantes Paper gestossen , sodass sich der Test ob sich ein Punkt in einer durch 4 Punkte definierten Kugel befindet auf die Lösung einer Determinante einer qudratischen Matrix reduziert. Das werde ich mal mit der Mathe Bib JAMA versuchen.


----------

