Martok - Do 03.07.08 19:17
Titel: Pfad verfolgen

---

Hallo,

Die Frage hat eigentlich nichts mit Delphi zu tun, das ganze wird nicht mal in Delphi implementiert werden, aber das ist ja erstmal egal.

Also, ich habe einen Pfad in 3 Dimensionen gegeben. Die einzelnen Wegpunkte sind unterschiedlich weit entfernt. Der Pfad ist geschlossen, aber das spielt erstmal keine Rolle, da ich ja kurzerhand nen Anfang festlegen kann.

Nun möchte ich diesen verfolgen können, dazu müsste ich ja wissen wo ein Bestimmter Punkt liegt.

Eingabe ist also z.b. "34%", und ich möchte dann den Punkt haben der bei 34% der gesamten Wegstrecke liegt. Welche Möglichkeiten außer des durchprobierens (aufaddieren der Längen und Interpolation des letzten Stücks) hätte ich hier?

Wichtig ist, dass ich weder mit Speicher noch mit Rechenleistung um mich werfen kann. Viel Vorberechnen geht also nicht wirklich.

Oder gibts nichts besseres? Wenn nicht, hätte ich noch ne Notlösung, wär also kein Weltuntergang.

Danke,
Sebastian

BenBE - Do 03.07.08 22:17

---

Du kannst über einen Baum oder ähnliche Strukturen um mit ein wenig Vorberechnung die iterativen Suchen des korrekten Teilabschnittes zu beschleunigen; lohnt sich aber nur bei großen Pfaden ...

Martok - Fr 04.07.08 00:03

---

Irgendwie wusste ich, dass wenn eine Antwort kommt, die dann von dir ist xD

So groß wird das Ding nicht, vielleicht 50 Punkte wenn ich ihn sehr detailliert mache. Eher weniger.
Das Problem ist ja, dass ich öfter da drüber muss. Deswegen hab ich mal vermutet dass ein wenig optimieren nicht schaden kann.

Ich habe aber grade festgestellt, dass ich zu jedem Punkt ja speichern könnte, bei wie viel Prozent er liegt (bzw. wie lang die Strecke bis dahin war). Der Speicheraufwand ist ja nun nur unwesentlich, und die Sucherei reduziert sich auf ein paar Vergleiche.

BenBE - Fr 04.07.08 09:38

---

Jup. Das ist eine BErechnung, die dann locker mit abfällt beim Initialisieren. Und dann die Knoten in nen Binärbaum (oder balancierten Baum) einordnen, aber das wäre halt wie gesagt bei wenigen Punkten etwas OVerkill.