Comparaison et Unicité de polygones en 3D

[fcaillaud]

Bonjour,

Je cherche un moyen (très) rapide de comparer 2 polygones quelconques (A et B) en 3 dimensions. Ceci afin de pouvoir faire A < B (par exemple) et si A < B = faux et B < A = faux alors A == B (j'espère que c'est clair :soupir2:)

Voici quelques idées que j'ai eu mais aucune n'est parfaite (du moins lorsqu'on l'utilise seule) et une combinaison serait peu rapide :

1. Comparaison du nombre d'arêtes/sommets
2. Comparaison de normales
3. Comparaison de barycentre
4. Comparaison 2 à 2 des sous éléments :
   
   1. Comparaison des arêtes ( les arêtes sont ordonnées dans le sens de parcours, entre autres pour le calcul de la normale, mais la première arête du premier polygone n'est pas forcement celle du deuxième )
   2. Comparaison des sommets (même problème que pour les arêtes )

Pour l'instant j'ai une solution, mais qui n'est sûrement pas optimale.

Si vous aviez des idées que l'on pourrait débattre, ce serait vraiment intéressant !

Merci d'avance à vous tous.

[fatal_error]

bj,

en tout cas on peut voir que:
si t'as n points dans les deux cas (resp a_i et b_j)
tu peux comparer tous les couples (a_i; b_j), et des que ya un j trouvé pour a_i fixé , alors t'enlèves le couple a_i;b_j; et tu recommences.
Si il existe pas de j tel que a_i==b_j, alors tes polygones sont différents.

On peut majorer ca par n^2 comparaisons( le produit cartésien )
en vrai ya un peu moins (genre la moitié grosso modo), pour aller jusqu'à la fin, ya
n+n-1+n-2...+1 == (n^2+n)/2

Mais si tu sais que tes points sont donnés dans l'ordre,
tu preux prendre a_0 chercher j tq a_0==b_j
puis chercher a_1==b_(j+1%n) ou a_1==b_(j-1+n%n)
si ca correspond, tu connais le sens de parcours, et apres t'as plus qu'une comparaison 1 à 1
donc au final t'as n+2+ (n-2) étapes == 2n comparaisons

ps:note que si tu montres que A!=B, tu pourras pas dire si ASi tu veux avoir un ordre parmi tes polygones, je dirais assez intituivement qu'il faut ordonner la représentation de tes points (idem tu donnes le polygone avec des points triés), et après t'as plus qu'à comparer tes vecteurs de points entre eux.. composante à composante!

[fcaillaud]

Oui, je suis d'accord avec toi, avec les sommets dans l'ordre, et une fois que j'ai le matching entre 2 sommets, je peux faire une comparaison circulaire 1 à 1. Évidemment, vu que je veux en premier lieu une comparaison entre 2 polygones, la comparaison entre les sommets ne peux être que du type :

1. a_i A b_j -> B on continue

Pour l'instant c'est plus ou moins la méthode que j'utilise.

Mais cette méthode n'est pas très robuste. Car si j'ai un polygone ABC plus petit que IJK, rien ne me dit que BCA le sera également puisque l'on se repose sur le a_i du premier polygone pour commencer la comparaison circulaire.

La solution, comme tu l'as dit serait de trier les sommets des deux polygones. Là pas d'a priori sur le commencement des comparaisons mais on perd l'ordre des sommets autour des polygones. ABCD sera alors égal à ACBD alors que ce n'est pas le cas en réalité.

Avec ce type de comparaison, le problème c'est que pour être robuste, on tombe dans la lourdeur, ce qui augmente le temps de calcul. Pour donner un ordre d'idée, je dois faire environ 10 millions de comparaisons de polygones donc on voit rapidement la limite !

[fatal_error]

10 millions c'est pas forcément très important...ca dépend combien de temps tu as ( et ce que tu as comme bécane aussi..)

mis à part,
si tu prends deux polygones A,B (A(a_1,a_2,...,a_n), B(b_1,...,b_n))

On est d'accord qu'on peut avoir un ordre sur les points facilement (par ex lexico)
donc on peut trouver le a_ia return b;
fintantque
return false[/CODE]

si tu réécris pas tes polygone avant de faire la comparaison, alors tu peux devrais au moins pour chacun d'eux connaitre l'indice du point mini et le sens de parcours..

A la louche qqch comme

Code: Tout sélectionner

class Polygone {
  vector v;
  size_t minIndex;
  bool goRight;
}
void Polygone::preOrder(){
  minIndex = 0
  for(size_t i=0; ia) return false;
    currentAIndex+=A.goRight?1:-1
    currentBIndex+=B.goRight?1:-1
  }
  return false;
}


