Ligne horizontale la plus rapide < - > algorithme d'intersection de polygones convexes?

Question

J'ai besoin de résoudre un problème relativement simple - j'ai un polygone 2D convexe à n-sommets et une ligne horizontale (!) avec une coordonnée en «y». Je n’ai besoin que d’une chose: vérifier si le polygone est croisé avec cette ligne (c’est-à-dire avoir 2 intersections) ou non.

Le plus rapide auquel je puisse penser est de trouver les coordonnées min / max y dans un polygone (boucle répétée n fois avec deux comparaisons et deux magasins), puis de comparer si min y < = y < max y.

En quelque sorte, j’ai le sentiment que cela pourrait être résolu plus "mathématiquement". mais je finis toujours par un code plus lent (par exemple, méthode vectorielle - je dois calculer les différences pour n [i] et n [i + 1], puis les multiplier, ajouter etc. - beaucoup plus lentement que 2 cmps + magasins).

Answer 1

Il vous suffit de vérifier si votre polygone a un point avec y1 < y et un avec y2 > y. Dès que vous avez trouvé ces deux points, vous avez terminé. Si vous pouvez indexer vos points par la coordonnée y, cela devrait être une recherche rapide.

Answer 2

S'il s'agit d'une ligne 2D horizontale, alors oui, la méthode que vous avez décrite est probablement la plus rapide. Vous pouvez aussi court-circuiter le problème, comme si vous aviez une partie de la vérification et un min + max qui sont > et < votre valeur y, alors vous avez une intersection.

Answer 3

Si vous devez le faire brutalement à chaque fois, vous n’allez probablement pas trouver d’astuce pour le rendre plus rapide que cela.

Si vous pouvez mettre en cache la valeur Y min / max avec le polygone, vous pouvez gagner du temps en évitant de boucler chaque sommet à chaque fois que vous effectuez le test.

Si votre polygone est associé à une boîte englobante alignée, vous pouvez le tester en fonction de son étendue au lieu du polygone et obtenir le même résultat plus rapidement.

Answer 4

Une autre approche est décrite ici: algorithme optimal si la ligne intersecte un polygone convexe . Mais comme vous utilisez des lignes orthogonales, vous pouvez le simplifier un peu :). Ainsi, la complexité totale est log N sans stocker de valeurs.