Vérifier si un plan 2D intersecte un hypercube

Question

Je voudrais vérifier rapidement si un plan 2D coupe un $N$-hypercube dimensionnel. Dans mon cas, l'hypercube est$[0,1]^N$, et le plan est décrit par un point de décalage $\mathbf r$ et deux vecteurs $\mathbf u$ et $\mathbf v$.

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

Je ne suis pas intéressé à construire l'intersection ou à identifier l'une de ses propriétés, mais uniquement à déterminer si elle existe.

Je n'ai pas trouvé de réponse à ces questions connexes:

• Cette question concerne l'intersection d'un sous-espace aléatoire centré sur l'origine avec un hypercube. Mon application implique un plan spécifié qui ne peut pas croiser l'origine.
• Ces questions 1 , 2 concernent les propriétés de l'intersection, mais n'abordent pas les méthodes rapides pour tester si l'intersection est non vide.
• Cette question concerne la vérification si une ligne coupe un hypercube, mais je ne savais pas trop comment la généraliser pour vérifier si un plan croise un hypercube.

Éditer:

J'ai supprimé un exemple plus détaillé discutant d'une réponse possible qui a depuis été supprimée.

La réponse actuelle suggère à juste titre d'utiliser la programmation linéaire. Cependant, j'espérais qu'il y avait une solution plus directe basée sur la géométrie du problème, quelque chose qui s'apparente vaguement à cette approche pour tester si un point se trouve à l'intérieur d'un triangle.

Answer 1

Cela peut être formulé comme un problème de programmation linéaire . Décomposez le problème par coordonnées.

\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*}

Laisser $\mathbf{x} = (s,t)^{\text{T}} \in \Bbb{R}^2$. Vous voulez seulement savoir s'il existe un point réalisable satisfaisant ces inégalités; vous n'essayez pas de maximiser ou de minimiser quoi que ce soit. Alors choisissez votre fonction d'objectif préférée ou aléatoire "pour maximiser". Puis convertissez chaque inégalité, pour$i=1\dots N$, ci-dessus dans la paire de contraintes de faisabilité \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*} et \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*} Donc la matrice des coefficients, $A$, a $2N$lignes dans les paires \ begin {pmatrix} & \ vdots \\ - \ mathbf {u} ^ i & & - \ mathbf {v} ^ i \\ \ mathbf {u} ^ i & & \ mathbf {v} ^ i \\ & \ vdots \ end {pmatrix} et les lignes correspondantes de$\mathbf{b}$are \ begin {pmatrix} \ vdots \\ \ mathbf {r} _0 ^ i \\ 1 - \ mathbf {r} _0 ^ i \\ \ vdots \ end {pmatrix} Cela rend l'équation des contraintes$A \mathbf{x} \leq \mathbf{b}$.

La programmation linéaire rend les contraintes supplémentaires $\mathbf{x} \geq 0$, ce qui correspond à trouver une intersection dans un quadrant du plan donné. Puisque nous voulons vérifier les quatre quadrants (mais que nous sommes libres de nous arrêter une fois que nous trouvons un point du tout), nous exécutons un solveur LP jusqu'à quatre fois. Le premier, comme décrit ci-dessus. Le second, avec$\mathbf{u}$ remplacé par $-\mathbf{u}$; il s'agit de mettre en œuvre le remplacement$s \mapsto -s$ rechercher des solutions avec $s \leq 0$coordonner. Puis avec$\mathbf{v}$ remplacé par $-\mathbf{v}$, pour rechercher des solutions avec $t \leq 0$. Puis une quatrième fois avec les deux$\mathbf{u}$ et $\mathbf{v}$ remplacés par leurs négatifs pour rechercher le quadrant restant.

Si une course trouve un point réalisable, il y a une intersection. Dès qu'une exécution trouve un point réalisable, vous n'avez plus besoin de courses supplémentaires. Si les quatre parcours ne trouvent aucun point réalisable, il n'y a pas d'intersection.

Il s'avère que trouver un point réalisable est à peu près aussi difficile (complexité de calcul équivalente) que la résolution de l'instance LP. Certains solveurs LP vous permettront de vous arrêter entre différentes phases de leur calcul. Si vous utilisez un solveur qui vous permettra de vous arrêter dès qu'il trouve un point réalisable (tout point de l'intersection du cube et du (quadrant du) plan), vous pouvez gagner du temps d'exécution.

(J'ai passé un peu de temps à essayer de tirer parti du $x \leq 0$contraintes à la moitié des contraintes pour le cube, nous n'aurions donc pas besoin de jusqu'à quatre exécutions LP. Cela aurait$\mathbf{x} \in \Bbb{R}^N$. L'obstacle est qu'il ne me semble pas y avoir de manière linéaire de déterminer si un choix particulier de$\mathbf{x}$ est dans l'avion.)

Answer 2

