Konturpolygon gesucht!

SnoopyBlue

Hallo Leute,

ich suche eine Methode um das Konturpolygon einer ungeordneten, ebenen Punktmenge zu bestimmen. Die Punkte liegen in kartesischen oder polaren
Koordinaten vor.

Die Punktwolke beschreibt eine Fläche deren "Randverlauf" zu bestimmen ist.
Leider führt die "Konvexe Hülle", bzw. die Verfahren zur Bestimmung dieser
nicht zum gewünschten Ergebnis, da hier natürlich einige Bereiche der Kontur
überbrückt werden die zur eignetlichen Kontur gehören.

Gibt es ein Verfahren mit dem ich das Konturpolygon einer beliebigen Punktwolke erfassen kann ohne Randbereiche innerhalb dieser Kontur zuzulassen,
in denen keine Punkte existieren (also bei dem konkave Konturbereiche nicht
überbrückt werden).

Vielen Dank für eure Hilfe !!!

MFG

Fischi

Hi such mal unter www.research.microsoft.com nach Hoppe oder nach selbigen unter www.acm.org/dl .
Der hat sich mit Algorithmen zur Flächenrekonstruktion beschäftigt.
Zwar in 3D, aber dass sollte irgendwie auf 2D zu übertragen sein.

Viele Grüße
Fischi

Hallo SnoopyBlue,

habe mal kurz über das Problem nachgedacht und ich glaube das könnt gsanz schön schwierig sein, insbsondere bei einer volständig ungeordneten Punktmenge, ich versuche das mal hier in ascii aufzumalen:

x1       x2
    x3
  x4
     x5
x6       x7

Im allgemeinen Fall kann wird es wohl so sein, das es Y-Koordinaten mit nur einem Punkt gibt, hier sind das zum besispiel x3 x4 x5 da wäre die Hülle dann Null Pixel (oder was auch immer) breit, ein bischen wenig, oder?
Wenn es immer mindestens Zwei Punkte pro Y-Koordinate gibt wäre eine Hüllenbestimmung natürlich gut möglich. Oder auch wenn eine Hüllenbreite von 0 okay ist.

Ich würde es dann mit einem Sweepplane/line alg versuchen.
erst alle punkte nach y koordinate sortieren und dann von unten oder oben anfangen. "Linkesten" und "Rechtesten" Punkt rausfinden und dann zur nächsten Y-Koor und wieder L und R bestimmen und so weiter.

Such doch mal Sweepplane Verfahren.

k.

edit Jester: code Tags um Zeichnung

Jester

Hallo,

ich sehe da das Problem, daß eine solche Hülle nicht eindeutig bestimmt ist.
Es gibt oft mehrere Möglichkeiten. Beispiel: Mach drei Punkte für ein Dreieck und noch einen in die Mitte. Wenn Du das verbindest, dann bekommst Du eine Pfeilspitze. Nur: auf welcher Seite ist das offene Ende?
Du mußt Dir also zunächst überlegen, wie Du Hülle definierst, sodaß es eindeutig wird.

MfG Jester

TGGC

Jester schrieb:

ich sehe da das Problem, daß eine solche Hülle nicht eindeutig bestimmt ist.

Ich auch.

Bye, TGGC \-/