Punkte umschließendes Polygon ermitteln?

[fliegermichl]

Hallo,

ich habe eine Liste von Punkten und möchte das diese umschließende Polygon ermitteln.
Kann mir da jemand einen Algorithmus nennen oder hat so etwas schon fertig?

Polygon_um_Punkte.png (4.3 KiB) 2887 mal betrachtet

[wp_xyz]

Ich denke, so wie die Skizze aussieht, ist das ohne weitere Information nicht lösbar. Denn durch welche Kriterien ist festgelegt, dass das Polygon ausgerechnet an den verwenden Punkten nach innen geht?

Eine üblichere Fragestellung ist die nach der konvexen Hülle. Das ist das Polygon das man erhält, wenn man - bildlich gesprochen - an dem am weitesten links liegenden Punkt eine Schnur verknotet und diese dann um die Punktwolke herum führt, bis man wieder zum Ausgangspunkt zurückkommt. Somit gibt es keine Stellen, an denen das Polygon wieder in die Punktwolke "hineingeführt" wird.

Eine Routine für die konvexe Hülle gibt es z.B. im SwissDelphiCenter: https://www.swissdelphicenter.ch/en/sho ... hp?id=2230

[fliegermichl]

Danke erstmal für die Antwort.
Die konvexe Hülle kann ich ermitteln. Die ist aber nicht was ich brauche.
Ich habe eine Schnittstelle zu den Daten der Fa. Airteam geschrieben. Diese fliegen mit einer Drohne über Gebäude und ermitteln so die Gebäudegeometrie.

Allerdings gibt es keine Informationen über die unter dem Dach befindlichen Wände.

Also habe ich zunächst alle Punkte der Dachflächen in die X/Y Ebene projiziert und muss nun die äußeren Begrenzungen ermitteln um den Grundriß und die Wandflächen berechnen zu können.

[fliegermichl]

Im Internet habe ich diesen englischsprachigen Aufsatz zu dem Thema gefunden. (Daraus ist auch die Grafik).

Aber so richtig schlau werde ich da nicht draus.

[wp_xyz]

Diese fliegen mit einer Drohne über Gebäude und ermitteln so die Gebäudegeometrie.

Und was gibt diese Messung aus? Ein Foto? Ein 3D-Modell des Gebäudes?

[fliegermichl]

3D Modell der Dachflächen und Dachaufbauten (Fenster, Kamine, Gauben etc.)

[m.fuchs]

ich habe eine Liste von Punkten und möchte das diese umschließende Polygon ermitteln.
Kann mir da jemand einen Algorithmus nennen oder hat so etwas schon fertig?

Woher weißt du, dass das eingezeichnete Polygon das richtige ist?

[fliegermichl]

ich habe eine Liste von Punkten und möchte das diese umschließende Polygon ermitteln.
Kann mir da jemand einen Algorithmus nennen oder hat so etwas schon fertig?

Woher weißt du, dass das eingezeichnete Polygon das richtige ist?

Ich vermute mal, daß es dasjenige mit der kleinsten Fläche ist.
Bei meiner weiteren Recherche bin ich auf diese Wikipedia Seite gestoßen.

Dort wird dieses gesuchte Polygon als Alpha Shape bezeichnet.

[TSchnuckenbock]

Schau mal auf die folgende Seite:

https://saturncloud.io/blog/what-is-the ... ithm-in-c/

Das wird Alpha Shape auch als konkave Hülle bezeichnet, wenn ich das recht verstanden habe.

(ich kannte bisher auch nur die konvexe Hülle )

[fliegermichl]

Schau mal auf die folgende Seite:

https://saturncloud.io/blog/what-is-the ... ithm-in-c/

Das wird Alpha Shape auch als konkave Hülle bezeichnet, wenn ich das recht verstanden habe.

(ich kannte bisher auch nur die konvexe Hülle )

Danke, ich schaue mir das mal an.
Ja konkave Hülle ist richtig weil sonst würde ich ja Wände ermitteln wo gar keine Dachfläche drüber ist. Dann regnet es da in die Bude

[wp_xyz]

Weiß nicht... Das Problem liegt darin, dass man einen magischen Grenzwert alpha braucht, um entscheiden zu können, ob Dreiecke aus der Dreieckszerlegung entfernt werden sollen.

