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:

Zitat von Dejan Vu (Beitrag 1311739)

Beide Links zeigen die selbe Lösung. :-)

Ach, bist Du helle!

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

[mcmichael]

Zitat:

Zitat von frankyboy1974 (Beitrag 1311740)

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.

[stahli]

Meine Mathekenntnisse reichen gerade zum Zählen von meinem Taschengeld...
Gestern habe ich mich nicht getraut zu antworten, aber vielleicht hilft es ja irgendwie:

Kürzlich habe ich zwei Funktionen zum vergrößern und verkleinern von Polygonen geschrieben. Ist auf sehr einfachem Niveau, aber für meine Zwecke ausreichend: http://www.delphipraxis.net/185374-r...-schatten.html

[Jens01]

ich habe mir gerade die Zeit genommen und den Algo von Peter Bone auf ein modernes Delphi zu übersetzen und etwas nachzubessern (es ist getestet aber nur dürftig) :

Delphi-Quellcode:

uses System.Math.Vectors, ...;

class function TPolygon.ConvexHullXY(const V: array of TVector): TArray<TVector>;
/// Author:     Peter Bone
/// Date added: 03 March, 2006
/// return the boundary points of the convex hull of a set of points
/// Url:
/// http://www.delphipages.com/tip/find_the_convex_hull_or_a_set_of_2d_points-10803.html
/// http://www.swissdelphicenter.ch/de/showcode.php?id=2230
var
  i, ii, iii : Integer;
  LPivot: TVector;
  Points: TList<TVector>;
  V1, V2: TVector;
begin
  SetLength(Result, 0);
  if System.Length(V) < 3 then
    Exit;

  Points := TList<TVector>.Create;
  try
    Points.AddRange(V);
    if Points.Count = 3 then
      Exit(Points.toArray); // already a convex hull

    // find pivot point, which is known to be on the hull
    // point with lowest y - if there are multiple, point with highest x
    Points.Sort(TComparer<TVector>.Construct(
      function(const L, R: TVector): Integer
      begin
        Result := CompareValue(R.y, L.y);
        if Result = 0 then
          Result := CompareValue(R.x, L.x);
      end));

    LPivot := Points.Extract(Points.First);

    // sort the points by angle
    Points.Sort(TComparer<TVector>.Construct(
      function(const L, R: TVector): Integer
      var
        L1, R1: TVector;
        LA, RA: Double;
      begin
        L1 := LPivot - L;
        LA := L1.x / Hypot(L1.x, L1.y);

        R1 := LPivot - R;
        RA := R1.x / Hypot(R1.x, R1.y);
        Result := CompareValue(RA, LA);
      end));

    Points.Add(LPivot);

    iii := 0;
    repeat
      // step through array to remove points that are not part of the convex hull
      ii := 0;
      for i := Points.Count - 2 downto 1 do
      begin
        // assign points behind and infront of current point
        // work out if we are making a right or left turn using vector product
        V1 := Points[i - 1] - Points[i];
        V2 := Points[i + 1] - Points[i];
        if CompareValue(V1.CrossProduct(V2).w, 0) > -1 then
        begin
          Points.Delete(i);
          Inc(ii);
        end;
      end;
      Inc(iii);
    until (ii = 0) or (iii > 10);

    Result := Points.toArray;
  finally
    Points.Free;
  end;
end;