Étant donné un grand ensemble (dizaines de milliers de millions) de points désordonnés représentés sous forme de vecteurs cartésiens 3D, quel est un bon algorithme pour faire une grille carrée régulière (d'espacement définie par l'utilisateur) qui renferme tous les points? Quelques contraintes:
Pour illustrer en 2D, compte tenu de cet ensemble de points:
Pour certains espaces de grille x, une valeur de retour possible de l'algorithme serait les coordonnées de ces points rouges (lignes pointillées à des fins d'illustration uniquement):
et pour l'espacement de la grille X / 2, une valeur de retour possible de l'algorithme serait les coordonnées de ces points rouges (lignes pointillées à des fins d'illustration uniquement):
Pour tous ceux qui sont intéressés, les points désordonnés que je travaille sont les coordonnées atomiques de grandes molécules de protéines, comme ce que vous pouvez sortir d'un fichier .PDB.
Python est préféré pour des solutions, bien que la pseudocode soit aussi bonne.
Edit: Je pense que ma première description de ce dont j'avais besoin était peut-être un peu floue, alors j'ai ajouté des contraintes et des images afin de clarifier les choses.
6 Réponses :
Trouver une place minimale de la zone qui renferme tous les points. Subdiviser à plusieurs reprises chaque carré en 4 sous-carrés (donc aller de 1 à 4 à 16 à 64 à 64 à ...). Arrêtez-vous juste avant que l'un des carrés devienne vide. Il n'est pas difficile de prouver que la grille résultante est au plus quatre fois plus grossière que la solution optimale (perspicacité clé: un carré vide est garanti pour contenir au moins un carré de n'importe quelle grille au moins deux fois plus fin).
Probablement cette constante peut être réduite en introduisant une traduction aléatoire.
Je vous suggère de faire un arbre K-D . C'est Fast-ish, simple et facile à mettre en œuvre:
Et code Wikipedia: Vous devez le modifier légèrement, cependant, pour s'adapter à vos contraintes.
Que diriez-vous de Voronoi Diagram ? Il peut être généré dans Je ne sais pas si cela répond à votre problème, mais les diagrammes de Voronoi sont très "naruraux". Ils sont très courants dans la nature.
Exemple (de Wikipedia):
O (n log n) en utilisant Forunes Algorithm < / a>.
À quiconque pense à perpétrer une autre mise en œuvre sur le monde: les algorithmes de division et de conquérir pour Voronoi / Delaunay sont beaucoup Saner que de Fortune. Les deux ont de graves problèmes avec des entrées de point flottantes presque dégénérées.
@JIMMY: Merci - corrigé ça. C'était d'une autre question.
Parce que vous demandez une grille carrée régulière d'espacement spécifié par l'utilisateur, cela ressemble à une approche raisonnablement simple devrait fonctionner.
Commencez par traverser les données pour déterminer la coordonnée minimale et maximale de chaque dimension. Travaillez le nombre d'étapes de l'espacement spécifié par l'utilisateur requis pour couvrir la distance entre le maximum et le minimum.
passe à nouveau dans les données pour allouer chaque point à une cellule dans la grille, à l'aide d'une grille avec un point au minimum de chaque coordonnée et l'espacement spécifié (par exemple X_Cell = math.floor ((x_i-x_min) / espacement)). Utiliser un dictionnaire ou un tableau pour enregistrer le nombre de points dans chaque cellule.
Imprimez maintenant les coordonnées des cellules avec au moins un point d'entre eux.
Vous avez une certaine liberté que je ne l'ai pas essayé d'optimiser: à moins que la distance entre coordonnées minimum et maximum est un multiple exact de l'espacement de la grille, il y aura des slops qui vous permet de faire glisser la grille autour et encore Demandez-vous que tous les points: au moment où la grille commence à la position du point le plus bas, mais cela se termine probablement avant les points les plus élevés, vous avez donc de la place pour le déplacer un peu dans chaque dimension. Comme vous le faites, certains points se déplaceront de la cellule à la cellule et le nombre de cellules occupées changera.
Si vous ne considérez que des mouvements d'une dimension à la fois, vous pouvez déterminer ce qui se passera raisonnablement efficacement. Travaillez la distance dans cette dimension entre chaque point et la coordonnée maximale dans cette dimension de sa cellule, puis trier ces valeurs. Lorsque vous déplacez la grille vers le bas, le point de la plus petite distance de sa coordonnée maximale échangera d'abord les cellules et vous pouvez itérer à travers ces points un par un en les déplaçant dans l'ordre triché. Si vous mettez à jour les comptes de points dans les cellules comme vous le faites, vous pouvez déterminer quel changement minimise le nombre de cellules occupées.
Bien sûr, vous avez trois dimensions à craindre. Vous pouvez y travailler un à la fois jusqu'à ce que vous obteniez des réductions dans le nombre de cellules. Ceci est un minimum local, mais peut ne pas être un minimum mondial. Une façon de rechercher d'autres minima locaux est de recommencer à partir d'un point de départ choisi au hasard.
J'ai de l'expérience avec le regroupement de la grille en 2D et mis en œuvre un exemple en code C #. http://kunuk.wordpress.com/2011/09/15/ Clustering-Grid-Cluster /
Ceci peut gérer la poignée étape 1, 2 et 4. Vous devrez modifier le code et le mettre à jour sur l'espace 3D. J'espère que cela vous donne quelques idées.
Le code fonctionne dans O (m * n) où m est le nombre de grilles et n est le nombre de points.
Alors, le minimal contenant le carré serait une solution valide, car il contiendrait au moins l'un des points et tous les points seraient dedans? Je ne le pense pas.
Surtout important, quel est le but de construire la grille?
La grille devrait-elle être des carrés? Ou pourrait-il être triangulaire ou hexagonal ou rectangles ou diamants? De plus, la grille devrait-elle être uniforme, c'est-à-dire que chaque cellule de la grille est de nature identique (translation de la traduction de l'origine) de l'autre cellule de la grille?
Pouvez-vous dire comment cela doit être utilisé? Par exemple, s'il s'agit de chèques de proximité rapides, plusieurs algorithmes standard sont nombreux.
Par «grille de taille minimale», il signifie réellement «grille avec granularité cellulaire minimale». Autrement; Oui, une boîte de sélection pour l'ensemble du point de vue serait la solution optimale.
@Dand. Ce serait un endroit pour commencer :) Mais une partie de ce que je veux, c'est pouvoir spécifier arbitrairement l'espacement des points de grille. En d'autres termes, je veux être capable de modifier la densité de la grille avec une seule variable.
@Depyellow Les points de grille vont être utilisés comme sondes dans un calcul du champ électrostatique de la protéine. Est-ce que cela tombe dans "Vérifications de proximité rapides"? Je suis plus d'un physicien qu'un gars CS.
@Pengone Votre commentaire est à la fois non pertinent et inutile. Ceci est un site de questions et de réponses. Vous ne voulez pas répondre à cette question particulière, allez lire un autre fil.
@Tel: Oui, ça fait. Vous voudrez peut-être que vous souhaitiez commencer ici: en.wikipedia.org/wiki/spatial_index#SSPatial_index. Blender a déjà mentionné l'arbre de la K-D, mais vous devez connaître les autres choix.