Benennen von diesem Algorithmus: Vergleichen und Interpolationspunkten?

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

  •  19-09-2019
  •  | 
  •  

Frage

meine Frage vielleicht ein wenig seltsam sein. Ich habe „entwickelt“ einen Algorithmus und weiß nicht, ob es ein ähnlicher Algorithmus ist bereits da draußen.

Die Situation: Ich habe eine Spur für Spur Punkte (2D) definiert bekam. Die Trackpunkte repräsentieren Kurven zum Beispiel. Zwischen den Trackpunkte gibt es nur gerade Linien. Jetzt bin ich eine Reihe von Koordinaten in diesem 2D-Raum gegeben. I berechnen den Abstand von dem ersten Bahnpunkt in die neuen Koordinaten und den Abstand für das Intervall für die ersten beiden Spurpunkte. Wenn der Abstand zu den gemessenen Koordinaten kürzer als der Abstand vom ersten zum zweiten Bahnpunkt ist, gehe ich davon aus, daß dieser Punkt liegt zwischen diesem Intervall. Ich mache dann eine lineare Interpolation, dass auf. Wenn es größer, ich werde mit dem nächsten Intervall überprüfen.

Es ist also im Grunde Intervall Entfernungen zu nehmen und zu versuchen, sie dort zu passen. Ich versuche, ein Objekt zu verfolgen etwa entlang dieser Strecke bewegen.

Wer kennt das nicht an jemanden? Kann jemand mit einem Vorschlag für einen similiar bestehenden Algorithmus kommen?

EDIT: Von dem, was ich bisher gesagt habe, möchte ich klarstellen, dass eine Position nicht zugeordnet ist mehrfach Punkte zu verfolgen. Betrachten wir die feinen ASCII Zeichnung Jonathan gemacht:

Die X-Position wird festgestellt, innerhalb des Segments 1 und 2 (S12) sein. Nun ist die nächste Position Y, die nicht in der Nähe zu betrachten, ist genug, um auf S12 zu sein. Ich werde zu S23 weitergehen, und prüfen Sie, ob es in.

Wenn es in ist, ich will S12 nicht für einen anderen Wert wird überprüft, da fand ich ein in dem nächsten Segment bereits. Der Algorithmus „sieht nicht zurück“.

Aber wenn es von dort nicht das richtigen Segment finden, weil es von dem ersten Segment zu weit weg sein happenend, aber immer noch weiter weg von jedem anderen Segment sowieso, werde ich den Wert und die nächste Position sinken suchte wieder in S12 wieder werden.

Die Schleife bleibt nach wie vor ein Problem. Man betrachte ich Y für S23 und dann überspringen zwei oder drei Positionen (wie sie zu weit weg sind), könnte ich den Überblick verlieren. Ich konnte eine Position in S34 bestimmen, wo es in S56 wird bereits würde.

Vielleicht kann ich mit einer gewissen Durchschnittsgeschwindigkeit kommen bis Vage in sagen, was Segment sollte es sein.

Es scheint, desto größer die Segmente sind, desto größer ist die Chance, eine richtige Entscheidung zu treffen.

War es hilfreich?

Lösung

Was ich über den Algorithmus Sie beschrieben haben, ist, dass es ‚gierig‘ und könnte das ‚falsche‘ Spursegment (oder zumindest ein Spursegment, das nicht in der Nähe von dem Punkt ist) wählen.

Zeit ASCII-Art an die Grenzen zu schieben. Man betrachte den folgenden Pfad (Zahlen stellen die Reihenfolge in der Liste der Spurpunkte), und die Koordinate X (und später, Y). 

    1-------------2
                  |
                  |    Y
                X |
            5-----+-----6
            |     |
            |     |
            4-----3

Wie sollen wir Ihre Beschreibung interpretieren?

  

[C] alculate den Abstand von dem ersten Bahnpunkt in die neuen Koordinaten und den Abstand für das Intervall für die ersten beiden Spurpunkte. Wenn der Abstand zu den gemessenen Koordinaten kürzer als der Abstand vom ersten zum zweiten Bahnpunkt ist, [annehmen], dass dieser Punkt zwischen diesem Intervall liegt; [...] [i] f es ist größer, [...] mit dem nächsten Intervall überprüfen.

Ich denke, der erste Satz bedeutet:

  • Berechnen Sie den Abstand von TP1 (Spur Punkt 1) bis TP2 - nennen es D12
    • .
  • Berechnen Sie den Abstand von TP1 bis X (nennen wir es D1X) und von TP2 bis X (es nennen D2X).

Der schwierige Teil ist die Interpretation des bedingten Satzes.

Mein Eindruck ist, dass, wenn entweder D1X oder D2X weniger als D12 ist, dann wird X sein auf (oder am nächsten zu) ausgegangen werden, das Spursegment TP1 bis TP2 (nennen wir es Segment S12).

an der Position X in dem Diagramm der Suche ist es mäßig klar, dass sowohl D1X und D2X sind kleiner als D12, so meine Interpretation des Algorithmus X als im Zusammenhang mit S12 interpretieren würde, doch X ist deutlich näher an S23 oder S56, als es zu S12 ist (aber die verworfen werden, ohne auch nur in Betracht gezogen werden).

Habe ich etwas über Ihren Algorithmus falsch verstanden?

Das Nachdenken über es ein wenig: was ich Ihren Algorithmus interpretiert, ist, dass, wenn der Punkt X liegt entweder innerhalb des Kreises von D12 Radius an TP1 oder der Kreis mit dem Radius D12 zentriert bei TP2 zentriert, dann sind Sie assoziieren X mit S12. Wenn wir jedoch auch Punkt Y betrachten, der Algorithmus Ich schlage vor, Sie verwenden auch mit S12 verbinden würde.

Wenn der Algorithmus verfeinert MAX(D1Y, D2Y) < D12 zu sagen, dann ist es nicht Y betrachten zu S12 in Beziehung steht. Jedoch ist X wahrscheinlich noch in Betracht gezogen S12 werden im Zusammenhang eher als S23 oder S56.

Andere Tipps

Der erste Teil dieses Algorithmus erinnert mich durch einen diskretisierten Raum zu bewegen. Ein Beispiel für einen solchen Raum repräsentieren, sind die Z Ordnung raumfüllende Kurve. Ich habe diese Technik verwendet, um zu repräsentieren eine Quadtree , die Datenstruktur für eine adaptive Verfeinerung Netz Code ich habe einmal auf und verwendet einen Algorithmus sehr wie die, die Sie beschreiben, um das Raster zu durchqueren und bestimmen Abstände zwischen den Teilchen.

Die Ähnlichkeit kann nicht ohne weiteres ersichtlich sein. Da es Ihnen nur um Intervall Standorte sind, behandeln Sie effektiv alle Punkte auf dem Intervall, wie in diesem Schritt äquivalent. Dies ist das gleiche wie einen Raum zu wählen, die nur diskretisierten Punkte haben -. Sie sind effektiv ‚schnappen‘, um Ihre Punkte zu einem Raster

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top