algorithme de partitionnement Espace

StackOverflow https://stackoverflow.com/questions/2959564

  •  23-10-2019
  •  | 
  •  

Question

J'ai un ensemble de points qui sont contenus dans le rectangle. Je voudrais diviser les rectangles en sous-rectangles selon la densité de points (ce qui donne un certain nombre de sous-rectangles ou densité désirée, selon le plus facile).

Le partitionnement ne doit pas être exacte (presque toute approximation meilleure que la grille régulière ferait), mais l'algorithme doit faire face au grand nombre de points - env. 200 millions. Le nombre désiré de sous-rectangles est toutefois nettement plus faible (environ 1000).

Quelqu'un sait-il tout algorithme qui peut me aider avec cette tâche particulière?

Était-ce utile?

La solution

Juste pour comprendre le problème. Ce qui suit est brut et de mauvais résultats, mais je veux savoir si le résultat est ce que vous voulez>

Assomption> Nombre de rectangles est même
Assomption> Point de distribution est nettement en 2D (aucune grande accumulation dans une ligne)

Procédure>
BiSect n / 2 fois dans l'un des axes, les boucles d'une extrémité à l'autre de chaque rectangle de comptage précédemment déterminé « passé » points et stocker le nombre de points spécifiés à chaque itération. Une fois compté, bisect la sélection de rectangle par les points comptés dans chaque boucle.

Est-ce ce que vous voulez atteindre?

Autres conseils

Vous êtes après une norme Kd-arbre ou arbre de partitionnement de l'espace binaire, je pense. (Vous pouvez chercher sur Wikipedia.)

Puisque vous avez un grand nombre de points, vous voudrez peut-être seulement environ partitionner les premiers niveaux. Dans ce cas, vous devriez prendre un échantillon aléatoire de vos points de 200M - peut-être 200k d'entre eux - et diviser l'ensemble des données au milieu de la sous-échantillon (le long de l'axe selon est plus). Si vous choisissez en fait des points au hasard, la probabilité que vous risquez de manquer un grand groupe de points qui ont besoin d'être subdivisé sera approximativement égale à zéro.

Maintenant, vous avez deux problèmes d'environ 100M points chacun. Diviser chaque long de l'axe plus. Répétez jusqu'à ce que vous arrêtez de prendre et sous-échantillons fendus le long de l'ensemble de données. Après dix itérations de largeur d'abord vous faire.

Si vous avez un autre problème - vous devez fournir Graduations le long de la X et Y et l'axe de remplissage dans une grille le long de ceux que vous le pouvez, plutôt que d'avoir la décomposition irrégulière d'un Kd-tree - prenez votre sous-échantillon de points et de trouver le 0/32, 1/32, ..., 32/32 centiles le long de chaque axe. Dessiner il vos lignes de la grille, puis remplissez la grille résultante 1024 éléments avec vos points.

Je pense que je commencerai par ce qui suit, qui est proche de ce que @belisarius déjà proposé. Si vous avez des exigences supplémentaires, telles que des rectangles préférant « presque carré » à « long et mince » ceux que vous aurez besoin de modifier cette approche naïve. Je suppose que, par souci de simplicité, que les points sont distribués de façon aléatoire environ.

  1. Divisez votre rectangle initial en 2 avec une ligne parallèle au petit côté du rectangle et en cours d'exécution exactement par le point milieu.
  2. Comptez le nombre de points dans les deux demi-rectangles. Si elles sont égales (assez) puis passez à l'étape 4. Sinon, passez à l'étape 3.
  3. Sur la base de la répartition des points entre les demi-rectangles, déplacer la ligne même des choses à nouveau. Donc, si, par hasard, la première coupe divisée points 1/3, 2/3, déplacer la mi-chemin de la ligne dans la moitié lourde du rectangle. Passez à l'étape 2. (Veillez à ne pas se faire piéger ici, déplacer la ligne dans les étapes toujours décroissante dans un sens, puis dans l'autre.)
  4. Maintenant, passer chacun des demi-rectangles dans un appel récursif à la fonction, à l'étape 1.

J'espère que les contours assez bien la proposition. Il a ses limites: elle produira un certain nombre de rectangles égaux à une puissance de 2, donc l'ajuster si ce n'est pas assez bon. Je l'ai Formulé récursivement, mais il est idéal pour parallélisation. Chaque split crée deux tâches, dont chacun se divise un rectangle et crée deux tâches.

Si vous faites peut-être vous ne pouviez pas comme cette approche, commencer par une grille régulière avec un multiple (10-100 peut-être) du nombre de rectangles que vous voulez. Comptez le nombre de points dans chacun de ces petits rectangles. Puis commencer à coller les petits rectangles ensemble jusqu'à ce que le rectangle moins minuscule contient (environ) le bon nombre de points. Ou, si elle répond à vos besoins assez bien, vous pouvez l'utiliser comme une méthode de discrétisation et l'intégrer à ma première approche, mais seulement placer les lignes de coupe le long des limites des rectangles minuscules. Ce serait probablement beaucoup plus rapide que vous souhaitez ne devez compter les points dans chaque petit rectangle une fois.

Je n'ai pas vraiment réfléchi à la durée de l'une de ces; J'ai une préférence pour la première approche « cos je fais un montant juste de la programmation parallèle et ont des tas de processeurs.

Bonne question.

Je pense que la zone que vous devez étudier est « géométrie algorithmique » et le problème « k-partitionnement ». Il y a un lien qui pourrait vous aider à démarrer

Il se peut que le problème lui-même est NP-dur qui signifie un bon algorithme d'approximation est le meilleur que vous allez obtenir.

k-moyennes ou a

C'est ressemble analyse Cluster .

QuadTree travail?

A quadtree est une structure de données d'arbre, dans lequel chaque noeud interne a exactement quatre enfants. Quadtrees sont le plus souvent utilisés pour partitionner un espace à deux dimensions en subdivisant récursivement en quatre quarts de cercle ou régions. Les régions peuvent être carrée ou rectangulaire, ou peuvent avoir des formes arbitraires. Cette structure de données a été nommé par quadtree Raphael Finkel et J.L. Bentley en 1974. Une répartition similaire est également connu sous le nom de Q-arbre. Toutes les formes de Quadtrees partagent certaines caractéristiques communes:

  • Ils se décomposent dans l'espace des cellules adaptables
  • Chaque cellule (ou un seau) a une capacité maximale. Lorsque la capacité maximale est atteinte, le grand écart de seau
  • Le répertoire des arbres suit la décomposition spatiale du quadtree
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top