spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi Leute,

gestern hatte ich schon einmal versucht ein Thema zu eröffnen, aber leider alles gelöscht-.- Deshalb heute ein neuer Versuch, in dem ich erstmal alle Randinfos weglasse und mich versuche auf das Wesentliche zu konzentrieren.

Ich habe ein komplett unsortierte Liste aus Punkten, die gemessene Punkte einer Art "Tunnelwand" repräsentieren. Ich möchte nun aus diesen Punkten diese Wand rekonstruieren.
(Die Wand ist überings in echt komplett glatt, Ausschläge sind meist Messfehlern und Ungenauigkeiten zu verschulden.)
Das funktioniert auch alles soweit sehr gut (Sortieralgortihmus, anschließende Glättung, usw...). Allerdings kommt es beim manchen Messungen vor, dass mein Algorithmus fehlt schlägt, da es extreme Ausschläge gibt. Ein Beispielbild habe ich mal angehängt. Die roten Punkte sind die gemessene Punkte und die Linie soll ungefähr das erwünschte Ergebnis darstellen.
Mein Sortieralgorithmus ist denkbar simpel: Ich fange mit dem ersten Punkt an (der bekannt ist!) und gehe von diesem zum nähsten unbesuchten Punkt. Von diesem wird wieder der nähste unbesuchte Punkt gesucht usw. Offensichtlich ist dies aber nicht die beste Lösung, da ich so teilweise falsche Konstrukte bekomme. Meine anschließende Glättung kann viel davon ausmerzen, aber leider nicht alles. So zum Beispiel der "Zacken" links in der Kurve. Dies sind definitiv fehlerhafte Messwerte. Wie ich diese aber entfernen kann ist mir unklar. Manuelle Entfernung zur Optimierung des Algortihmus ist für mich nur eine unbefriedigende Notlösung..

Hat jemand von euch mit einem ähnlichen Problem zu tun und hat wertvolle Tipps für mich bzgl. der Sortierung, Filterung solcher Punkte?
Vielen Dank im Voraus

Hey Jonathan,

danke für deine Gedanken und Tipps!
Mein Beispielanhang ist vielleicht etwas doof geworden, denn tatsächlich habe ich nicht EINE Kurve, sondern wirklich einen eventuell viel größeren Verlauf. Man kann sich das ganze als Kanalsystem vorstellen, in dem es gerade Rohre gibt und Bögen (90° links oder rechts) und nach Baukastenprinzip aufgebaut ist. Deshalb ist es recht schwierig eine komplette Wand durch eine Bezierkurve oder Ähnliches darzustellen...
Mean-Shift klingt tatsächlich interessant, vielleicht kann ich damit etwas anfangen. Ob es wirklich so funktioniert, wie ich es gerne hätte, kann ich aber erst nach ausreichendem Testen sagen. Danke für die Anregung!
Grüße

Danke euch allen für euren tollen Vorschläge!

Ich habe jetzt einiges ausprobiert und verwende folgendes, was bisher echt ganz gut und zuverlässig funktioniert:
RANSAC war echt ein guter Tipp (wobei die Idee dahinter ja denkbar logisch ist). Durch mein sehr hohe Punktezahl und aufwändigen Algorithmus zur Erstellung des Modells, ist mir dieses Verfahren im Ganzen zu speicher- und vor allem zeitintensiv. Dahinter verwende ich gerade nur das (etwas abgeänderte) Grundprinzip mit den Grenzwerten bzgl. des Abstandes zur Kurve.
Auf der anderen Seite muss ich aufpassen, dass ich nicht zu viele Ausreisser "wegschmeisse", denn dadurch das die Messung generell nicht 100% genau ist, ist so gut wie jeder Punkt wertvoll für das Modell. Nachdem ich die Punkte gefiltert habe und die Linie ziehe, mache ich jetzt also folgendes:
Mein Algorithmus dazu (siehe 1. Post) nimmt nur den nächsten Punkt, wenn dessen Winkel maximal x Grad Abstand zum Durchschnittswinkel der letzten n Punkte hat. (x ist am besten immer <= 90°, d.h. nächster Punkt muss immer mindestens auf gleicher Höhe liegen, nie aber hinter dem lertzten Punkt). Dadurch stelle ich sicher, dass auch Messreihen erfolgreich durchlaufen, die grobe Ausreisser haben un einfach durch die "Naivität" des Algorithmus falsche Verläufen nahmen. Jetzt ist das Problem allerdings, das mit der Methode viele Punkte (die keine Ausreisser sind) durch das Raster fallen, obwohl sie eventuell die Genauigkeit des Modells noch verbessern könnten. Dies hat mir ganz gut geholfen: Ich nehme alle diese Punkte, die noch nicht einer Wand zugeordnet wurden und suche ihnen den nächsten Punkt im Modell. Ist dieser Abstand <= x cm, dann sehe ich den Punkt als "einbringungswert" und füge ihn in die Liste neben dem nächsten Punkt ein. Dadurch wird eine vorher schon recht gerade Linie zwar etwas "krieselig", liefert aber im Endeffekt das realitätsnahere Ergebnis, da ich eh noch auf verschiedenste Arten die fertige Linie/Modell glätte und postprocesse.
Ich habe mal ein Bild angehängt, wo ich zeige, wie das Ganze jetzt an einem Beispiel aussieht.
Oben aus Vogelperspektive und unten in 3D.

Liebe Grüße