Si j'ai un vecteur (une ligne composée de 2 points) sur un plan 2D Comment puis-je déterminer s'il est passé à travers un polygone?
Je sais que je peux prendre chaque ligne qui compose le polygone et voir si tout intersect, mais y a-t-il une meilleure façon?
J'ai lu cette post Comment puis-je déterminer si un point 2D est à l'intérieur Un polygone? qui me donne des idées pour voir si le point est dans un polygone, mais j'ai besoin de voir si elle est passée / intersectée.
4 Réponses :
Si vous ne vous souciez pas trop de l'efficacité, vous pouvez simplement tester une intersection de ligne étant donné vos deux points de référence et toutes les paires de points adjacents sur le polygone. Une fois que vous avez détecté une intersection, vous savez que votre ligne se coupe avec le polygone.
Un bon point de départ est, comme toujours, Wikipedia: http://fr.wikipedia.org/wiki/line-line_intersection
donc, permet de traverser un exemple Et n'oubliez pas de faire du vélo avec (qn, q0) pour fermer le poly! bonne chance!
ligne traverse le polygone si et seulement s'il traverse l'un de ses bords (ignorant une seconde les cas lorsqu'il passe à travers un sommet). Donc, dans votre cas, il vous suffit de tester toutes les bords de votre polygone contre votre ligne et de voir s'il y a une intersection.
Il est facile de tester si un bord , puis calculez la valeur Tout ce qui reste est de déterminer un moyen de gérer les cas lorsque la ligne passe à travers un sommet (point final d'un bord), mais il est facile à faire. (A, B) intersecte a ligne. Il suffit de construire une équation de ligne pour votre ligne sous la forme suivante AX + b par + C pour les points A et B . Si les signes de Thèses valeurs pour A et B sont différents, puis bord (a, b) intersecte la ligne.
N'y a-t-il pas un point rapide dans l'algorithme de polygone? En utilisant un, vous pouvez déterminer si exactement l'un des points est à l'intérieur, ce qui pourrait également dire l'intersection. S'ils sont tous deux situés à l'extérieur, l'une des autres méthodes est toujours requise.
Si vous voulez une bibliothèque Python pour les opérations géométriques, consultez Voici un exemple rapide d'intersections, de tampon et de coupure (avec une belle parcelle ... J'utilise galbé code> . Cela rend cela aussi simple que someline.Inersects (certainspolygon) code>. Descartes code> Pour convertir facilement des polygones élémentaires en patchs matplotlib.). P> Blue line intersects clipped shape: True
Green line intersects clipped shape: False
Est-ce que cela fonctionne avec la géométrie 3D? (Ou même la géométrie n-dénominationelle?)
Vous devez déterminer si la ligne intersecte l'un des bords du polygone ou comprend l'un de ses sommets. Selon ce que vous faites, cela peut souvent être accéléré en calculant un cercle de liaison pour chaque polygone à l'avance et vérifiez d'abord si la ligne interverse si la ligne reconvertit rapidement des polygones entiers.