Ich habe für eine unfertige Erweiterung von TAChart eine Delaunay-Zerlegung im Werkzeugkasten und habe ein Testprogramm für die Alpha-Shape umgebaut. Das Programm erzeugt eine zufällige Punkt-Wolke und macht darauf eine Delaunay-Zerlegung, d.h. es findet Dreiecke so dass in deren Umkreis (Kreis durch drei Punkte) keine weiteren Punkte mehr liegen. Das Polygon der äußersten Randlinien der Dreiecks-Wolke ist zunächst mal konvex (d.h. keine Eindellungen). Führe ich nun diesen Alpha-Wert ein (1/UmkreisRadius) und erhöhte ich ihn langsam, verschwinden allmählich die Dreiecke am Rand und die Wolke bekommt Eindellungen. Nur: Wo ist das Ende? Die absolute Grenze scheint bei Alpha = 4.7 erreicht zu sein, wenn sich das erste Dreieck abtrennt, aber auch schon bei Alpha = 3.7 verschwindet ein inneres Dreieck (#60) aus der Zerlegung. Und auch vorher ist ein weiter Übergangsbereich.

Das Beispiel ist natürlich extrem, weil die Punkte völlig zufällig und weitgehend homogen verteilt sind. Vielleicht ist es besser, wenn die Messwerte zu Clustern gruppiert liegen.

Ich wäre nicht begeistert, wenn der Grundriss meiner Wohnung so vermessen werden würde.

Bemerkung: Das Programm berechnet noch nicht die "konkave Hülle".

[six1]

Ich vermute mal, daß es dasjenige mit der kleinsten Fläche ist.

Hi,
ich denke, das können nicht alle Bedingungen sein, denn sonst wäre die Fläche bei den eingezeichneten Strecken kleiner...
Man könnte noch einen Helligkeitstest der benachbarten Pixel ausführen, um angrenzende zugehörige Flächen zu erkennen.

Image1.jpg (3.97 KiB) 2738 mal betrachtet

[fliegermichl]

Vielen Dank für eure Mithilfe

Ich glaube, ich denke zu kompliziert.

Ich hatte ja geschrieben, daß ich nur die Punkte hab, aber das stimmt nicht.
Ich habe die Koordinaten der Dachflächen.

Somit sind auch die gesuchten Kanten bereits vollständig vorhanden und müssen nur identifiziert werden.

AirteamImport.png (12.56 KiB) 2724 mal betrachtet

Wie auf der Grafik zu sehen ist, können auch mehrere Gebäude enthalten sein. Diese habe ich aber schon getrennt in eigenen Klassen.
D.h. die Erkennung der umlaufenden Flächenkanten kann für jedes Gebäude separat ausgeführt werden.

[fliegermichl]

Da aber z.B. auch so etwas vorkommt, kann ich die konvexe Hülle nicht verwenden.

Winkelbau.png (19.63 KiB) 2723 mal betrachtet

[fliegermichl]

Weiß nicht... Das Problem liegt darin, dass man einen magischen Grenzwert alpha braucht, um entscheiden zu können, ob Dreiecke aus der Dreieckszerlegung entfernt werden sollen.

Ich habe für eine unfertige Erweiterung von TAChart eine Delaunay-Zerlegung im Werkzeugkasten und habe ein Testprogramm für die Alpha-Shape umgebaut. Das Programm erzeugt eine zufällige Punkt-Wolke und macht darauf eine Delaunay-Zerlegung, d.h. es findet Dreiecke so dass in deren Umkreis (Kreis durch drei Punkte) keine weiteren Punkte mehr liegen. Das Polygon der äußersten Randlinien der Dreiecks-Wolke ist zunächst mal konvex (d.h. keine Eindellungen). Führe ich nun diesen Alpha-Wert ein (1/UmkreisRadius) und erhöhte ich ihn langsam, verschwinden allmählich die Dreiecke am Rand und die Wolke bekommt Eindellungen. Nur: Wo ist das Ende? Die absolute Grenze scheint bei Alpha = 4.7 erreicht zu sein, wenn sich das erste Dreieck abtrennt, aber auch schon bei Alpha = 3.7 verschwindet ein inneres Dreieck (#60) aus der Zerlegung. Und auch vorher ist ein weiter Übergangsbereich.

Das Beispiel ist natürlich extrem, weil die Punkte völlig zufällig und weitgehend homogen verteilt sind. Vielleicht ist es besser, wenn die Messwerte zu Clustern gruppiert liegen.

Ich wäre nicht begeistert, wenn der Grundriss meiner Wohnung so vermessen werden würde.

Bemerkung: Das Programm berechnet noch nicht die "konkave Hülle".

Vielen Dank für diesen Beitrag.
Leider kann ich das Projekt nicht compilieren.
Ich bekomme eine Fehlermeldung
tadelaunay.pas(236,37) Error: Incompatible type for arg no. 2: Got "TDoublePoint", expected "TPoint"

Code: Alles auswählen

    ARadius := -PointDist(B, ACenter);

Die Routine PointDist in TAGeometry.pas erwartet Parameter vom Typ TPoint und ich konnte auch keine überladene Funktion für Parameter vom Typ TDoublePoint finden.