La réponse basée sur la programmation linéaire (LP) est claire et facile à mettre en œuvre, et peut être utilisée généralement pour une classe beaucoup plus large de problèmes d'intersection. Cependant, nous pouvons gagner un peu d'efficacité dans certains cas en exploitant directement la géométrie de ce problème, comme décrit ci-dessous.

Méthode 1: test direct pour l'intersection

Ceci est rapide pour les petites dimensions, par exemple N = 4 ou 5, mais échoue mal pour les grands N.

Envisagez de projeter une unité $N$-cube centré sur $\mathbf p \in \mathbb R^N$ sur un plan centré à l'origine et défini par les vecteurs $\mathbf u, \mathbf v \in \mathbb R^N$. (Le problème plus général de la vérification de l'intersection d'un$N$-cube et un plan peuvent être réduits à cela avec le bon choix de coordonnées.)

Le plan définit un 2D $(s,t)$ sous-espace de $N$-Espace D, avec base $A = (\mathbf u, \mathbf v)$

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

On peut projeter le problème sur l'espace nul du plan, $A^\perp$. Cela envoie chaque point du plan à zéro. Le problème se résume alors à tester si le$N{-}2$ la projection de l'hypercube contient l'origine.

Projeter le $N$-cube jusqu'à $N{-}2$ dimensions crée un polytope qui peut être exprimé comme l'union de tous $N{-}2$ visages de l'original $N$-cube. Si l'une de ces faces contient l'origine, l'hypercube d'origine coupe le plan.

Par exemple, projeter un 4 cubes en 2D donne une collection de losanges 2D, un pour chaque face 2D des facettes 3D du 4 cube. Si l'un de ces losanges contient l'origine, alors nous savons que le plan 2D coupe le 4-cube dans notre problème d'origine.

Une façon de vérifier si un $N{-}2$ losange contient l'origine est de changer pour une base où le losange est un cube $[0,1]^{N-2}$, et testez si ce cube contient l'origine. Pour ce faire, sélectionnez un sommet du losange et tous les points auxquels il se connecte immédiatement comme ensemble de base.

(Lors de la vérification de toutes les sous-facettes, vous pouvez vous arrêter dès que vous avez trouvé une seule sous-facette contenant le point cible)

Cela semble inefficace, mais est plus rapide que d'utiliser, par exemple, les solveurs de programmation linéaire intégrés de Python pour $N{=}4$. Cependant, il s'adapte mal aux dimensions supérieures. Il pourrait y avoir une solution plus élégante si l'on pouvait exploiter les symétries et éliminer les calculs redondants.

Méthode 2: $\mathcal O[ N \log(N) ]$ via l'algorithme de Preparata et Muller (ou quelque chose comme ça)

Tout d'abord, transformez le problème en un ensemble de $2N$contraintes d'inégalité linéaire. Chaque contrainte définit un demi-plan. Le plan coupe l'hypercube si l'intersection de ces demi-plans n'est pas vide.

Jusqu'à présent, cela est identique à l'approche de programmation linéaire. Mais, en fin de compte, il existe des algorithmes spécifiques pour tester si l'intersection de$n=2N$demi-plan est non vide. Par exemple, voici une approche de Preparata et Muller pour résoudre l'intersection de$n$ demi-espaces avec $n\log(n)$complexité temporelle. Il existe d'autres variantes (par exemple Wu, Ji et Chen ), mais elles ont toutes la même complexité.

Ces notes de cours de Dave Mount sont particulièrement utiles pour comprendre la géométrie sous-jacente à ces algorithmes. Ces notes montrent comment construire le jeu d'intersections (convexes) comme l'intersection d'une enveloppe (convexe) supérieure et inférieure.

Le pseudocode de base est:

• Tout d'abord, identifiez les lignes de délimitation verticales. Ces travées délimitées de la$s$axe du plan. Leur intersection$s\in[s_0,s_1]$ définit les limites d'une procédure de recherche (ci-dessous).
• Divisez les lignes restantes en celles qui délimitent le demi-plan par le bas et celles qui délimitent le demi-plan par le haut, où «ci-dessous» et «dessus» sont définis en termes $t$ coordonnée du plan.
• Ces deux ensembles de lignes définissent des régions de faisabilité supérieure et inférieure, qui sont convexes. La limite de ces régions peut être interprétée comme des courbes$t_l(s)$ et $t_u(s)$
• Nous pouvons tester si l'intersection entre les régions de faisabilité supérieure / inférieure est non vide en trouvant le minimum de $t(s) = t_l(s)-t_u(s)$ sur $s\in[s_0,s_1]$
• Si seulement $\exists s\in[s_0,s_1]\text{ s.t. } t(s)<0 $, puis le plan coupe l'hypercube.
• Cela peut être vérifié via une recherche binaire, en recherchant le point où $t(s)$ change de signe, et s'arrête tôt si un point satisfaisant toutes les contraintes est trouvé.