[Cliffe]

Je cherche un moyen (très) rapide de comparer 2 polygones quelconques (A et B) en 3 dimensions. Ceci afin de pouvoir faire A < B (par exemple) et si A < B = faux et B < A = faux alors A == B

ça veut dire quoi un polygone inférieur à un autre ?

[fcaillaud]

Pour te répondre en premier, fatal_error, 10 millions n'est pas beaucoup (encore que) sauf si le traitement doit être en temps réel et que ces comparaisons ne sont qu'un dixième (voir un vingtième) de mon traitement total.

Autrement, pour des raisons d'implémentation et d'optimisation (et oui, snif), je ne peux pas réécrire l'ordre des sommets sur un polygone, ni ajouter un flag pour spécifier le sens de parcours (plus précisement, je me l'interdit, j'utilise une structure générique et si je commence à mettre en place des flags pour ça, ça va devenir n'importe quoi rapidement).

Mais l'idée de faire des comparaisons sommet à sommet en partant du minimum et en allant dans le même sens sur les 2 polygones me paraît possible. Ça reste un peu lourd mais c'est le mieux que j'ai pour l'instant !!

ça veut dire quoi un polygone inférieur à un autre ?

Le inférieur n'est qu'une relation d'ordre permettant de trier des polygones et de pouvoir définir un opérateur d'égalité.

[Cliffe]

Le inférieur n'est qu'une relation d'ordre permettant de trier des polygones et de pouvoir définir un opérateur d'égalité.

Ma question est la mm. Qu'elle est la relation d'ordre ?
Qu'est ce que trier des polygones ? Qu'est ce que deux polygones égaux ?

S'il s'agit d'avoir les mm sommets et les mm arêtes alors il suffit d'utiliser les opérateurs de comparaisons bit a bit en C++ par exemple.
Tu dois juste trier les sommets/arêtes.

[fcaillaud]

Ma question est la mm. Qu'elle est la relation d'ordre ?
Qu'est ce que trier des polygones ? Qu'est ce que deux polygones égaux ?

S'il s'agit d'avoir les mm sommets et les mm arêtes alors il suffit d'utiliser les opérateurs de comparaisons bit a bit en C++ par exemple.
Tu dois juste trier les sommets/arêtes.

Excuse moi, je ne suis pas vraiment précis.

En fait, la relation d'ordre en elle même importe peu. Je cherche simplement à pouvoir trier de manière unique et robuste des polygones mais ne pas inclure deux fois le même polygone.

Et soit les polygones A et B, A == B s'il sont géométriquement égaux (que les coordonnées de leurs sommets sont égaux 1 à 1), et bien sûr que leurs sommets soient reliés de la même façon (par des arêtes) -> ABCD sera différent de ACBD.

Voilà, j'espère que c'est plus clair.

[Cliffe]

Tu as un grand nombre de polygones et tu souhaite virer les doublons ?

[fcaillaud]

Oui ET obtenir un ordre dans cet ensemble de polygones.

EDIT : peu importe l'ordre.

[Cliffe]

ce genre de truc ? : http://fr.wikipedia.org/wiki/Fonction_de_hachage

[fatal_error]

Ben perso, je trouve ca pas tres lourd, mais bon
je pense que c'est dommage de pas pouvoir manipuler un peu les données.
On pourrait tres bien imaginer une struct avec ces données + pointeur vers polygone, ca fait
1(struct)+4(bool)+4(index)+4(pointeur) octets de plus,
jpense pas c'est un énorme overhead par rapport à la taille de Polygone qui contient plusieurs points... et ca joue bcp parce que c'est du temps CPU que tu sauves à chaque fois que tu vas comparer deux polygones.

