Distance pour déplacer deux polygones afin qu'ils touchent les bords

Question

Le mieux décrit dans l'image ci-dessous.

J'ai besoin de connaître la distance minimale pour déplacer un polygone de référence (en rouge) dans un axe (juste y) tel qui vient toucher l'autre polygone. Si c'est à l'intérieur du polygone, il devra se déplacer vers l'extérieur. J'ai essayé de regarder toutes les lignes d'un polygone et tous les points d'un autre, de projeter le point sur la ligne et d'obtenir la différence entre le point y et le point de projection y, puis de trouver la distance minimale. Cependant, cela posait le problème que si les polygones se chevauchaient et que la ligne la plus éloignée d'un polygone et le point le plus éloigné de l'autre avaient la distance minimale, cela donnerait un résultat qui ferait chevaucher les polygones. Edit: en projetant le point sur la ligne, je veux dire trouver la valeur y pour un point sur la ligne qui a la même valeur x que le point d'origine. Ignorez cette étape si la valeur x se trouve en dehors de la ligne.

Answer 1

Je ne suis pas sûr d'avoir bien compris votre proposition (qu'est-ce que "projeter le point sur la ligne"?).

Quoi qu'il en soit, je voudrais essayer ce (pseudo code),:

for pA: points of polygon A: 
    for sB: segments of polygon B 
     compute distance along y-axis d(pA,sB) and store in table 
Find minimum distance in table: d1 
Proceed as above by reversing A and B: d2 
final d = min(d1,d2) 

Mais malheureusement, cela est probablement pas bon si vos polygones sont concaves, ce qui semble être le cas.

Answer 2

Vous devez dessiner une ligne verticale à travers chaque sommet des deux polygones et déterminer son intersection avec les polygones (une intersection de ligne/polygone est faite d'intervalles disjoints).

Sur une verticale donnée, calculez la différence entre l'extrémité la plus élevée d'un polygone et la plus basse de l'autre. La réponse est la plus petite différence parmi toutes les verticales (ce qui peut être un nombre négatif). Pour effectuer le calcul efficacement, vous pouvez utiliser le principe de la ligne de balayage: trier tous les sommets de gauche à droite et maintenir une "liste active", qui est la liste des arêtes qui coupent la verticale actuelle. Lorsque vous passez d'un sommet à l'autre, vous mettez à jour cette liste.

Pour deux polygones de taille N et M, le tri coûtera O(N+M)Log(N+M)); alors le balayage coûtera approximativement O((N+M)K), où K est le nombre moyen d'intersections d'une verticale avec un polygone, habituellement un petit nombre entre 2 et 4.