AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Voronoi-Diagramme

Ein Thema von striderx · begonnen am 28. Mai 2019 · letzter Beitrag vom 30. Mai 2019
Antwort Antwort
Seite 1 von 2  1 2   
striderx

Registriert seit: 11. Feb 2007
Ort: Bergisch Gladbach
163 Beiträge
 
Delphi 10.3 Rio
 
#1

Voronoi-Diagramme

  Alt 28. Mai 2019, 17:46
Zur Zeit befasse ich mich mit Voronoi-Diagrammen.

Ein brute-force-Ansatz zum Füllen der Zellen ist ja recht schnell geschrieben, was mir aber fehlt ist ein Algorhitmus zur Bestimmung der Eckpunkte des jeweiligen Hüll-Polygons.

Hat jemand soetwas in seinem Fundus?
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.482 Beiträge
 
Delphi 2007 Enterprise
 
#2

AW: Voronoi-Diagramme

  Alt 29. Mai 2019, 01:50
Ich wage mal zu bezweifeln, dass es da einen expliziten Algo für gibt. Alle Voronoi bzw. Delauney Algos die ich bisher gesehen habe basieren in einer oder anderer Weise immer auf inkrementellen Verfahren. Bei letzterem hat man nachher zwar wirklich Punkte an der Hand, aber soweit ich weiß sind die zwei Algos zwar dual zueinander, aber man kann nicht auf einfache Weise von der Triangulierung auf die Eckpunkte des bei Voroni enstehendes "Gitters" überführen. Das Einzige was mir da einfiele wäre nachträgliche Vektorisierung. Zwar unelegant, auflösungsabhängig und nicht wirklich präzise, aber mir fällt im Moment nichts schlaueres ein.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Rollo62

Registriert seit: 15. Mär 2007
2.135 Beiträge
 
Delphi 10.3 Rio
 
#3

AW: Voronoi-Diagramme

  Alt 29. Mai 2019, 06:36
Leider nichts in Delphi, aber vielleicht ist hier was für dich dabei.
https://kynosarges.org/Tektosyne.html
https://github.com/christianbender/Algorithms-1
http://jeffe.cs.illinois.edu/compgeom/code.html
  Mit Zitat antworten Zitat
striderx

Registriert seit: 11. Feb 2007
Ort: Bergisch Gladbach
163 Beiträge
 
Delphi 10.3 Rio
 
#4

AW: Voronoi-Diagramme

  Alt 29. Mai 2019, 07:18
@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.
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
565 Beiträge
 
Delphi 10.3 Rio
 
#5

AW: Voronoi-Diagramme

  Alt 29. Mai 2019, 07:56
Der Algorithmus auf Wikipedia hilft dir nicht?
https://de.wikipedia.org/wiki/Voronoi-Diagramm

Was hast du denn an Daten?
  Mit Zitat antworten Zitat
striderx

Registriert seit: 11. Feb 2007
Ort: Bergisch Gladbach
163 Beiträge
 
Delphi 10.3 Rio
 
#6

AW: Voronoi-Diagramme

  Alt 29. Mai 2019, 09:59
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).
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
565 Beiträge
 
Delphi 10.3 Rio
 
#7

AW: Voronoi-Diagramme

  Alt 29. Mai 2019, 10:45
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
  Mit Zitat antworten Zitat
striderx

Registriert seit: 11. Feb 2007
Ort: Bergisch Gladbach
163 Beiträge
 
Delphi 10.3 Rio
 
#8

AW: Voronoi-Diagramme

  Alt 29. Mai 2019, 14:08
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.

Geändert von striderx (29. Mai 2019 um 15:38 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von timog
timog

Registriert seit: 26. Sep 2006
Ort: Landkreis Oldenburg (Oldb)
111 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#9

AW: Voronoi-Diagramme

  Alt 29. Mai 2019, 19:37
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;
Miniaturansicht angehängter Grafiken
voronoi.png  
Angehängte Dateien
Dateityp: 7z Voronoi.7z (52,4 KB, 4x aufgerufen)
Timo
Real Programmers are surprised when the odometers in their cars don't turn from 99999 to 9999A.
  Mit Zitat antworten Zitat
striderx

Registriert seit: 11. Feb 2007
Ort: Bergisch Gladbach
163 Beiträge
 
Delphi 10.3 Rio
 
#10

AW: Voronoi-Diagramme

  Alt 29. Mai 2019, 20:39
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.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 12:19 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf