Überprüfen Sie, ob eine 2D-Ebene einen Hypercube schneidet

Sep 25 2020

Ich möchte schnell überprüfen, ob eine 2D-Ebene a schneidet $N$-dimensionaler Hyperwürfel. In meinem Fall ist der Hypercube$[0,1]^N$und die Ebene wird durch einen Versatzpunkt beschrieben $\mathbf r$ und zwei Vektoren $\mathbf u$ und $\mathbf v$.

$$\mathbf r = \mathbf r_0 + s \mathbf u + t \mathbf v$$

Ich bin nicht daran interessiert, den Schnittpunkt zu konstruieren oder seine Eigenschaften zu identifizieren, sondern nur festzustellen, ob er existiert.

Ich habe in diesen verwandten Fragen keine Antwort gefunden:

Diese Frage betrifft den Schnittpunkt eines zufälligen Unterraums, der auf dem Ursprung zentriert ist, mit einem Hyperwürfel. Meine Anwendung umfasst eine bestimmte Ebene, die den Ursprung möglicherweise nicht schneidet.
Diese Fragen 1 , 2 betreffen die Eigenschaften der Kreuzung, berühren jedoch nicht schnelle Methoden zum Testen, ob die Kreuzung nicht leer ist.
Diese Frage betrifft die Überprüfung, ob eine Linie einen Hyperwürfel schneidet, aber ich war mir nicht ganz sicher, wie ich sie verallgemeinern sollte, um zu überprüfen, ob eine Ebene einen Hyperwürfel schneidet.

Bearbeiten:

Ich habe ein ausführlicheres Beispiel entfernt, in dem eine mögliche Antwort besprochen wurde, die inzwischen gelöscht wurde.

Die aktuelle Antwort schlägt zu Recht die Verwendung der linearen Programmierung vor. Ich hatte jedoch gehofft, dass es eine direktere Lösung auf der Grundlage der Geometrie des Problems gibt, was diesem Ansatz vage ähnelt, um zu testen, ob ein Punkt innerhalb eines Dreiecks liegt.

Antworten

2 EricTowers Sep 25 2020 at 03:47

Dies kann als lineares Programmierproblem formuliert werden . Teilen Sie das Problem nach Koordinaten auf.

