Windpark als Polygon

[mcmichael]

Hallo liebe Programmierer,

ich habe eine interessante Aufgabe im Blick: Ein aus einzelnen Punkten (Windkraftanlagen) definiertes Gebiet
mit einem konvexen Polygon zu umgeben. Alle Punkte müssen in diesem Polygon enthalten sein und
die Eckpunkte sollen ausschließlich aus den außenliegenden Punkten bestehen.

Hat jemand schon mal etwas ähnliches gemacht?
Mein Ansatz wäre wie folgt:
Aus den ersten drei Punkte bilde ich ein Dreieck. Beim nächsten Punkt prüfe ich, ob er in dem aufgespannten
Dreieck enthalten ist. Wenn nein, bildet er zunächst einen weiteren Eckpunkt des entstehenden Polygons.
(zu prüfen: Reihenfolge!)
Ich prüfe dann, ob und welche der schon definierten Eckpunkte wieder entfernt werden können.
Weiter geht's mit dem nächsten Punkt.

Habt jemand ne Idee?

Lieben Dank,
Michael

[uligerhardt]

Du suchst die konvexe Hülle des Polygons. Google mal, da gibt's bestimmt schon was.

Edit: QuickHull ist deine Idee, etwas verfeinert.

[Rollo62]

Ich weiss nicht obs dir weiterhilft, aber schau dir mal TClipper an.

Rollo

[mcmichael]

@uligerhard: Danke! Quickhull sieht sehr interessant aus - das werde ich mir auf jeden Fall mal näher ansehen.
Da es bei dem Programm nicht die Bohne auf Geschwindigkeit ankommt - Es wird alle 4 Wochen einmal gestartet werden und kann notfalls einen ganzen Tag Zeit bekommen bis es fertig ist - werde ich aus Neugier auch meinen Ansatz verfolgen.

Für Interessierte: Der umgebende Polygonzug wird für eine Annäherungswarnung für Flugzeuge eingesetzt. Damit Flugzeuge und Windräder friedlich weiterleben können...

[Mikkey]

Da Du nach Ideen fragst:

Suche einen außenliegenden Punkt (z.B. der am weitesten westlich liegende).
Von diesem Punkt ausgehend bildest Du die Richtungsvektoren zu den anderen Punkten. Der mit der nördlichsten Richtung ist Dein zweiter Punkt.
Vom zweiten Punkt bildest Du wieder die Richtungsvektoren und nimmst den, der der vorherigen Richtung am nächsten kommt.
Du wiederholst solange, bis Du den Anfangspunkt wieder erreichst.

[hathor]

Find the convex hull or a set of 2D points - Delphi Source Code

SwissDelphi

[Dejan Vu]

Beide Links zeigen die selbe Lösung.

[frankyboy1974]

hallo,

@mcmichael

Das Problem sollte wohl grundsätzlich gelöst sein! Aber eine Frage von einem Interessierten:

Zitat:

Für Interessierte: Der umgebende Polygonzug wird für eine Annäherungswarnung für Flugzeuge eingesetzt. Damit Flugzeuge und Windräder friedlich weiterleben können...

Wie muss ich dass jetzt verstehen, ist die Gesamtfläche für ein Flugzeug Tabu oder nur die Eckpunkte des Polygonzug dürfen nicht angenähert werden? Anders formuliert, ich kann die Nordsee beispielsweise in 5 Windparks einteilen und jeweils die Teilflächen sperren. Ich kann natürlich die Nordsee als einen einzigen Windpark betrachten, und somit als ganzes sperren. Ich hoffe es ist klar worauf ich hinaus will.

mfg

frank

[hathor]

Zitat von Dejan Vu:

Beide Links zeigen die selbe Lösung.

Ach, bist Du helle!

Meine Beiträge sollen keine Eintagsfliegen sein.
Link weg - Beitrag nutzlos.

[mcmichael]

Zitat von frankyboy1974:

hallo,

@mcmichael

Das Problem sollte wohl grundsätzlich gelöst sein! Aber eine Frage von einem Interessierten:

Zitat:

Für Interessierte: Der umgebende Polygonzug wird für eine Annäherungswarnung für Flugzeuge eingesetzt. Damit Flugzeuge und Windräder friedlich weiterleben können...

Wie muss ich dass jetzt verstehen, ist die Gesamtfläche für ein Flugzeug Tabu oder nur die Eckpunkte des Polygonzug dürfen nicht angenähert werden? Anders formuliert, ich kann die Nordsee beispielsweise in 5 Windparks einteilen und jeweils die Teilflächen sperren. Ich kann natürlich die Nordsee als einen einzigen Windpark betrachten, und somit als ganzes sperren. Ich hoffe es ist klar worauf ich hinaus will.

mfg

frank

@frankyboy1974: "Gesperrt" sind die Gebiete nicht - es geht um eine Alarmierung, falls ein Lfz zu tief und zu nah auf die Hindernisse zu fliegt. Das System, welches alarmiert, kann nicht mit allen einzelnen Türmen als Alarmierungsobjekten umgehen, deshalb muß zusammengefasst werden. Da die Windräder schon vom Betreiber her zu "Windparks" zusammengefasst sind, dient das als Gruppierung.