Außenkontur erkennen

[MechMac666]

Hallo,

ich habe ein Array of Pointlist. Jede Pointlist beinhaltet die Koordinaten für z.B. eine Polylinie.

Das Ganze könnte z.B. so aussehen:


Nun möchte ich gerne die Außenkontur als eine einzelne Polylinie erhalten. Der Hintergrund ist der, das ich dieses "Outline"-Polygon als Region in der GDI verwenden möchte. Dazu dürfen es aber keine einzelnen Linien sein, sondern es muss ein "Objekt" sein.

Nur wie kann ich ermitteln, was zur Außenkontur gehört und was zur Innenkontur? Man bräuchte quasi ein "Im Uhrzeigersinn abfahren und immer links halten" Algo.

Gruß, Andreas

[BenjaminH]

Hi,
du kannst ja für jeden Punkt prüfen, ob er im Polygon, das die restlichen Punkte aufspannen enthalten ist. Wenn ja, dann lässt du den Punkt weg.
Dabei wird dir das helfen:
http://paulbourke.net/geometry/insidepoly/

Viele Grüße,
Benjamin

[Edit]Übersichtlichere Seite gefunden.

[MechMac666]

Hm. Und was wäre mit der Rot markierten Linie? Deren beiden Punkte liegen exakt auf Punkten der sich darüber und darunter befindlichen Linien.



Gruß, Andreas

[Uwe Raabe]

In diesem Fall empfehle ich eine passende Aneinanderreihung der Funktionen CreatePolyPolygonRgn und CombineRgn.

[jfheins]

Du suchst die konvexe Hülle der Punkte. Algorithmen gibt's auf Wikipedia: http://de.wikipedia.org/wiki/Konvexe_Hülle

wobei... die Hülle ist dann konvex, in deinem Beispiel hat sie also zwei schräge linien... stört das?

[Uwe Raabe]

Zitat von jfheins:

Du suchst die konvexe Hülle der Punkte. Algorithmen gibt's auf Wikipedia: http://de.wikipedia.org/wiki/Konvexe_Hülle

wobei... die Hülle ist dann konvex, in deinem Beispiel hat sie also zwei schräge linien... stört das?

Wobei "Im Uhrzeigersinn abfahren und immer links halten" aber etwas anderes ergeben würde.

[Medium]

Man könnte so Dinge tun, wie prüfen, ob die 2 Kanten an einem Punkt jeweils auf der einen Seite innerhalb, auf der anderen ausserhalb eines Polygons darstellen, was aber bei manch engen Situationen eher mäh sein kann (Point-In-Poly Prüfung von Punkten knapp neben den Kanten in Normalenrichtung - ist der Offset zu groß, kann man Lücken übersehen, ist er zu klein, haut einem die Genauigkeit vors Knie).
Das praktikabelste wird hier wirklich Uwes Lösung sein. Alternativ kannst du deine Polys auch einfarbig auf ein Bitmap zeichnen, und mit diesem als Maske eine Region erzeugen, was aber so ziemlich das gleiche sein dürfte, wie das was Windows mit Uwes Weg intern eh täte