Comment déterminer l'ordre des sommets 3D

Question

Si j'ai 5 sommets dans l'espace de coordonnées 3D, comment puis-je déterminer l'ordre de ces sommets. c'est-à-dire dans le sens des aiguilles d'une montre ou dans le sens inverse des aiguilles

Si je sur ce point plus,

J'ai un modèle 3D qui consiste ensemble de polygones. Chaque polygone est une collection de sommets et je veux calculer la norme de la surface du polygone. Pour calculer la norme, je dois considérer les sommets dans le sens inverse des aiguilles d'une montre. Ma question est donnée ensemble de sommets comment puis-je déterminer si elle est ordonnée dans le sens horaire ou antihoraire? Ceci est pour la génération de maillage de navigation où je veux supprimer les polygones qui ne peuvent pas être parcourus par l'agent. Pour ce faire, mon approche consiste à calculer la norme de surface (vecteur perpendiculaire du polygone) et à retirer le polygone en fonction de l'angle avec le plan 2D. Pour calculer la norme, je devrais savoir dans quel ordre les points sont arrangés. Donc, pour un ensemble donné de points dans un polygone, comment puis-je déterminer l'ordre de la disposition des points.

Ex.

polygon1 se composent de Vertex1 = ces 3 points [-21,847065 19,569759 -2,492895], Vertex2 [-22,279873 16,017160 1,588395], Vertex3 [-17,234818 7,132950 7.453146] et comment puis-je déterminer l'ordre de les

Answer 1

Votre question est trop mal défini pour donner une réponse complète, mais voici le squelette d'un.

La partie manquante (la viande si vous voulez), est une fonction qui prend deux coordonnées et vous indique laquelle est «plus grande» que l'autre. Sans une définition solide pour cela, vous ne pourrez rien faire fonctionner.

Le reste, le squelette, est assez simple. Triez votre liste de vecteurs en utilisant votre fonction de comparaison. Pour cinq vecteurs, un simple bubble sort sera tout ce dont vous avez besoin, bien que si le nombre de sommets augmente considérablement, vous voudrez peut-être examiner un algorithme de tri plus rapide (c'est-à-dire Quicksort).

Si la ou les bibliothèques de votre choix vous permettent de trier, vous avez déjà votre squelette.

EDIT Après re-lecture de votre question, il me aussi apparu que, puisque ces n sommets définissent un polygone, vous pouvez probablement faire l'hypothèse que tous se situent sur le même plan (si elles ne le font pas , alors bonne chance rendant que). Donc, si vous pouvez mapper les coordonnées vectorielles à des positions 2d sur ce plan, vous pouvez réduire votre problème en les ordonnant dans le sens des aiguilles d'une montre ou dans le sens inverse des aiguilles d'une montre dans un espace bidimensionnel.

Answer 2

Comme d'autres l'ont noté, votre question n'est pas entièrement claire. Est-ce que le quelque chose comme un test 3D backface culling? Si oui, vous avez besoin d'un point pour déterminer la direction de l'enroulement par rapport à. Vus d'un côté du polygone, les sommets semblent s'enrouler dans le sens des aiguilles d'une montre. De l'autre côté, ils sembleront tourner dans le sens inverse des aiguilles d'une montre. Mais supposons que votre polygone soit convexe et correctement planaire. Prenez trois sommets consécutifs A, B et C.Ensuite, vous pouvez trouver le vecteur surface normal en utilisant la cross product:

N = (B - A) x (C - A) 

Prendre le dot product de la normale avec un vecteur du point de vue donné, V, à l'un des sommets vous donnera une valeur dont le signe indique de quelle manière les sommets semblent vent vu de V:

w = N . (A - V) 

Que ce soit positif pour le sens horaire et négatif pour anti-horaire ou le contraire dépendra de la chiralité de votre système de coordonnées.

Answer 3

Je pense que votre confusion vient du fait que les méthodes de calcul de produits croisés sont parfois enseignées en termes de clockwiseness, avec un chèque de clockwiseness de 3 points A, B, C déterminant le signe de: (B-A) X (C - A) Cependant, une Une meilleure définition détermine cela pour vous. En général, on ne peut pas dire que 5 points arbitraires dans 3 dimensions ont un ordre dans le sens des aiguilles d'une montre mais 3 peuvent puisque 3 points se trouvent toujours dans un plan.