\begin{align*} 0 &\leq (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{1} \leq 1 \\ 0 &\leq (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{2} \leq 1 \\ & \phantom{(r_0+s u+)}\vdots \\ 0 &\leq (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{N} \leq 1 \\ \end{align*}

Lassen $\mathbf{x} = (s,t)^{\text{T}} \in \Bbb{R}^2$. Sie möchten nur wissen, ob es einen realisierbaren Punkt gibt, der diese Ungleichheiten befriedigt. Sie versuchen nicht, etwas zu maximieren oder zu minimieren. Wählen Sie also Ihre Lieblings- oder zufällige Zielfunktion "zum Maximieren". Dann konvertiere jede Ungleichung, z$i=1\dots N$oben in das Paar von Machbarkeitsbeschränkungen \begin{align*} 0 &\leq (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{i} \\ -(\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{i} &\leq 0 \\ -\mathbf{r}_0^i - s \mathbf{u}^i - t \mathbf{v}^{i} &\leq 0 \\ - s \mathbf{u}^i - t \mathbf{v}^{i} &\leq \mathbf{r}_0^i \end{align*} und \begin{align*} (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{i} &\leq 1 \\ \mathbf{r}_0^i + s \mathbf{u}^i + t \mathbf{v}^{i} &\leq 1 \\ s \mathbf{u}^i + t \mathbf{v}^{i} &\leq 1 -\mathbf{r}_0^i \text{.} \end{align*} Also die Koeffizientenmatrix, $A$, hat $2N$Zeilen in den Paaren \ begin {pmatrix} & \ vdots \\ - \ mathbf {u} ^ i & & - \ mathbf {v} ^ i \\ \ mathbf {u} ^ i & & \ mathbf {v} ^ i \\ & \ vdots \ end {pmatrix} und die entsprechenden Zeilen von$\mathbf{b}$sind \ begin {pmatrix} \ vdots \\ \ mathbf {r} _0 ^ i \\ 1 - \ mathbf {r} _0 ^ i \\ \ vdots \ end {pmatrix} Dies macht die Einschränkungsgleichung$A \mathbf{x} \leq \mathbf{b}$.

Die lineare Programmierung macht die zusätzlichen Einschränkungen $\mathbf{x} \geq 0$Dies entspricht dem Auffinden eines Schnittpunkts in einem Quadranten der angegebenen Ebene. Da wir alle vier Quadranten überprüfen möchten (aber frei sind, anzuhalten, sobald wir einen Punkt gefunden haben), führen wir einen LP-Solver bis zu vier Mal aus. Die erste, wie oben beschrieben. Der zweite mit$\mathbf{u}$ Ersetzt mit $-\mathbf{u}$;; Dies dient zum Implementieren des Austauschs$s \mapsto -s$ nach Lösungen suchen mit $s \leq 0$Koordinate. Dann mit$\mathbf{v}$ Ersetzt mit $-\mathbf{v}$, um nach Lösungen zu suchen mit $t \leq 0$. Dann ein viertes Mal mit beiden$\mathbf{u}$ und $\mathbf{v}$ durch ihre Negative ersetzt, um den verbleibenden Quadranten zu durchsuchen.

Wenn ein Lauf einen möglichen Punkt findet, gibt es eine Kreuzung. Sobald ein Lauf einen realisierbaren Punkt findet, benötigen Sie keine weiteren Läufe. Wenn alle vier Läufe keine realisierbaren Punkte finden, gibt es keine Kreuzung.

Es stellt sich heraus, dass das Finden eines realisierbaren Punktes ungefähr so schwierig ist (äquivalente Rechenkomplexität) wie das Lösen der LP-Instanz. Bei einigen LP-Solvern können Sie zwischen verschiedenen Phasen ihrer Berechnung anhalten. Wenn Sie einen Solver verwenden, mit dem Sie anhalten können, sobald ein möglicher Punkt gefunden wurde (ein beliebiger Punkt im Schnittpunkt von Würfel und (Quadrant der) Ebene), können Sie Laufzeit sparen.

(Ich habe ein wenig versucht, das zu nutzen $x \leq 0$Einschränkungen müssen die Hälfte der Einschränkungen für den Cube sein, sodass wir nicht bis zu vier LP-Läufe benötigen würden. Das hätte$\mathbf{x} \in \Bbb{R}^N$. Das Hindernis ist, dass es für mich keine lineare Ungleichung zu geben scheint, um festzustellen, ob eine bestimmte Wahl von$\mathbf{x}$ ist im Flugzeug.)

2 MRule Sep 27 2020 at 20:27

Die auf Linear Programming (LP) basierende Antwort ist klar und einfach zu implementieren und kann allgemein für eine viel breitere Klasse von Schnittpunktproblemen verwendet werden. In einigen Fällen können wir jedoch ein wenig an Effizienz gewinnen, indem wir die Geometrie dieses Problems direkt ausnutzen, wie unten beschrieben.

Methode 1: Direkter Schnittpunkttest

Dies ist schnell für kleine Dimensionen, z. B. N = 4 oder 5, skaliert jedoch schlecht für große N.

Erwägen Sie, eine Einheit zu projizieren $N$-Würfel zentriert bei $\mathbf p \in \mathbb R^N$ auf eine Ebene, die am Ursprung zentriert und durch die Vektoren definiert ist $\mathbf u, \mathbf v \in \mathbb R^N$. (Das allgemeinere Problem der Überprüfung auf den Schnittpunkt von a$N$-Würfel und eine Ebene können mit der richtigen Wahl der Koordinaten auf diese reduziert werden.)

Die Ebene definiert eine 2D $(s,t)$ Unterraum von $N$-D Raum mit Basis $A = (\mathbf u, \mathbf v)$

$$ \mathbf x = A \begin{bmatrix} s\\t \end{bmatrix} $$

Wir können das Problem auf den Nullraum der Ebene projizieren. $A^\perp$. Dies sendet jeden Punkt in der Ebene auf Null. Das Problem reduziert sich dann auf das Testen, ob die$N{-}2$ Die Projektion des Hyperwürfels enthält den Ursprung.

Projizieren der $N$-Würfel runter zu $N{-}2$ Dimensionen erzeugen ein Polytop, das als Vereinigung aller ausgedrückt werden kann $N{-}2$ Gesichter des Originals $N$-Würfel. Wenn eine dieser Flächen den Ursprung enthält, schneidet der ursprüngliche Hyperwürfel die Ebene.

Wenn Sie beispielsweise einen 4-Würfel nach 2D projizieren, erhalten Sie eine Sammlung von 2D-Rauten, eine für jede 2D-Fläche der 3D-Facetten des 4-Würfels. Wenn eine dieser Rauten den Ursprung enthält, wissen wir, dass die 2D-Ebene in unserem ursprünglichen Problem den 4-Würfel schneidet.

Eine Möglichkeit zu überprüfen, ob a $N{-}2$ Raute enthält den Ursprung ist zu einer Basis zu ändern, wo die Raute ein Würfel ist $[0,1]^{N-2}$und testen Sie, ob dieser Würfel den Ursprung enthält. Wählen Sie dazu einen Scheitelpunkt der Raute und alle Punkte, mit denen sie sofort verbunden ist, als Basissatz aus.

(Wenn Sie alle Unterfacetten überprüfen, können Sie anhalten, sobald Sie eine einzelne Unterfacette gefunden haben, die den Zielpunkt enthält.)

Dies scheint ineffizient zu sein, ist jedoch schneller als die Verwendung von zB Pythons integrierten linearen Programmierlösern für $N{=}4$. Es skaliert jedoch schlecht auf höhere Dimensionen. Es könnte eine elegantere Lösung geben, wenn man Symmetrien ausnutzen und redundante Berechnungen eliminieren könnte.

Methode 2: $\mathcal O[ N \log(N) ]$ über Preparata und Mullers Algorithmus (oder so ähnlich)

Transformieren Sie zunächst das Problem in eine Reihe von $2N$lineare Ungleichheitsbeschränkungen. Jede Einschränkung definiert eine Halbebene. Die Ebene schneidet den Hyperwürfel, wenn der Schnittpunkt dieser Halbebenen nicht leer ist.

Bisher ist dies identisch mit dem linearen Programmieransatz. Es stellt sich jedoch heraus, dass es spezielle Algorithmen gibt, um zu testen, ob der Schnittpunkt von$n=2N$Halbebenen sind nicht leer. Hier ist zum Beispiel ein Ansatz von Preparata und Muller zur Lösung des Schnittpunkts von$n$ Halbräume mit $n\log(n)$zeitliche Komplexität. Es gibt andere Varianten (z. B. Wu, Ji und Chen ), aber alle haben die gleiche Komplexität.

Diese Vorlesungsunterlagen von Dave Mount sind besonders nützlich, um die diesen Algorithmen zugrunde liegende Geometrie zu verstehen. Diese Hinweise zeigen, wie der (konvexe) Schnittpunkt als Schnittpunkt einer (konvexen) oberen und unteren Hüllkurve erstellt wird.