Space partitioning-Algorithmus

Question

Ich habe eine Reihe von Punkten, die sich innerhalb des Rechtecks.Ich möchte teilen Sie die Rechtecke in subrectangles basierend auf Punkt-Dichte (die eine Reihe von subrectangles oder die gewünschte Dichte, je nachdem, was am einfachsten ist).

Die Partitionierung muss nicht exakt sein (fast jede Annäherung besser als die regulären Gitter tun würde), aber der Algorithmus hat der Umgang mit der großen Zahl von Punkten, - ca.200 Millionen.Die gewünschte Anzahl von subrectangles ist jedoch deutlich niedriger (um 1000).

Weiß jemand, jeder Algorithmus, die können mir helfen mit diese Aufgabe?

Answer 1

Nur um das Problem zu verstehen. Das Folgende ist grob und funktioniert schlecht, aber ich möchte wissen, ob das Ergebnis das ist, was Sie wollen>

Annahme> Anzahl der Rechtecke ist gleichmäßig
Annahme> Punktverteilung ist deutlich 2D (keine große Akkumulation in einer Linie)

Verfahren>
Halbier N/2 -mal in beiden Achsen, schaufelt von einem Ende zum anderen von jedem zuvor bestimmten Rechteckzählpunkten "übergeben" Punkten und speichern die Anzahl der übergebenen Punkte bei jeder Iteration. Sobald es gezählt wurde, halte das Rechteck, das nach den Punkten in jeder Schleife ausgewählt wird.

Möchten Sie das erreichen?

Answer 2

Ich denke, ich denke, ich denke, ich denke, ich denke. (Sie können es auf Wikipedia nachschlagen.)

Da Sie sehr viele Punkte haben, möchten Sie möglicherweise nur ungefähr die ersten Stufen partitionieren. In diesem Fall sollten Sie eine zufällige Stichprobe Ihrer 200-m-Punkte-vielleicht 200.000 von ihnen-nutzen und den vollständigen Datensatz im Mittelpunkt der Teilstichprobe teilen (entlang der Achse ist länger). Wenn Sie zufällig die Punkte auswählen, ist die Wahrscheinlichkeit, dass Sie einen riesigen Punkt von Punkten verpassen, die unterteilt werden müssen, ungefähr Null.

Jetzt haben Sie zwei Probleme von jeweils etwa 100 m Punkten. Teilen Sie jeden entlang der längeren Achse. Wiederholen Sie, bis Sie nicht mehr untermachten und sich entlang des gesamten Datensatzes teilen. Nach zehn Breiten-First-Iterationen werden Sie fertig sein.

Wenn Sie ein anderes Problem haben, müssen Sie Zeckenspuren entlang der X- und Y-Achse bereitstellen und ein Netz entlang derjenigen füllen, die so gut Sie können, anstatt die unregelmäßige Zersetzung eines KD-Baumes zu haben-, nimm deine Unterprobe von Punkten und deine Teilstichprobe an Finden Sie die 0/32, 1/32, ..., 32/32 Perzentile entlang jeder Achse. Zeichnen Sie dort Ihre Netzlinien und füllen Sie das resultierende 1024-Element-Gitter mit Ihren Punkten.

Answer 3

R-tree

Answer 4

Ich denke, ich würde beginnen mit der folgenden, die in der Nähe zu dem, was @Belisar bereits vorgeschlagen.Wenn Sie haben zusätzliche Anforderungen, wie zum Beispiel lieber 'fast quadratisch' Rechtecke 'lang und Dünn' diejenigen, die Sie werden müssen ändern diese naive Ansatz.Ich nehme an, für die der Einfachheit halber, dass die Punkte sind etwa zufällig verteilt.

