J'ai deux polygones convexes en 3D. Ils sont tous deux à plat sur différents plans, alors ils sont une paire de visages.
Quel est le moyen le plus simple de calculer la distance la plus proche entre ces deux polygones?
Edit: la longueur de la ligne la plus courte possible qui a un point d'extrémité dans le premier polygone et un autre autre point d'extrémité dans le second polygone. La distance que je recherche est la longueur de cette ligne la plus courte possible.
5 Réponses :
Boucle à travers tous les sommets du premier objet, puis dans cette boucle, boucle à travers tous les sommets du deuxième objet. Dans votre boucle la plus interne, comparez la distance entre les deux sommets actuels et stockez la distance la plus basse. Je le fais de cette façon tout le temps et aussi longtemps que vous n'avez pas de maillage ridiculement grand, il est à peu près instantané.
Les sommets pourraient ne pas aligner. Par exemple, il est possible que ces deux polygones se touchent à un angle droit, avec l'un des sommets du deuxième polygone touchant le premier polygone au centre.
Ce n'est pas clair ce que vous avez essayé.
Ce semble probable pour les segments en soi.
Alors, tout ce que vous avez à faire est de vérifier toutes les paires de bords. Je chercherais à mettre en œuvre cela d'abord avant d'essayer d'optimiser.
Il y a probablement une optimisation dans la prise en compte du vecteur d'un Centroid à l'autre et envisager uniquement des bords qui sont en quelque sorte dans cette direction.
@Blueraja, @DMI. OK, a raté le cas noté. Il me semble toujours comme un algorithme relativement stupide devrait fonctionner. Le problème est-il en calculant les distances entre paires primitives (surface, bord, sommet) ou déterminer quels ensembles de paires primitives doivent être calculés? Ou être sûr que même vérifier que toutes les paires primitives répondent à l'exigence?
Ce serait bien, sauf qu'il est possible qu'un polygone "touche" l'autre polygone dans son centre à angle droit. Dans ce cas, le deuxième polygone aura un bord ou un sommet qui touche le plan du premier polygone tout en étant toujours à une distance des bords du premier polygone.
Eh bien, il n'y a que quelques possibilités; La ligne la plus courte entre les deux polygones pourrait être:
Les cas 1-3 sont tous pris en charge en traitant chaque tranchant + verx-paire en tant que segment de ligne et enumérant le distance entre toutes les paires de segments de ligne .
Pour le cas 4, recherchez le distance entre chaque sommet et l'autre plan du polygone . Vérifiez que la ligne (couvrant du sommet au point le plus proche de l'avion) est à l'intérieur de l'autre polygone; Si ce n'est pas le cas, la ligne la plus courte de l'autre polygone sera sur son périmètre, déjà pris en charge dans le cas 1 ou 2. Pour le cas 5, au moins un segment de ligne doit se croiser avec la zone de l'autre polygone - s'ils se sont intersectés sur leurs périmètres, nous l'aurions déjà pris dans des cas 1 à 3, et si un sommet intersecté la zone, nous aurait attrapé-le dans l'affaire 4. Alors simplement vérifier le intersection de chaque bord avec le plan de l'autre polygone et Voir si le point d'intersection est à l'intérieur de l'autre polygone. Prenez la distance minimale trouvée dans tout cela, et nous avons fini.
(assurez-vous de faire cette vérification pour polygones)
(assurez-vous de faire cette vérification pour polygones)
Cela semble assez simple, je vais essayer cela.
Je pense que vous oubliez de mentionner le cas où les 2 polygones sont parallèles. Il est inclus dans 1-4, donc pas de problème, mais mieux garder cela à l'esprit lorsque vous faites les mathématiques pour les projections, etc. En raison de la recherche de point d'intersection sans envisager le cas parallèle causer souvent des erreurs désagréables. Par exemple, la vérification de 5 besoin de surveiller ceci (intersection de chaque bord avec le plan de l'autre polygone).
@Alink: Correct, je n'ai pas mentionné cela parce que c'est inclus dans 1-4, mais c'est quelque chose à craindre. L'affaire Edge / Inside-of-Other-Polygon est une autre: elle est incluse dans les cas 3-4, mais il est toujours nécessaire de prendre conscience de (à tout le moins pour les tests).
@DMI: Je vois que vous avez marqué cela correct. Je pense vraiment que vous devriez considérer la solution de @benoigt; C'est la vraie réponse correcte.
Merci, j'ai en fait mis en œuvre cela maintenant et cela fonctionne bien. Je vais également jeter un coup d'œil à l'autre méthode après avoir lu sur la programmation quadratique un peu plus.
Il s'agit d'une optimisation délimitée simple avec des contraintes linéaires et une fonction d'objectif quadratique. Il existe de nombreux algorithmes qui peuvent être utilisés, tels que la descente de gradient.
Pourriez-vous s'il vous plaît expliquer un peu plus loin - que serait la fonction d'objectif quadratique?
L'objectif est "minimiser (x2 - x1) ** 2 + (y2 - y1) ** 2 + (z1 - z1) ** 2". Les points qui donnent la distance minimale donnent également la distance minimale carré.
Ah, et les contraintes seraient "X1, Y1, Z1 se situe sur un tel plan et un tel plan" et "x1, Y1, Z1 se trouvent sur cette moitié de l'avion" pour chaque bord. Brillant! Tant que vous pouvez diviser un avion en deux dans de l'espace 3D en utilisant une seule équation (que je crois que vous pouvez, mais d'être honnête, je n'ai posé aucune pensée) , cela fonctionnera , et sera plus facile et moins émis par des erreurs que ma méthode. +1!
@Blueraja: une inégalité linéaire crée un demi-espace. Une égalité linéaire crée un plan (qui peut être exprimé comme l'intersection de deux inégalités), puis sur le point d'intersecter plus de demi-espaces permet de définir une forme convexe.
Ce que la plupart des gens ont proposé sur ce thread est "Prenez tous les points / bords d'un polygone et comparer à chaque point / bords de l'autre". Cela va probablement fonctionner bien si tout ce que vous faites est de comparer deux polygones assez simples et si vous n'êtes pas trop préoccupé par le faire rapidement.
Cependant, si vous voulez une méthode assez facile et meilleure. Utilisez, comme suggéré par Ben Voigt, une méthode d'optimisation quadratique (c'est-à-dire une méthode d'optimisation quadratique (c'est-à-dire une méthode d'optimisation quadratique (I.e programmation quadratique ). Fondamentalement, vos polygones sont votre ensemble de contraintes linéaires, c'est-à-dire que votre point de solution doit mentir vers le côté intérieur de chaque bord de votre polygone (c'est une contrainte d'inégalité). Et votre fonction de coûts à optimiser n'est que la distance euclidienne, c'est-à-dire la Q dans la formulation standard, c'est juste la matrice d'identité. Une fois lancé en tant que tel problème, vous pouvez utiliser une bibliothèque qui la résout (il y en a beaucoup d'entre eux) ou vous pouvez l'étudier à partir d'un livre et vous pouvez en faire valoir votre propre code (c'est un algorithme assez facile à coder ).
Si vous voulez une méthode réelle de faire cela, par exemple, si ce simple test de polygon-polygone est la première étape vers des formes 3D plus complexes (comme un solide en polygones). Ensuite, vous devriez probablement utiliser simplement un paquet qui le fait déjà. ici est un ensemble de bibliothèques de détection de collision, dont beaucoup de la profondeur de pénétration de la sortie ou, de manière équivalente, une distance minimale.
Merci, cela ressemble à un sujet intéressant. Je ne vais pas vers des formes plus complexes, je cherche simplement des paires de distances simples pour des visages 3D.
Vous recherchez la distance entre leurs centroïdes ou la distance entre leurs deux bords les plus proches?
Donc, pas la distance entre les deux points les plus proches alors? Comment définissez-vous le "bord le plus proche" et, étant donné une définition appropriée, comment définissez-vous la distance entre les deux bords les plus proches?
La longueur de la ligne la plus courte possible qui a un point d'extrémité dans le premier polygone et un autre autre point d'extrémité dans le second polygone. La distance que je recherche est la longueur de cette ligne la plus courte possible.
Ce n'est pas les deux bords les plus proches, c'est-à-dire les deux points les plus proches. Dans quel cas, +1, grande question :)
Notez que si les deux polygones sont parallèles, la ligne la plus courte n'est pas unique;) Mais puisque toutes ces lignes les plus courtes ont la même longueur, la distance est toujours bien définie.