Ici, on voit que dans l'algo on va comparer point à point (2n worst case (n pour le point le plus petit, plus n comparaisons point à point). Mais on peut imaginer faire au minimum n+1 si on suppose qu'on store directement f(A) dans la structure, et compare f(A) à f(B), avec f typiquement une fonction injective..)

Et il faut bien sur que le cout de la fonction f soit suffisamment faible.
(à priori comme l'a suggéré Cliffe dans un de ses posts, on peut comparer bit à bit moyennant la position du point minimal et du sens, mais je suis pas sûr que ca soit plus rapide déjà psk je connais pas mes instructions asm)

Si on suppose que cout(calcul de f(A))==n au minimum, à chaque fois que tu vas comparer A à un autre polygone, tu vas payer n + le coup de comparaison
Alors que si tu stores f(A), tu vas juste payer le cout de comparaison!

[Cliffe]

avec f typiquement une fonction injective..)

Toute la difficulté est là. Je ne pense pas cette fonction existe.
On peut facilement trouvée une fonction surjective, et lorsque deux éléments où plus on la mm image (empreinte) alors il faut faire une comparaison plus poussée.

Exemple simple, si on note l'ensemble des polygones :
[CENTER]
[/CENTER]

avec le volume de .

[fcaillaud]

Merci pour toutes vos réponses.

Cliffe, malheureusement, l'utilisation de fonctions de Hachage serait possible (bien que j'utilise plutôt des std::set en C++ pour l'instant), mais cela n'enlève pas qu'il faut les définir et conserver à la fois les polygones et la table de hachage (même si cela ne reste que des mots.

Je ne l'ai pas mentionner avant pour ne pas trop contraindre le raisonnement mais mes polygones sont constitués d'arêtes, et mes arêtes de 2 sommets. Ce qui fait que c'est plus rapide pour moi de manipuler les arêtes que les sommets.

J'ai déjà un ordre définit sur les arêtes (à partir des sommets), donc je pense que je vais retenir ton idée, fatal_error, de trier les arêtes (plutôt que les sommets) et de les comparer 1 à 1.

Avec cette méthode, au final, on compare quand même les sommets entre eux mais en étant robuste aux différences de topologie. J'ai fait mes calculs et ça paraît être le plus efficace en allouant pas plus de mémoire (j'ai des contraintes également sur ça).

[Cliffe]

du coup c'est quoi l'ordre ?

[fcaillaud]

du coup c'est quoi l'ordre ?

L'ordre est un ordre lexicographique. Un polygone est plus petit qu'un autre si ses arêtes (triées) sont plus petites que l'autre polygone. Et une arête est plus petites qu'une autre si ses sommets (triés) sont plus petits que l'autre arêtes. Enfin, un sommet est plus petits qu'un autre si ses coordonnées (d'abord x, ensuite y puis z) sont plus petits que l'autre sommet.

Mais au final, la nature de l'ordre importe peu, l'important est d'en avoir un, pour pouvoir parcourir de façon unique et sans doublon la liste des polygones.

L'intérêt peut paraître faible, mais pour comparer 2 complexes polygonaux (aux indices de sommets différents mais avec potentiellement la même géométrie et la même connectivité), par exemple, ça peut être utile.

[fatal_error]

Toute la difficulté est là. Je ne pense pas cette fonction existe.

ben créer une fonction injective, c'est assez trivial.
Tu ordonnes tes sommets.
Tu concatènes tes sommets (idem une suite de bits)
et voilà t'as une fonction injective..

Apres si tu demandes une comparaison sur la suite de bits, qui doit etre grosse, je sais pas combien de cycles il faut, et si c'est plus rapide que de faire point par point et de potentiellement arreter la comparaison apres le premier point... trop hardware pour moi et pas le plus passionant pour moi non plus

[Cliffe]

du coup on reviens à mon deuxième post.
Tu vas te taper plein de trie à faire.

ben créer une fonction injective, c'est assez trivial.
Tu ordonnes tes sommets.
Tu concatènes tes sommets (idem une suite de bits)
et voilà t'as une fonction injective.

Tu peux avoir deux polygones différents avec le mm nombre de sommets et qui te donne le mm ordre ...
Il faut prendre les coordonnées des sommets pour que ça fonctionne.