3D Math - Nur Positionen innerhalb einer bestimmten Anzahl von Yards halten

Question

Ich versuche aus einer großen Reihe von Positionen zu ermitteln, wie ich meine Liste deutlich eingrenzen kann.

Im Moment habe ich ungefähr 3000 Positionen (x, y, z) und möchte grundsätzlich die Positionen halten, die am weitesten voneinander entfernt sind (ich muss nicht 100 Positionen halten, die alle innerhalb von 2 Yard liegen) Radius voneinander).

Abgesehen von einer Brute-Force-Methode und buchstäblich 3000^2 Vergleiche, hat jemand irgendwelche Ideen, wie ich diese Liste weiter eingrenzen kann?

Ich bin ein wenig verwirrt darüber, wie ich das aus einer mathematischen Perspektive nähern sollte.

Answer 1

Nun, ich kann mich nicht an den Namen für diesen Algorithmus erinnern, aber ich werde Ihnen eine lustige Technik für den Umgang damit sagen. Ich nehme an, dass es in einer 3D-Umgebung eine halb-zufällige Streuung von Punkten gibt.

Einfache Version: Divide and Conquer

1. Teilen Sie Ihren Raum in ein 3D-Raster von Würfeln. Jeder Würfel wird X Yards auf jeder Seite sein.
2. Deklarieren Sie ein mehrdimensionales Array [x, y, z] so, dass Sie ein Element für jeden Cube in Ihrem Raster haben.
3. Jedes Element des Arrays sollte entweder ein Scheitelpunkt oder ein Verweis auf eine Scheitelpunktstruktur (x, y, z) sein, und jeder sollte standardmäßig NULL sein.
4. Iterieren Sie durch jeden Scheitelpunkt in Ihrem Dataset, bestimmen Sie, auf welchen Würfel der Scheitelpunkt fällt in.
   • Wie? Nun, Sie könnten annehmen, dass der Scheitelpunkt (5.5, 8.2, 9.1) in MyCubes [5.8.9] liegt, vorausgesetzt, dass X (Cube-Side-Length) die Größe 1 hat. Hinweis: Ich habe nur die Dezimalzahlen/Gleitkommazahlen abgeschnitten Bestimmen Sie, welcher Würfel.
5. Überprüfen Sie, ob dieser relevante Würfel bereits von einem Eckpunkt belegt ist. Check: Wenn MyCubes [5,8,9] == NULL dann (injizieren meine Vertex) andere (nichts tun, werfen Sie es heraus vor Ort genommen, Kumpel!)

Lassen Sie uns etwas Speicher sparen

Dadurch erhalten Sie einen schön vereinfachten Datensatz in einem Durchgang, jedoch auf Kosten einer potenziell großen Speichermenge.

Also, wie machst du es, ohne zu viel Speicher zu verwenden?

Ich würde eine Hashtabelle verwenden, so dass mein Schlüssel die Gitter-Würfel-Koordinate (5,8,9) in meinem obigen Beispiel ist.

If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...) 

Nun haben Sie eine One-Pass-Lösung mit minimalem Speicherverbrauch (kein gigantisches Array mit einer potenziell großen Anzahl von leeren Würfel schneiden. Was sind die Kosten? Nun, die Programmierzeit Ihre Struktur/Klasse einrichten so dass Sie die .contains Aktion in einem HashTable ausführen kann (oder Ihre Sprache-Äquivalent)

Hey, sind klobig meine Ergebnisse!

das ist richtig, weil wir das erste Ergebnis nahm die jeden Würfel passen .Im Durchschnitt haben wir eine X-Trennung zwischen den Scheitelpunkten erreicht, aber wie Sie jetzt feststellen können, sind einige Scheitelpunkte immer noch nahe beieinander (an den Kanten der Würfel).

Also, wie gehen wir damit um? Nun, zurück zur Array-Methode (speicherintensiv!).

statt nur zu prüfen, ob sich ein Scheitelpunkt bereits im Cube-in-Frage, auch diese andere Prüfung durchführen:

If Not ThisCubeIsTaken() 
    For each SurroundingCube 
     If not Is_Your_Vertex_Sufficiently_Far_Away_From_Me() 
     exit_loop_and_outer_if_statement() 
     end if 
    Next 
    //Ok, we got here, we can add the vertex to the current cube because the cube is not only available, but the neighbors are far enough away from me 
End If 

Ich glaube, Sie wahrscheinlich die Schönheit dieses sehen können, wie es ist Wenn Sie ein 3D-Array haben, ist es sehr einfach, benachbarte Würfel zu erhalten.

Wenn Sie eine solche Glättung durchführen, können Sie wahrscheinlich eine Richtlinie "Do not add if with 0.25X" erzwingen. Sie müssen nicht zu streng sein, um einen spürbaren Glättungseffekt zu erzielen.

Immer noch zu klobig, ich will es

In dieser Variante glätten, werden wir die Aktion der Qualifikation für ändern, ob ein Vertex Wohnsitz in einem Würfel zu nehmen erlaubt ist.

If TheCube is empty OR if ThisVertex is closer to the center of TheCube than the Cube's current vertex 
    InsertVertex (overwrite any existing vertex in the cube 
End If 

Hinweis, wir müssen keine Nachbarerkennung für diesen durchführen. Wir optimieren nur zur Mitte jedes Würfels.

Wenn Sie möchten, können Sie diese Variante mit der vorherigen Variante zusammenführen.

Cheat-Modus

Für manche Menschen in dieser Situation können Sie einfach eine 10% zufällige Auswahl Ihres Datensatz an, und das wird eine ausreichend gute Vereinfachung sein. Es wird jedoch sehr eng mit einigen Punkten sehr eng zusammen sein. Auf der hellen Seite dauert es ein paar Minuten max. Ich empfehle es nicht, es sei denn Sie prototypieren.