Comment tester si une ligne coupe un polygone convexe?

Question

Supposons qu'on vous donne l'équation d'une ligne (en 2d), et les équations des lignes qui forment un polygone convexe (le polygone pourrait être illimité). Comment déterminer si la ligne coupe le polygone?

De plus, y at-il des bibliothèques de la géométrie algorithmique où ces tâches sont prédéfinies? Je demande parce que je suis intéressé pas seulement dans la version 2D mais la géométrie n-dimensionnelle.

Answer 1

En géométrie, généralement see wikipedia, un polygone est délimité. Ce que vous décrivez est généralement appelé un polytope ou un polyèdre see wikipedia

Il existe quelques bibliothèques de géométrie disponibles, dont deux qui viennent à l'esprit sont boost (polygone) et CGAL. Généralement, il existe une séparation distincte entre les méthodes de calcul qui traitent de 2d, 3d et Nd - pour des raisons évidentes.

Pour votre problème, j'utiliserais une approche un peu binaire de partitionnement de l'espace. Je voudrais prendre la première ligne de votre "poly" et couper la ligne de requête contre elle, créant un rayon. Le rayon commencerait à l'intersection des deux lignes, et continuerait en direction de l'intérieur du demi-espace généré par la première ligne du "poly". Maintenant je répète la procédure avec le rayon et la deuxième ligne du "poly". (Cela pourrait générer un segment au lieu de rayon) Si à un certain point l'origine du rayon (ou segment) se trouve sur le côté extérieur d'une ligne poly actuellement considéré et ne l'intersecte pas, alors la réponse est non - la ligne ne se croise pas votre "poly". Sinon, il se croise. Faites particulièrement attention avec divers boîtiers de bord parallèles. Assez simple et fonctionne pour des cas multidimensionnels.

Answer 2

Pour le cas 2D, je pense que le problème se simplifie un peu.

La ligne partitionne l'espace en deux zones.

Si le polygone est présent dans une seule de ces régions, la ligne ne l'intersecte pas.

Si le polygone est présent dans les deux régions, la ligne l'intersecte.

Alors:

Prenez une perpendiculaire à la ligne, ce qui rend l'intersection avec la ligne l'origine.

Projetez chaque sommet du polytope sur la perpendiculaire.

Si ces projections se produisent avec les deux signes, le polygone coupe la ligne.

[Mise à jour à la suite de commentaires de elexhobby.]

oublié d'inclure le traitement de l'affaire sans bornes.

Je voulais ajouter que l'on pourrait créer un "sommet virtuel" pour représenter la zone ouverte. Ce dont nous avons vraiment besoin, c'est la "direction" de l'aire ouverte. Nous pouvons considérer cela comme la moyenne des vecteurs pour les limites de la zone ouverte.

Nous traitons ensuite le produit scalaire de cette direction avec la normale et l'ajoutons à l'ensemble des projections de sommets.

Answer 3

Je ne suis pas tout à fait sûr, mais je suppose que vous pouvez résoudre ce problème en utilisant la dualité. Commencez par normaliser les équations de ligne a.x+b.y=1 et considérez l'ensemble des points (a,b).

Ceux-ci doivent former un polygone convexe, et je suppose que la nouvelle ligne peut ne pas correspondre à un point à l'intérieur du polygone. Ceci est facilement vérifié en vérifiant que le nouveau point est du même côté de tous les bords. (Si vous ne connaissez pas l'ordre des lignes, construisez d'abord la coque convexe.)

Answer 4

Commençons par les polygones finis.

Pour croiser un polygone, une ligne doit croiser l'un de ses côtés. L'intersection entre la ligne et un bord n'est possible que si deux points se trouvent sur des côtés différents de la ligne.

Cela peut être facilement vérifié avec sign(cross_product(Ep-Lp,Ld)) pour deux points du bord. Ep - pointe, Lp - un point sur la ligne, Ld - vecteur de direction de la ligne, cross_product(A,B)=Ax*By-Ay*Bx.

Pour traiter des polygones infinis, nous pouvons introduire des "points infinis". Si nous avons un demi-bord infini avec le point E1 et la direction Ed, son "deuxième point" est quelque chose comme E1+infinity*Ed, où infinity est "assez grand nombre".

Pour « infinis points » le chèque sera légèrement différent: cross_product(Ep-Lp,Ld)= =cross_product(E1+infinity*Ed-Lp,Ld)= =cross_product(E1-Lp+infinity*Ed,Ld)= =cross_product(E1-Lp,Ld)+cross_product(infinity*Ed,Ld)= =cross_product(E1-Lp,Ld)+infinity*cross_product(Ed,Ld)

Si cross_product(Ed,Ld) est égal à zéro (la ligne est parallèle au bord), le signe sera déterminé par le premier composant. Sinon, le second composant dominera et déterminera le signe.