Wie überprüfe ich, ob ein Simplex den Ursprung enthält?

Question

Ich implementiere den Gilbert-Johnson-Keerthi Algorithmus, der berechnet, ob zwei Objekte sich schneiden (dh kollidieren).

Der Einstiegspunkt zu meinem Code ist die hasCollided Funktion, die zwei Listen von Punkten nimmt und True zurückgibt, wenn sie sich schneiden. Ich glaube, ich habe das Papier korrekt umgesetzt - allerdings muss ich noch die contains Funktion implementieren.

Die contains Funktion sollte bestimmen, ob ein Simplex den Ursprung enthält. Ich bin unsicher, wie ich das umsetzen soll.

Wie kann ich effizient feststellen, ob ein Simplex (Punktsammlung) den Ursprung enthält?

---

Das folgende ist meine Implementierung:

type Simplex = Set (Vector Double) 

hasCollided :: [Vector Double] -> [Vector Double] -> Bool 
hasCollided points1 points2 = gjk points1 points2 simplex (scale (-1) direction) p 
    where simplex = insert p empty 
     p   = support points1 points2 direction 
     direction = fromList [1, 0, 0] 

gjk :: [Vector Double] -> [Vector Double] -> Simplex -> Vector Double -> Vector Double -> Bool 
gjk points1 points2 simplex direction lastAdded = 
    if p <.> direction < 0 then False 
    else 
    if contains simplex' (fromList [0, 0, 0]) direction p then True 
    else gjk points1 points2 simplex' direction' p 
    where p   = support points1 points2 direction 
     simplex' = insert p simplex 
     direction' = cross ab $ cross ao ab 
     ab   = sub p lastAdded 
     ao   = sub origin3D lastAdded 

Die Helferfunktionen sind:

contains :: Simplex -> Vector Double -> Vector Double -> Vector Double -> Bool 
contains simplex point direction lastAdded = undefined 


support :: [Vector Double] -> [Vector Double] -> Vector Double -> Vector Double 
support points1 points2 direction = sub p1 p2 
    where p1 = getFarthestPoint points1 direction 
     p2 = getFarthestPoint points2 direction 

getFarthestPoint :: [Vector Double] -> Vector Double -> Vector Double 
getFarthestPoint points direction = points !! index 
    where index  = fromJust $ elemIndex (maximum dotproducts) dotproducts 
     dotproducts = map (direction <.>) points 

origin3D :: Vector Double 
origin3D = fromList [0, 0, 0] 

Answer 1

Um genau zu bestimmen, ob der Punkt in den Simplex liegt oder nicht, müssen Sie nur ein Zeichen von maximal d + 2 Determinanten von d * d Größe wissen.

Let:

dann können wir eine Matrizen-Konstrukt (j,k Index bedeutet: ausschließen j Reihen- und subtrahieren Vektor vom Ursprung k von jedem d verbleibenden Reihen zu verweisen, die alle auf der linken Seite in Reihen definiert eine Facette gegen j Scheitel liegende):

Determinante der obigen Matrix ist d! mal d -dimensional orientiertes Hypervolumen eines Simplex, konstruiert aus Punkten, die in der Formel enthalten sind (strikt gesagt ist das ausgerichtete Hypervolumen eines Parallelotops, dessen Kanten durch die Matrixzeilen gegeben sind).

Wenn Punkt innerhalb des Simplex liegt, dann werden alle folgenden Gleichungen wahr ist (die Ausrichtung (Vorzeichen von orientierten Hypervolumen) von j und 0 Paar von Punkten relativ zu einer Facette passend):

aber wir können beachten Sie, dass

So können wir nur eine Determinante von der linken Seite des Vergleichs berechnen (?):

und gehen davon aus, dass Zeichen Flips für die nächste j s.

