Bestellen einer Reihe nicht organisierter Punkte entlang einer Kurve

Ich habe eine Reihe von 3D-Punkten (die ich aus einer Bibliothek wiederherstelle, die die Tessellation eines Festkörpers ausführt), die zu einer Kurve (dh einer Kante des Festkörpers) gehören. Das bedeutet, dass die Kurve sicher an jedem dieser Punkte vorbeiführt.

Trotzdem ist die Punktmenge ungeordnet, so dass ich sie sortieren muss, um diese Kurve korrekt zeichnen zu können.

Gibt es einen bekannten Ansatz für diese Art von Problem?

Einige zusätzliche Informationen:

Die Kurven sind im Allgemeinen parametrisch (Splines / Bezier, Kreisscheiben ..).
Die Punkte werden als Gleitkommakoordinaten angegeben.
Die Punkte sind sehr dicht gepackt (aber sie können so dicht sein, wie ich es möchte). Um Ihnen eine Vorstellung zu geben, zitiere ich für eine Kurve, die 19 Einheiten in x, 10 Einheiten in x und 5 Einheiten in z einnimmt, eine Folge von Punkten in einem Kurvensegment: (20.7622, 25.8676, 0) (20.6573, 25.856, 0) (20,5529, 25,8444, 0) (20,4489, 25,8329, 0) (20,3454, 25,8213, 0)

geometry mesh curve andrea.al
quelle

Selbst wenn wir die Reihenfolge kennen, gibt es bis zu einer unendlichen Anzahl von Kurven, die durch die Punkte passen. Selbst wenn wir zusätzliche Einschränkungen hinzufügen, sind die offenen Enden problematisch, da ihre tangentiale Ausrichtung beliebig sein kann. Ein Bild hier

joojaa

@joojaa Ja, du hast recht. Da die Packung der Punkte jedoch sehr dicht ist, erwarte ich nicht, dass sie genau ist. Wenn ich die richtige Reihenfolge habe, wollte ich die Punktfolge als Polylinie verbinden.

andrea.al

Kennen Sie in dem Code, der die Punkte ordnen muss, überhaupt die parametrische Form der Kurve? (Wenn nicht, werde ich meine erste Antwort löschen, da Sie die parametrische Form kennen müssen.)

Martin Ender

@ MartinBüttner Ja, ich habe Zugriff auf die parametrische Form der Kurve, falls erforderlich.

andrea.al

Bitte zeigen Sie einen typischen Punktesatz!

Yves Daoust

Antworten:

Sie haben ein Problem, das als Kurvenrekonstruktion aus nicht organisierten Punkten bezeichnet wird . Jetzt, da Sie wissen, wonach Sie suchen müssen, finden Sie verschiedene Methoden, wie z. B. die Kruste, die NN-Kruste usw. Hier einige Links:

Das Applet zur Rekonstruktion der Krustenkurve
Kurvenrekonstruktion von Tamal Dey
Kurven- und Oberflächenrekonstruktion: Algorithmen mit mathematischer Analyse , Buch von Tamal K. Dey, Cambridge University Press, 2006

Da es sich um Kurven handelt und die Stichproben dicht sind, empfehle ich Ihnen, einen euklidischen minimalen Spannbaum zu berechnen.

lhf
quelle

Nach einigen Klarstellungen gibt es wahrscheinlich einen viel besseren Ansatz, bei dem nicht einmal die parametrische Form der Kurve bekannt sein muss und der möglicherweise problematische numerische Minimierungsschritt vermieden wird.

Wenn sich die Kurve nicht schneidet und die Punkte auf der Kurve ausreichend dicht gepackt sind (und damit meine ich, dass sie näher sein müssen als zwei beliebige Punkte auf der Kurve, die nicht zum selben Segment gehören, z. B. durch die Kurvenumhüllung um sich selbst herum), dann können Sie leicht den vorherigen und nächsten Punkt zu jeder Probe bestimmen:

$O(n \log n)$
Sie müssen eine spezielle Behandlung für die Endpunkte durchführen. Ihre beiden nächsten Nachbarn sind die nächsten zwei Punkte entlang der Kurve anstelle von einem auf jeder Seite. Sie können diese entweder heuristisch erkennen, wenn sich das Verhältnis der Abstände zu den beiden Nachbarn um mehr als einen Schwellenwert unterscheidet (1,5 hängt beispielsweise von der Glätte Ihrer Kurve und der Dichte der Punkte ab). Oder Sie können die Daten Ihres nächsten Nachbarn als Diagramm behandeln, in dem Sie feststellen, dass die beiden Nachbarn der Endpunkte aufeinander zeigen (was an keiner anderen Stelle im Diagramm vorkommen sollte).
Jetzt können Sie einfach einen Endpunkt auswählen und entlang der nächsten Nachbarn gehen (immer den auswählen, von dem Sie nicht angekommen sind), um die Punkte entlang der Kurve zu durchqueren.

$\theta$

Martin Ender
quelle

$(X,Y,Z)$ $(x(t), y(t), z(t))$

(X. - - x (t))^{2} + (Y. - - y (t))^{2} + (Z. - - z (t))^{2}

$(X-x(t))^2+(Y-y(t))^2+(Z-z(t))^2$

$t$

$t$ $t$ $t$

Martin Ender
quelle