1. Teilen Sie Ihre ursprüngliche Rechteck in 2 mit einer Linie parallel zu der kurzen Seite des Rechtecks und läuft genau durch die Mitte.
2. Zählen Sie die Anzahl der Punkte, die sowohl in halb-als Rechtecke.Wenn Sie gleich sind (genug), dann gehen Sie zu Schritt 4.Andernfalls gehen Sie zu Schritt 3.
3. Basierend auf der Verteilung der Punkte zwischen den Hälfte-Rechtecke, die Zeile verschieben, sogar die Dinge wieder.Also, wenn, vielleicht, der erste Schnitt teilen Sie die Punkte 1/3, 2/3, verschieben Sie die Linie auf halbem Weg in die schwere Hälfte des Rechtecks.Gehen Sie zu Schritt 2.(Werden vorsichtig nicht zu bekommen, hier in der Falle, bewegen Sie die Linie, die in immer kleineren Schritten, zuerst in einer Richtung, dann die andere.)
4. Nun, pass jede halbe Rechtecke, um einen rekursiven Aufruf dieser Funktion, bei Schritt 1.

Ich hoffe, dass die Umrisse der Vorschlag gut genug.Es hat Einschränkungen:es produziert eine Reihe von Rechtecken gleich um einiges Potenz von 2, so passen Sie es, wenn, dass ist nicht gut genug.Ich habe so formuliert es rekursiv ist, aber es ist ideal für die Parallelisierung.Jeder split erstellt zwei Aufgaben, von denen jeder teilt ein Rechteck und erstellt zwei weitere Aufgaben.

Wenn Sie nicht möchten, dass der Ansatz, vielleicht könnten Sie beginnen mit einem regelmäßigen raster mit einigen mehrere (10 - 100 vielleicht) die Anzahl der Rechtecke, die Sie wollen.Die Anzahl der Punkte in jeder der kleinen Rechtecke.Starten Sie dann die Verklebung der kleinen Rechtecken zusammen, bis die weniger-kleine Rechteck enthält (ungefähr) die richtige Anzahl von Punkten.Oder, wenn es erfüllt Ihre Anforderungen gut genug, so könnten Sie als Diskretisierung Methode und integrieren es mit meinem ersten Ansatz, aber die einzige Ort, an den Schnittlinien entlang der Grenzen der kleinen Rechtecke.Dies würde wahrscheinlich sehr viel schneller, als würde man nur zum zählen der Punkte in jedem winzigen Rechteck einmal.

Ich habe nicht wirklich gedacht, über die Laufzeit der diese;Ich habe eine Vorliebe für die ehemalige Ansatz 'cos ich tun, eine faire Menge der parallelen Programmierung und haben Unmengen von Prozessoren.

Answer 5

Gute Frage.

Ich denke, der Bereich, den Sie untersuchen müssen, ist die "Computergeometrie" und das Problem "K-Partition". Es gibt einen Link, der Ihnen helfen könnte, Ihnen den Einstieg zu erleichtern hier

Sie könnten feststellen, dass das Problem selbst NP-Hard ist, was bedeutet, dass ein guter Annäherungsalgorithmus das Beste ist, was Sie bekommen werden.

Answer 6

Möchten K-Means Clustering oder ein Voronoi -Diagramm Passen Sie gut zu dem Problem, das Sie lösen möchten?

Answer 7

Das sieht aus wie Clusteranalyse.

Answer 8

Würde a Quadtree Arbeit?

Ein Quadtree ist eine Baumdatenstruktur, bei der jeder interne Knoten genau vier Kinder hat. Quadtrees werden am häufigsten verwendet, um einen zweidimensionalen Raum aufzuteilern, indem er rekursiv in vier Quadranten oder Regionen unterteilt wird. Die Regionen können quadratisch oder rechteckig sein oder willkürliche Formen haben. Diese Datenstruktur wurde 1974 von Raphael Finkel und JL Bentley als Quadtree bezeichnet. Eine ähnliche Aufteilung wird auch als Q-Tree bezeichnet. Alle Formen von Quadtrees haben einige gängige Merkmale:

• Sie zersetzen Raum in anpassungsfähige Zellen
• Jede Zelle (oder Eimer) hat eine maximale Kapazität. Wenn die maximale Kapazität erreicht ist, spaltet sich der Eimer auf
• Das Baumverzeichnis folgt der räumlichen Zerlegung des Quadtree