Discussion :

[mhtrinh]

Bonjour,

Voici mon probleme :
- 2 ensembles de points dans l'espaces : environs 4000 points par ensemble(c'est en fait aux atoms dans un fichier pdb, pour ceux qui connaissent)
- ces 2 ensembles subissent des transformations (translations et rotations) : 2000 transformations chacuns
- Pour chaque transformations, je cherche quelle est la distance minimal entre ces 2 ensembles. Cad, quelle la distance minimale entre 2 points les plus proches appartenant à ces 2 ensembles (probleme originale : trouver les clashes stérics ...)

Est-ce que vous avez une petite idee ? Surtout des mot cles d'algorithme "interessant" pour que je google :-)

[ToTo13]

Bonsoir,

je n'ai pas d'algorithme particulier sous la main.
- Je commencerai par calculer les enveloppes convexes de chacun des ensembles. Cela réduira le nombre de points candidats et ne changera pas pour les transformations classiques (translation, rotation et homothétie).
- Ensuite je trierai les points en fonctions de leurs distances par rapport au plan orhtogonal à la droite reliant les barycentres des deux ensembles. Ca te donnera un ordre de départ pour faire une recherche.

[Graffito]

Si le problème est d'optimiser,

• Diviser l'espace en "petits" cubes de coté C,
• Identifier pour chaque ensemble les cubes non vides (avec des points)
• trouver les 2 cubes non vides (1 de chaque ensemble) CubeX et CubeY avec la plus petite distance Dmin entre leur 2 volumes
• puis éliminer les couples de cubes (1 de chaque ensemble) dont la distance D est supérieure à Dmin+2*SQRT(3*C) (majorant du pire des cas entre CubeX et cubeY).
• traiter uniquement les couples de cubes retenus avec la méthode "bourrine" vu qu'on a déjà optimisé ou alors avec la méthode de toto13.

[edfed]

exact, en isolant les points des enveloppes des nuages (convexe ou non) pendant les translations et rotations, on peu apres faire une selection des points dirigés vers l'autre nuage
puis en calculant le carré des distances entre les points les plus proches, on sait quels sont les plus proches voisins.
le carré de la distance est plus facile a obtenir et plus rapide.