Quel est le moyen le plus rapide de trouver la distance cartésienne la plus courte entre deux polygones

StackOverflow https://stackoverflow.com/questions/84034

Question

J'ai un polygone rouge et 50 polygones bleus placés au hasard : ils sont situés dans un espace 2D géographique . Quel est l’algorithme le plus rapide / rapide pour trouver la distance la plus courte entre un polygone rouge et son polygone bleu le plus proche?

N'oubliez pas qu'il n'est pas simple de prendre les points qui constituent les sommets du polygone comme valeurs pour tester la distance car ils ne sont pas nécessairement les points les plus proches.

Au final, la réponse devrait rendre le polygone bleu le plus proche du polygone rouge au singulier.

C'est plus difficile qu'il n'y paraît!

Était-ce utile?

La solution

Je doute qu'il existe une meilleure solution que de calculer la distance entre le rouge et tous les bleus et de les trier par longueur.

En ce qui concerne le tri, généralement, QuickSort est difficile à battre en termes de performances (optimisé, il coupe la récursion si la taille passe au-dessous de 7 éléments et passe à quelque chose comme InsertionSort, peut-être ShellSort).

Donc, je suppose que la question est de savoir comment calculer rapidement la distance entre deux polygones, après tout, vous devez effectuer ce calcul 50 fois.

L'approche suivante fonctionnera également pour la 3D, mais ce n'est probablement pas la plus rapide:

Distance minimale du polygone dans un espace 2D

La question est la suivante: êtes-vous prêt à échanger de la précision contre la vitesse? Par exemple. vous pouvez regrouper tous les polygones dans des boîtes englobantes, où les côtés des boîtes sont parallèles aux axes du système de coordonnées. Les jeux 3D utilisent cette approche assez souvent. Par conséquent, vous devez rechercher les valeurs maximales et minimales pour chaque coordonnée (x, y, z) afin de construire le cadre de sélection virtuel. Calculer les distances de ces boîtes englobantes est alors une tâche assez triviale.

Voici un exemple d'image de cadres de sélection plus avancés, non parallèles aux axes du système de coordonnées:

Boîtes de sélection orientées - OBB

Cependant, le calcul de la distance est moins trivial. Il est utilisé pour la détection des collisions, car vous n'avez pas besoin de connaître la distance, vous devez seulement savoir si un bord d'un cadre de sélection se situe dans un autre cadre de sélection.

L'image suivante montre un cadre de sélection aligné sur les axes:

Zone de délimitation alignée des axes - AABB

Les OOB sont plus précis, les AABB sont plus rapides. Peut-être aimeriez-vous lire cet article:

Techniques avancées de détection de collision

Cela suppose toujours que vous êtes prêt à échanger la précision contre la vitesse. Si la précision est plus importante que la vitesse, vous aurez peut-être besoin d'une technique plus avancée.

Autres conseils

Vous pourrez peut-être réduire le problème, puis effectuer une recherche intensive sur un petit ensemble.

Traitez d'abord chaque polygone en recherchant:

  • Centre du polygone
  • Rayon maximal du polygone (c'est-à-dire un point sur une arête / une surface / un sommet du polygone le plus éloigné du centre défini)

Vous pouvez maintenant rassembler, par exemple, les 5 à 10 polygones les plus proches du polygone rouge (recherchez la distance centre à centre, soustrayez le rayon, triez la liste et prenez le top 5), puis effectuez une routine beaucoup plus exhaustive.

Pour les formes de polygones avec un nombre raisonnable de points limites, comme dans un SIG ou une application de jeux, il peut être plus rapide de faire une série de tests.

Pour chaque sommet du polygone rouge, calculez la distance par rapport à chaque sommet des polygones bleus et recherchez le plus proche (indice, comparez la distance ^ 2 pour ne pas avoir besoin de sqrt ()). Recherchez le plus proche, puis vérifiez le sommet de chaque côté des sommets rouge et bleu trouvés pour déterminer les segments de droite les plus proches, puis recherchez l'approche la plus proche entre deux segments de droite.

Voir http://local.wasp.uwa.edu. au / ~ pbourke / geometry / lineline3d / (il est facile de simplement pour le cas 2d)

Cette technique de filtrage est destinée à réduire le nombre de calculs de distance que vous devez effectuer dans le cas moyen, sans compromettre la précision du résultat. Cela fonctionne sur les polygones convexes et concaves.

Trouvez la distance minimale entre chaque paire de sommets de telle sorte que l'un soit un sommet rouge et l'autre un bleu. Appelez-le r . La distance entre les polygones est au maximum r . Construisez une nouvelle région à partir du polygone rouge où chaque segment de droite est déplacé vers l'extérieur par r et est relié à ses voisins par un arc de rayon r est centré au sommet. Déterminez la distance entre chaque sommet de cette région et chaque segment de droite de la couleur opposée intersectant cette région.

Vous pouvez bien sûr ajouter une méthode approximative, telle que les cadres de sélection, pour déterminer rapidement lequel des polygones bleus ne peut éventuellement pas se croiser avec la région rouge.

Je sais que vous avez dit "la distance la plus courte". mais vous vouliez vraiment dire la solution optimale ou un "bon / très bon" solution est bien pour votre problème?

Parce que si vous devez trouver la solution optimale, vous devez calculer la distance entre toutes les limites de votre poligon source et cible (pas seulement les sommets). Si vous êtes dans un espace 3D, chaque borne est un plan. Cela peut être un gros problème (O (n ^ 2)) en fonction du nombre de sommets que vous avez.

Donc, si vous avez un nombre de sommets qui donne à ces carrés un nombre effrayant ET un "bon / très bon" la solution vous convient, optez pour une solution heuristique ou une approximation.

Vous voudrez peut-être regarder Voronoi Culling. Papier et vidéo ici:

http://www.cs.unc.edu/~geom/DVD/

Je commencerais par délimiter tous les polygones par un cercle puis par trouver une limite supérieure de la distance minimale. Ensuite, je voudrais simplement vérifier les bords de tous les polygones bleus dont la limite inférieure de la distance est inférieure à la limite supérieure de la distance minimale par rapport à tous les bords du polygone rouge.

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

Mais tout dépend de vos données. Si les polygones bleus sont relativement petits comparés aux distances qui les séparent du polygone rouge, cette approche devrait fonctionner correctement, mais s'ils sont très proches, vous ne sauvegarderez rien (beaucoup d'entre eux seront suffisamment proches). Autre chose: si ces polygones n’ont pas beaucoup de sommets (comme si la plupart d’entre eux étaient des triangles), il pourrait être presque aussi rapide de simplement vérifier chaque bord rouge par rapport à chaque bord bleu.