Daher sollten wir mindestens 2 Determinanten von Matrizen d*d und maximale d + 2 (von A ^1,1 und einem ^{j, 0 für alle}j in {1, 2, ... zu berechnen, d + 1}). Wenn das Zeichen in einem Schritt nicht übereinstimmt, liegt der Punkt außerhalb einer aktuellen Facette des Simplex und damit überhaupt außerhalb des Simplex.

ZUSATZ:

Wenn einige der rechten Seite Determinanten Null sind, dann ist der Punkt, zu den Ebenen der entsprechenden Facetten koplanar.

Answer 2

Ich werde das nicht klug nehmen „, lassen Sie uns einige der linearen Algebra tun, es zu lösen " Ansatz.

Jeder Punkt innerhalb eines Simplex ist ein convex combination der Punkte, die den Simplex definieren. Eine konvexe Kombination ist nur eine lineare Kombination, wobei die Koeffizienten alle> = 0 sind und sich zu 1 addieren.

"Enthält ein Simplex den Ursprung?" Ist identisch mit der Frage, ob es eine konvexe Kombination der Simplex-Punkte gibt gleich dem Nullvektor. Können wir das als Matrixausdruck schreiben?

Nehmen wir an, wir arbeiten mit einem Simplex, definiert durch vier Vektoren, x1 bis x4.

Wir werden eine beliebige lineare Kombination dieser Vektoren bilden, y = a1*x1 + a2*x2 + a3*x3 + a4*x4.

Wir möchten a1 bis a4 so finden, dass y der Nullvektor und a1 + a2 + a3 + a4 = 1 ist.

Ich werde zeigen, wie das lineare System aussehen würde, wenn der Simplex von Punkten in einem dreidimensionalen euklidischen Raum ist; Lassen Sie den Vektor xi haben Komponenten xi1, xi2 und xi3.

[ x11 x21 x31 x41 ] [ a1 ] [ 0 ] 
[ x12 x22 x32 x42 ] [ a2 ] = [ 0 ] 
[ x13 x23 x33 x43 ] [ a3 ] [ 0 ] 
[ 1 1 1 1 ] [ a4 ] [ 1 ] 

Die ersten drei Zeilen dieses linearen System entsprechen die Beschränkung, daß y Null sein muss, das heißt, dass wir auf den Ursprung durch irgendeine lineare Kombination von x1 durch x4 zu erhalten. Die letzte Zeile entspricht der Beschränkung, dass die Koeffizienten sich zu 1 addieren, was notwendig, aber nicht ausreichend ist, damit die lineare Kombination eine konvexe Kombination ist. Die Einschränkung, die nicht durch die Matrixgleichung ausgedrückt wird, ist ai >= 0.

Wählen Sie Ihre bevorzugte Methode, um ein lineares System zu lösen und anzuwenden. Wenn die Vektoren, aus denen Ihr Simplex besteht, linear unabhängig sind, werden Sie keine Lösungen finden. Wenn das lineare System eine Lösung oder Lösungen hat und mindestens eine Lösung hat alle ai >= 0, dann enthält der Simplex den Ursprung.

Ich habe keine fertige Beschreibung für einen Algorithmus für diesen letzten Schritt, um festzustellen, ob der Lösungssatz Punkte enthält, an denen alle Koeffizienten positiv sind. Ich schlage vor, ein paar Beispiele auf Papier zu bringen - ich nehme an, Sie können einen finden.

BEARBEITEN: Bestimmen, ob der Lösungssatz Punkte enthält, an denen alle Koeffizienten positiv sind, ist tatsächlich gleichbedeutend mit der Bestimmung, ob der durch den Schnittpunkt des Lösungsraums mit ai >= 0 definierte Simplex andere Punkte als den Ursprung enthält.

dass diese Methode der Lösung bedeutet, reduziert das Problem der

"Does die Eingangs Simplexenthalten den Ursprung?"

zu

"Does anderen simplex (aus dem Eingang simplex abgeleitet) enthalten keine anderen Punkte als der Ursprung?"

Ich denke, es ist ein nettes Beispiel für die Reduzierung eines Problems auf ein anderes (hoffentlich einfacher) Problem.