Voronoi-Diagramme

[striderx]

@Medium

Die nachträglich Vektorisierung wird u. a. auch dadurch schwierig, dass der brute-force-Ansatz keine glatten Kanten erzeugt sondern teilweise starke Treppen. Man könnte versuchen, die Stellen zu finden, an denen drei oder mehr Farben aneinander treffen (Sonderfall Ränder), dann weiß mann aber immer noch nicht, welche solcher Punkte zu welcher Zelle gehören.


@Rollo 62

Danke für die Links, nach einer ersten Prüfung bringen sie mich aber nicht weiter.

[TigerLilly]

Der Algorithmus auf Wikipedia hilft dir nicht?
https://de.wikipedia.org/wiki/Voronoi-Diagramm

Was hast du denn an Daten?

[striderx]

Zitat von TigerLilly:

Der Algorithmus auf Wikipedia hilft dir nicht?
https://de.wikipedia.org/wiki/Voronoi-Diagramm

Was hast du denn an Daten?

Na, wenn da z. B. steht "Berechne KH(P') //Mit geeignetem Algorithmus" dann fehlt mir halt der geeignete Alogrhitmus (und nicht nur an dieser Stelle).

Ich bin mir nicht sicher, was du mit 'Daten' meinst. Ich habe natürlich die Koordinaten der 'Zellkerne ('sites') und die Farben der jeweiligen Zellen (jeweils Farbe des Kerns).

[TigerLilly]

Vielleicht helfen diese Links?

http://tizian.cs.uni-bonn.de/publica...udsonKlein.pdf
http://algo.informatik.uni-freiburg..../slides/11.pdf
https://lernprocessing.wordpress.com...noi-diagramme/
http://www.pi6.fernuni-hagen.de/down...s-vdlap-02.pdf

Aber das war jetzt nur gegoogelt + das hast du wahrscheinlich auch gemacht.

Ach ja:
https://rosettacode.org/wiki/Voronoi_diagram#Delphi

[striderx]

Zitat von TigerLilly:

Aber das war jetzt nur gegoogelt + das hast du wahrscheinlich auch gemacht.

Ach ja:
https://rosettacode.org/wiki/Voronoi_diagram#Delphi

Oh ja, da habe ich mittlerweile schon einige Seiten von Suchergebnisses abgearbeitet. Die Rosettacode-Delphi-Implementierung hatte ich ganz am Anfang schon einmal ausprobiert, aber keine brauchbaren Ergebnisse bekommen. Der Code scheint nicht vollständig zu sein - was man daran sehen kann, dass die dynamisch erzeugten Variablen nirgendwo wieder frei gegeben werden.

Aber ich werde mal einen neuen Anlauf nehmen - mittlerweile weiß ich ja schon einiges mehr über das Thema.


edit: Es bleibt dabei - dieser Code erzeugt keine korrekten Ergebnisse.

[timog]

Dieser Ansatz dürfte langsamer als die Polygon Methode von RosettaCode.org sein, aber sie tut's - glaube ich

Delphi-Quellcode:

procedure TformMain.DrawVoronoi(AImage: TImage; const AP, ACells: Integer; ADistanceType: TDistanceType);
var
  px, py: array of Integer;
  LColor: array of TColor;
  LImg: TBitmap;
  n, i, x, y, j: Integer;
  d1, d2: Double;

  function GetDistance(const x1, x2, y1, y2, AP: Integer; const ADistanceType: TDistanceType): Double;
  begin
    case ADistanceType of
      dtManhattan: Result := Abs(x1 - x2) + Abs(y1 - y2);
      dtMinkovski: Result := Power(Power(Abs(x1 - x2), AP) + Power(Abs(y1 - y2), AP), (1 / AP));
    else
      Result := Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); // dtEuclidian
    end;
  end;

begin
  LImg := nil;
  try
    LImg := TBitmap.Create;
    LImg.Width := AImage.Width;
    LImg.Height := AImage.Height;

    SetLength(px, ACells);
    SetLength(py, ACells);
    SetLength(LColor, ACells);

    // Zufällige Zellen/Sites erzeugen
    for i := 0 to ACells - 1 do
    begin
      px[i] := RandomRange(1, AImage.Width-1);  // nicht direkt auf dem Rand
      py[i] := RandomRange(1, AImage.Height-1);
      LColor[i] := GenerateRandomColor;
    end;

    // In x und y Richtung die Entfernungen ermitteln, Farbe der am nächsten liegenden Zelle bestimmen
    for x := 0 to AImage.Width - 1 do
    begin
      for y := 0 to AImage.Height - 1 do
      begin
        n := 0;
        for i := 0 to ACells - 1 do
        begin
          d1 := GetDistance(px[i], x, py[i], y, AP, ADistanceType);
          d2 := GetDistance(px[n], x, py[n], y, AP, ADistanceType);
          if d1 < d2 then n := i;
        end;
        LImg.Canvas.Pixels[x, y]:=LColor[n];
      end;
    end;

    // Zelle/Site zeichnen
    for j := 0 to ACells - 1 do
    begin
      LImg.Canvas.Pen.Color := clBlack;
      LImg.Canvas.Brush.Color := clBlack;
      LImg.Canvas.Rectangle(px[j] - 2, py[j] - 2, px[j] + 2, py[j] + 2);
    end;

    AImage.Picture.Assign(LImg);
  finally
    LImg.Free;
  end;
end;

[striderx]

Vielen Dank, dass du dir die Mühe gemacht hast!

Aber ... das ist eine Umsetzung des brute-Force-Ansatzes. D. h. du prüfst für jedes Pixel, welcher Kern am nächsten liegt und färbst es dementsprechend ein. Das jeweilige Hüll-Poligon einer Zelle wird aber nicht ermittelt.

Du setzt Zellen (Cells) und Sites gleich, das sind sie aber nicht. Sites sind die einzelnen 'Kerne', Cells die sie umgebene Fläche.