Problème chaud en 3D (maths avancé)

Messages postés
370
Date d'inscription
lundi 1 avril 2002
Statut
Membre
Dernière intervention
11 février 2010
- - Dernière réponse : crenaud76
Messages postés
4172
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
9 juin 2006
- 27 févr. 2004 à 21:23
Je possède un nuage de n points dans l'espace (j'ai accès aux coordonnés de chacun des points)

Problème :

Trouver l'équation d'un plan
qui sépare le nuage en deux nuages.

Si n est pair chaque sous-nuage possèdera (n div 2) points.
Sinon l'un aura (n div 2) points et l'autre ((n div 2) + 1).

Question simple ... réponse difficile :C

Je pourrais bien sur tenter de résoudre ça à la bourrin
mais je dois le faire un nombre assez conséquent de fois.
Et ma méthode pour l'instant ne marcherai pas pour certain cas particulier.

Je cherche donc l'algorithme (itératif si possible mais pas grave si fonctionnel) dans n'importe quel langage.

Mais toute aide est la bienvenue.

Merci d'avance.

-={[ Zeroc00l ]}=-
Afficher la suite 

3 réponses

Messages postés
4172
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
9 juin 2006
15
0
Merci
Voici une idée de départ :
1- Rechercher les deux points les plus éloignés l'un de l'autre (nommons les A et B)
2- Définir la droite passant par A et B (nommons-la D)
3- Définir un plan dont D est la normale et tel que A soit dans ce plan (nommons-le P)
4- Calculer la distance de tous les autres points à ce plan P.
5- trier les points selon leur distance au plan P.
6- tu tapes ensuite au milieu de ton tableau entre les points A' et B', disons.
7- A' doit donc faire parti du nuage N°1 et B' du nuage N°2
8- tu fait la moyenne de la distance de P à A' et de P?à B', nommons cette moyenne dm
9- Déplace P d'une distance dm le long de D.
10 - Tu as ton plan et tes deux nuages.
J'ai été clair ?

Ca merdouille dans des cas particuliers : quand tous les points, autres que A et B, sont dans un même plan, dont D est une normale.
Cela peut être solutionné en ne prenant pas les même A et B au départ. Le fait de prendre les deux points les plus éloignés me paraissait intéressant pour éliminer des cas particuliers, mais en fait, cela ralonge l'alogrithme (recherche de ces deux points au départ, obligeant un calcul de distance point à point) et cela ne résoud pas tout. Pourquoi ne pas essayer avec deux points au hasard dans le nuage. Cela devrait fonctionner aussi.
Christophe R.
Messages postés
370
Date d'inscription
lundi 1 avril 2002
Statut
Membre
Dernière intervention
11 février 2010
0
Merci
En fait j'y avait pense ...
mon probleme etait de separer les centre de gravite des face d'un polyedre

(pk j'ai pas pris les sommet ? parce qu'un sommet peut servir a 99% d'un mesh (la pointe d'un cone par exemple pour un mesh represdentant une glace ) )
je suis sur (pratiquement ) que les centre des triangle sont unique , ou bien c'est que les faces sont au meme endroit et peut etre a l'envers (normale dans l'autre sens ).

mon but est de separer recursivement le nuage de point
mais il existe bcp de cas articulier ;
Soit R1, R2, R3 reels

Par exemple un cercle dans le plan Oxy de rayon R1
+ un cercle dans le plan Oxz de rayon R2
+ un cercle dans le plan Oyz de rayon R3

en fait ce ne sont as des cercle mais des point situe sur ces cercle (disons 10 par cercle )

si je prend les points les plus éloignés, je vais prendre les deux point qui distant du plus grand rayon des cercle (pour eu que le nombre de point du cercle soit paires mais bref .. on s'en fout).
lorsque je vais crrer un plan .. je vais avoir un des deux autre cercle compris dans le plan a quel coté appartiennent til ?

Le but est de trouver un plan qui separe vraiment le nuage de tel sorte que la distance entre el point le plus proche du plan SOIT maximum
Pour un polyedre representant des haltere cet algo marcherai bien... mais our une sphere ...
je cherche un algo qui me trouve un plan optimale ...msi bon si y'a deja un algo qui marche deja bien ... :)

Il faut surtout qu'aucun point ne soit contenu dans le plan a chaque fois que l'on coupe et cela n'est pas impossible.
Ceci du au fait que le nombre de point n'est pas infini (je le prouve pas ca me semble intuitif mais si vous avez la preuve contraire donner la moi quand meme :) )

Bien sur on pourrait ecrire des algo bourrin ... mais calculer les deux point les plus eloigne d'un polyedre pouvent faire 68 000 face .. non merci .surtout si je dois le refaire our des polygone de 32 000 face 2 fois de suite etc (c recursif alors forcement ... )

Mais merci d'avoir pris du temps pour y reflechir et d'ecrire cette réponse ...
d'autre suggestion ?

-={[ Zeroc00l ]}=-
Messages postés
4172
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
9 juin 2006
15
0
Merci
Ben je suis un peu à cours là !!! Mais je réflechis àune autre solution ...

Christophe R.