espérons que cela aide

Comme d'autres l'ont déjà mentionné, l'utilisation de zones de délimitation (boîtes, cercles) peut vous permettre de supprimer certaines interactions polygone-polygone. Il existe plusieurs stratégies pour cela, par exemple

.
  1. Choisissez un polygone bleu et trouvez la distance par rapport au rouge. Maintenant, choisissez n'importe quel autre polygone. Si la distance minimale entre les zones limitrophes est supérieure à la distance déjà trouvée, vous pouvez ignorer ce polygone. Continuer pour tous les polygones.
  2. Trouvez la distance minimale / centroïde entre le polygone rouge et tous les polygones bleus. Triez les distances et considérez d'abord la plus petite distance. Calculez la distance minimale réelle et parcourez la liste triée jusqu'à ce que la distance maximale entre les polygones soit supérieure à la distance minimale trouvée jusqu'à présent.

Votre choix de cercles / boîtes alignées axialement ou de boîtes orientées peut avoir un effet important sur les performances de l'algorithme, en fonction de la présentation réelle des polygones en entrée.

Pour le calcul de la distance minimale réelle, vous pouvez utiliser la commande de Noreferrer"> de Yang et al. Un nouvel algorithme rapide pour calculer la distance entre deux polygones convexes disjoints basé sur le diagramme de Voronoï 'qui correspond à O (log n + log m).

Vous devez assister à un enterrement dans une seconde, mais si vous divisez vos polygones en sous-poles convexes, vous pouvez procéder à certaines optimisations. Vous pouvez faire une recherche binaire sur chaque poly pour trouver le sommet le plus proche, puis je crois que le point le plus proche devrait être soit ce sommet, soit un bord adjacent. Cela signifie que vous devriez pouvoir le faire dans log (journal m * n) où m est le nombre moyen de sommets sur un poly et n est le nombre de polies. C'est une sorte de hâte, donc ça pourrait être faux. Donnera plus de détails plus tard si vous le souhaitez.

Vous pouvez commencer par comparer la distance entre les boîtes englobantes. Tester la distance entre les rectangles est plus facile que de tester la distance entre les polygones, et vous pouvez immédiatement éliminer tous les polygones qui sont plus que rectangle plus proche (its_diagonal) (vous pouvez éventuellement l'affiner encore plus). Ensuite, vous pouvez tester les polygones restants pour trouver le polygone le plus proche.

Il existe des algorithmes pour rechercher la proximité des polygones - je suis sûr que Wikipedia en a une bonne critique. Si je me souviens bien, ceux qui n'autorisent que les polygones convexes sont beaucoup plus rapides.

Je pense que ce que vous recherchez, c’est l’algorithme A *, utilisé dans la recherche de trajectoire.

L’approche naïve consiste à déterminer la distance entre les objets rouges et les 50 objets bleus. Vous recherchez donc 50 calculs pythagoriciens en 3D et un tri pour trouver la réponse. Cela ne fonctionnerait vraiment que pour trouver la distance entre les points centraux.

Si vous voulez des polygones arbitraires, le mieux est peut-être une solution de lancer de rayons qui émet des rayons à partir de la surface du polygone rouge par rapport à la normale et indique quand un autre polygone est touché.

Un hybride pourrait fonctionner - nous pourrions trouver la distance entre les points centraux, en supposant que nous ayons une idée de la taille relative des polygones bleus, nous pourrions sélectionner le résultat le plus proche parmi ceux-ci, puis utiliser le lancer de rayons pour réduire vers le bas du ou des polygones véritablement les plus proches.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top