Comment puis-je déterminer si deux polygones convexes se croisent?

Question

Supposons qu'il existe un certain nombre de polygones convexes sur un plan, peut-être une carte. Ces polygones peuvent buter les uns contre les autres et partager un bord, mais ne peuvent pas se chevaucher.

Pour tester si deux polygones P et Q chevauchement, d'abord je peut tester chaque bord P pour voir si elle croise l'une quelconque des les bords en Q . Si une intersection se trouve, je déclare que P et Q intersecte. Si aucune intersecte, je dois ensuite tester pour le cas que P est entièrement contenue par Q , et vice versa. Ensuite, il y a le cas que P == Q . Enfin, il y a le cas qui partagent quelques bords, mais pas tous. (Ces deux derniers cas peuvent probablement être considérés comme le même cas général, mais qui pourrait ne pas être important.)

I ai un algorithme qui détecte lorsque deux segments de droite se croisent. Si les deux segments sont colinéaires, ils ne sont pas considérés comme recouper pour mes besoins.

Ai-je bien énuméré les cas? Toutes les suggestions pour tester ces cas?

Notez que je ne cherche pas à trouver le nouveau polygone convexe qui est l'intersection, je veux juste savoir s'il existe une intersection. Il existe de nombreux algorithmes bien documentés pour trouver l'intersection, mais je ne pas besoin de passer par tous les efforts.

Answer 1

Vous pouvez utiliser cet algorithme de collision :

  

Pour être en mesure de décider si deux polygones convexes se croisent (se touchent), nous pouvons utiliser le théorème de séparation Axe. Essentiellement:

     

  
• Si deux polygones convexes ne sont pas sécantes, il existe une ligne qui passe entre eux.
  
• Une telle ligne existe que si l'un des côtés de l'un des polygones forme une telle ligne.
  

     

La première déclaration est facile. Étant donné que les polygones sont à la fois convexe, vous serez en mesure de tracer une ligne avec un polygone d'un côté et l'autre polygone de l'autre côté à moins qu'ils ne se croisent. Le second est un peu moins intuitive. Regardez la figure 1. À moins que le plus proche côtés des polygones sont parallèles les uns aux autres, au point où ils se le plus proche de l'autre est le point où un coin d'un polygone se rapproche le plus d'un côté de l'autre polygone. Ce côté formera alors un axe de séparation entre les polygones. Si les côtés sont parallèles, les deux axes se séparent.

     

     

Alors, comment cela nous aide concrètement à décider si un polygone se croisent A et B? Eh bien, nous allons un peu plus de chaque côté de chaque polygone et vérifier si elle forme un axe de séparation. Pour ce faire, nous allons utiliser un peu de maths de vecteur de base de squash tous les points des deux polygones sur une ligne qui est perpendiculaire à la ligne de séparation potentiel (voir la figure 2). Maintenant, le problème est commodément 1 dimensions. On peut déterminer une région dans laquelle les points pour chaque polygone se trouvent, et cette ligne est un axe de séparation si ces régions ne se chevauchent pas.

     

     

Si, après avoir vérifié chaque ligne des deux polygones, aucun axe de séparation a été trouvé, il a été prouvé que les polygones se croisent et quelque chose doit être fait à ce sujet.

Answer 2

• si les polygones sont toujours convexe, premier calcul de l'angle d'une ligne de centre à centre des polygones. on peut alors éliminer besoin de tester des segments de bord dans la partie du polygone (s) de 180 degrés par rapport à l'autre polygone (s).

• pour éliminer les arêtes, commencez par le polygone à gauche. prendre le segment de ligne à partir du centre du polygone qui est perpendiculaire au segment de ligne à partir du point précédent, et touche les deux côtés du polygone. appeler ce segment de droite p, avec vertex p1 et p2. Ensuite, pour tous les vertex si la coordonnée x est inférieure à P1.x et p2.x Ce sommet peut aller dans le « seau sûr ».

• si elle n'a pas, vous devez vérifier pour vous assurer qu'il est sur le côté « sûr » de la ligne (il suffit de cocher les coordonnées y aussi)

-si un segment de ligne dans le polygone a tous les sommets dans le « seau sûr » vous pouvez l'ignorer.

-reverse la polarité de sorte que vous êtes « droit orienté » pour le second polygone.

Answer 3

Vos cas de test devrait fonctionner, puisque vous vérifiez le cas où les polygones ne se coupent pas du tout (complètement à l'extérieur ou complètement à l'intérieur), ainsi que là où il y a une forme d'intersection partielle (arêtes se croisent toujours s'il est chevauchement).

Pour les tests, je voudrais juste assurez-vous de tester toutes les combinaisons potentiel. L'un disparu au-dessus de ce que je vois est un seul bord partagé, mais un poly contenu dans l'autre. Je voudrais aussi ajouter des tests pour certaines formes de poly plus complexes, de tri -.> De nombreux côtés, comme précaution

En outre, si vous avez eu une forme de U qui entoure complètement poly poly, mais ne se chevauchent pas, je crois que votre cas traiterait, mais j'ajouter que comme un contrôle, aussi bien.

Answer 4

Depuis altCognito vous avez déjà donné une solution, je ne signale un excellent livre sur la géométrie de calcul qui pourraient vous intéresser.

Answer 5

GJK collision href="https://mollyrocket.com/forums/viewtopic.php?t=245" rel="nofollow noreferrer"> devrait travail .

Answer 6

Voici une idée:

• Trouver le point central de chaque polygone

• Trouver les deux points de chaque polygone le plus proche du point central de l'autre. Ils seront des points adjacents dans des polygones convexes. Ceux-ci définissent le bord le plus proche de chaque polygone, nous allons appeler les points {A, B} et {Y, Z}

• Trouver l'intersection des lignes AB et YZ. Si les segments de ligne se croisent (l'intersection AB se situe entre A et B), vos polygones se croisent. Si AB et XY sont parallèles ignorer cette condition, l'étape suivante interceptera le problème.

• Il y a un plus si vous avez besoin de vérifier, ce qui est quand les polygones se croisent assez fortement que AB et XY sont complètement passés entre eux et ne fait pas recouper. Pour piéger ce cas, calculer les distances perpendiculaires de AB et XY à chacun des points centraux de polygones. Si l'point central est plus proche du segment de ligne de polygone en face de votre chevauchement des polygones fortement.

Answer 7

Il existe plusieurs façons de détecter l'intersection et / ou confinement entre les polygones convexes. Tout dépend de l'efficacité que vous voulez que l'algorithme soit. Considérons deux polygones convexes R et B dont les sommets r et b, respectivement:

1. ligne de balayage algorithme. Comme vous l'avez mentionné, vous pouvez effectuer une procédure de ligne de balayage et de garder les intervalles résultant de l'intersection des polygones avec la ligne de balayage. Si à tout moment les intervalles se chevauchent, puis les polygones se croisent. La complexité est O ((r + b) log (r + b)) temps.
2. algorithme basé Rotating Etriers. Voir et ici pour plus de détails. La complexité est O (r + b) temps.
3. Les méthodes les plus efficaces sont disponibles et ici . Ces algorithmes prennent O (log r + log b) le temps.