Intersection de polygones

Il y a deux polygones donnés. Comment peut-on déterminer si un polygone est à l’intérieur, à l’extérieur ou en intersection de l’autre? Les polygones peuvent être concaves ou convexes.

Vous souhaitez utiliser le théorème de séparation des axes pour les polygones convexes. Fondamentalement, pour chaque face de chaque polygone, vous projetez chaque polygone sur la normale de cette face et vous voyez si ces projections se croisent.

Vous pouvez effectuer différentes astuces pour réduire le nombre de calculs à effectuer. Par exemple, vous pouvez tracer un rectangle autour de l’object et supposer que si les rectangles de deux objects ne se croisent pas, ils ne se croisent pas eux-mêmes. (Ceci est plus facile car il est moins coûteux en calculs de vérifier l’intersection de ces cases et est généralement assez intuitif.)

Les polygones concaves sont plus difficiles. Je pense que vous pouvez décomposer le polygone en un ensemble de polygones convexes et essayer de vérifier chaque combinaison d’intersection, mais je ne me considérerais pas assez compétent dans ce domaine pour l’essayer.

Généralement, de tels problèmes sont facilement résolus par un algorithme de balayage. Cependant, le principal objective et l’avantage de l’utilisation de l’approche par ligne de balayage est qu’elle peut résoudre le problème efficacement lorsque l’entrée est constituée de deux ensembles relativement grands de polygones. Une fois que la solution de ligne de balayage est implémentée, elle peut également être appliquée efficacement à une paire de polygones, le cas échéant. Vous devriez peut-être envisager d’aller dans cette direction, au cas où vous auriez besoin de résoudre un problème massif à l’avenir.

Cependant, si vous êtes certain d’avoir besoin d’une solution pour deux et deux polygones seulement, vous pouvez la résoudre à l’aide de tests séquentiels point / polygone et segment / polygone.

Il existe une méthode facile pour vérifier si un point est situé dans un polygone. Selon cet article de Wikipedia, cela s’appelle l’algorithme de lancer de rayons.

L’idée de base de l’algorithme est de lancer un rayon dans une direction arbitraire à partir du point que vous testez et de compter le nombre d’arêtes du polygone qu’il intersecte. Si ce nombre est pair, le point se trouve en dehors du polygone, sinon s’il est impair, le point se trouve à l’intérieur du polygone.

Cet algorithme pose un certain nombre de problèmes que je ne vais pas approfondir (ils sont décrits dans l’article de Wikipédia que j’ai déjà lié), mais c’est la raison pour laquelle j’appelle cet algorithme easyish. Mais pour vous donner une idée, vous devez gérer les cas d’angle impliquant le sumt intersectant les rayons, le rayon parallèle et l’intersection d’un bord et les problèmes de stabilité numérique avec le point situé près d’un bord.

Vous pouvez ensuite utiliser cette méthode de la manière décrite par Thomas dans sa réponse pour vérifier si deux polygones se croisent. Cela devrait vous donner un algorithme O(NM) où les deux polygones ont respectivement N et M sumts.

Voici un algorithme simple pour savoir si un point donné est à l’intérieur ou à l’extérieur d’un polygone donné:

 bool isInside(point a, polygon B) { double angle = 0; for(int i = 0; i < B.nbVertices(); i++) { angle += angle(B[i],a,B[i+1]); } return (abs(angle) > pi); } 
  • Si un segment de ligne de A coupe un segment de ligne de B, les deux polygones se coupent.
  • Sinon, si tous les points du polygone A sont à l’intérieur du polygone B, alors A est à l’intérieur de B.
  • Sinon, si tous les points du polygone B sont à l’intérieur du polygone A, alors B est à l’intérieur de A.
  • Sinon, si tous les points du polygone A sont hors du polygone B, alors A est en dehors de B.
  • Sinon, les deux polygones se croisent.