Vonoroi / Fortunes algorithm

[cwangdk 1]

Im' looking for a unit/code that generates a Voronoi diagram (from a 2D image with random points) pref. with Fortunes algorithm, including (!) outputting a list of the coordinates for all Voronoi polygons created in the plane - border polygons fittning the edges of the sourrounding rectangle.

 

Ref: https://en.wikipedia.org/wiki/Fortune's_algorithm

 

I do have the code for a solution that cannot output polygon coordinates 😞

 

Polygon/coordinates is needed for export to i.e. SVG scalable big print "art"-work.

 

Thanks a lot !! 🙂 BRGDS from retired programmer in Denmark /cwang.dk

 

voronoi01.bmp

Edited January 17, 2023 by cwangdk

[Rollo62 534]

Have you considered Python4Delphi, I would assume that Python has all the modern libraries easily available.

[Stefan Glienke 2001]

Not tested for correctness but translating this C++ code into Delphi should be easy enough: https://de.wikipedia.org/wiki/Voronoi-Diagramm#Programmierung

[Der schöne Günther 316]

If you already have code that outputs a bitmap, wouldn't the easiest solution be swapping out the canvas with an "svg canvas" and keeping the drawing code?

 

Quickly Create SVG (Scalable Vector Graphics) files with SVG Canvas Library for VCL in Delphi And C++Builder (embarcadero.com)

 

Haven't tried anything like this, but maybe this is a feasible option.

[cwangdk 1]

Correct - thanks Stefan.

Only my delphi code (ref: https://rosettacode.org/wiki/Voronoi_diagram ) paints by drawing pixel-line-by-pixel-line iteratating the whole canvas - the coordinates of the polygons are simply not present in the code (as far as I can see) - and furthermore this algorithm will create a massive number of SVG-code lines.

 

And I do have (my own) routines for SVG output.

 

Thanks anyway 🙂

 

[cwangdk 1]

And to Rollo: I'm not capable of Python ...

rgds cwang

[Rollo62 534]

17 hours ago, cwangdk said:

And to Rollo: I'm not capable of Python ...

Me neither

But I think it should be fairly simple to get the Python4Delphi bridge running and to understand the basics, while I assume that on the python side you may choose from a bunch of different Voronoi library incarnations for testing.
To call such voronoi functions should be similar in each case, if you have the boilerplate code running.

[David Schwartz 426]

On 1/17/2023 at 1:32 AM, cwangdk said:

Im' looking for a unit/code that generates a Voronoi diagram (from a 2D image with random points) pref. with Fortunes algorithm, including (!) outputting a list of the coordinates for all Voronoi polygons created in the plane - border polygons fittning the edges of the sourrounding rectangle.

 

Ref: https://en.wikipedia.org/wiki/Fortune's_algorithm

 

I do have the code for a solution that cannot output polygon coordinates 😞

 

Polygon/coordinates is needed for export to i.e. SVG scalable big print "art"-work.

 

Thanks a lot !! 🙂 BRGDS from retired programmer in Denmark /cwang.dk

 

voronoi01.bmp

 

I'm not sure what Fortune's algorithm has to do with anything except it's not giving you the data you want. 

 

Here's a nice theoretical discussion from a University course:

 

https://cs.brown.edu/courses/cs252/misc/resources/lectures/pdf/notes09.pdf

 

Here's your question on SO with a proposed solution:

 

https://stackoverflow.com/questions/68850889/convert-voronoi-edges-into-polygons

This might seem silly, but I suspect that modeling a manual method may be the simplest:

 

https://www.instructables.com/Hand-Drawn-Voronoi-Diagrams/

 

Overall, it doesn't seem that complicated. You just keep bisecting lines between points and the enclosed regions represent your polygons. You pick a point, then trace a bisection line until you hit an intersecting line, then keep going in the direction that gets you closer to the point you're enclosing. (It's pretty much always a Y and the other direction will take you further away.) Those intersection points are the points that form your polygonal surfaces.

 

Here's a C++ implmentation of Fortune's algorithm:

 

https://github.com/dkotsur/FortuneAlgo

 

This is where I was first introduced to Voronoi Diagrams:

 

http://www.lukatela.com/hrvoje/papers/dobbs92.html

 

Here's the DDJ code that goes with that article. At one point I translated most of it into Delphi, but never quite finished.

 

http://www.lukatela.com/hrvoje/papers/dobbs92.zip

 

 

 

 

Edited January 19, 2023 by David Schwartz

[cwangdk 1]

20 hours ago, Rollo62 said:

Me neither

But I think it should be fairly simple to get the Python4Delphi bridge running and to understand the basics, while I assume that on the python side you may choose from a bunch of different Voronoi library incarnations for testing.
To call such voronoi functions should be similar in each case, if you have the boilerplate code running.

Thanks ..

[cwangdk 1]

27 minutes ago, David Schwartz said:

 

I'm not sure what Fortune's algorithm has to do with anything except it's not giving you the data you want. 

 

Here's a nice theoretical discussion from a University course:

 

https://cs.brown.edu/courses/cs252/misc/resources/lectures/pdf/notes09.pdf

 

Here's your question on SO with a proposed solution:

 

https://stackoverflow.com/questions/68850889/convert-voronoi-edges-into-polygons

This might seem silly, but I suspect that modeling a manual method may be the simplest:

 

https://www.instructables.com/Hand-Drawn-Voronoi-Diagrams/

 

Overall, it doesn't seem that complicated. You just keep bisecting lines between points and the enclosed regions represent your polygons. You pick a point, then trace a bisection line until you hit an intersecting line, then keep going in the direction that gets you closer to the point you're enclosing. (It's pretty much always a Y and the other direction will take you further away.) Those intersection points are the points that form your polygonal surfaces.

 

Here's a C++ implmentation of Fortune's algorithm:

 

https://github.com/dkotsur/FortuneAlgo

 

This is where I was first introduced to Voronoi Diagrams:

 

http://www.lukatela.com/hrvoje/papers/dobbs92.html

 

Here's the DDJ code that goes with that article. At one point I translated most of it into Delphi, but never quite finished.

 

http://www.lukatela.com/hrvoje/papers/dobbs92.zip

 

 

 

 

Thanks David!! I do understand the algorithms, Also how to identify the polygon coordinates. My problem is the math and how to code it. Just hoping that somebody will convert this Python code ( https://github.com/Yatoom/foronoi )  to a small Delphi Pascal projekt - including a list of polygon coordinates 🙂 

[David Schwartz 426]

The thing is, the Fortune algorithm's code is partly in service to a UI that I think in your case is irrelevant. If I'm understanding you correctly, you just need the polygon vertices when the whole process is complete so you can colorize each of them, right? Meaning, I think you can go with a simpler algorithm.

 

The logic behind those hand-made art pieces is about as simple as it gets. There is no UI component at all. You just start with a random set of points and go through the math to find the bisections between pairs of points and points where they intersect. Those intersection points for a given center-point form the coordinates of your polygons. The bisection lines themselves are infinitely long until they're cut off by intersecting with another bisection line. Each of those points is going to be a member of typically three other polygons, and more if there happens to be a highly "perfect" relationship between the "random" points (very unlikely).

 

One of the unique things about the Dr. Dobb's article is that the authors change the coordinate system from (x,y) like (lat, lon) to a pair made up of an (arccos, radius) as measured from the centroid, allowing all the math to be done using 16-bit integers; even 8-bit integers are sufficient for even smaller sized v-cells. At the time it was published (1992), this resulted in a HUGE savings in floating-point computational overhead, but today it's not as significant. It still makes the problem a lot simpler.

 

But, you may object, how does this work for tracking locations on an ellpisoidal sphere like the Earth's surface? Well, the centroids are specified using a 3D coordinate system where (x,y,z) represents the point on the Earth's surface (lat, lon, radius). However, the distance between them is small enough that the voronoi cells can be treated as a 2D surface because the error due to curvature is minimal compared to the error due to localized variations in the Earth's surface over that same area. So the only floating point calculations need to be done on the centroids and everything in between is simple integer-based 2D Euclidian calculations

 

 

 

Edited January 20, 2023 by David Schwartz

[cwangdk 1]

Correct David 🙂

I need the following output, in one simple text file per Voronoi diagram:
1: Width and length of the plane, as well as number of random points/cells (= number of polygons to fill the entire plane).
2: An indexed list of all polygons' vertices (the union set of the vertices) - including vertices of polygons along the edges of the plane.
3: An indexed list with each polygon's corner points referencing to the points in list 2.
Moreover:
- Must be able to edit and run in the Delphi RAD environment (I use Delphi 10.4 Community Edition).
- No need for graphical output.
- No need for precision calculations.
- No use of 3rd party components or units.
- No special requirements for the user interface.

 

[plane]
width=w
height=h
cells=c

 

[vertices]
num=4
1=point(x,y)
2=points(a,b)
3=points(i,j)
4=points(s,t)

 

[polygons]
num=3
1=poly(1,2,3)
2=poly(1,2,3,4)
3=poly(4,2,3)

[cwangdk 1]

And the random seeds could well be included in the outputfile as well:

 

[plane]
width=w
height=h
cells=c

 

[seeds]

num=c

1=point(r1x,r1y)
2=points(r2x,r2y)
3=points(r3x,r3y)
4=points(r4x,r4y)

. . .

 

[vertices]
num=4
1=point(x,y)
2=points(a,b)
3=points(i,j)
4=points(s,t)

. . . 

 

[polygons]
num=c
1=poly(1,2,3)
2=poly(1,2,3,4)
3=poly(4,2,3)

. . .

 

 

[cwangdk 1]

A bit more structured:
 

Output tekst-file structure:

 

[plane]

width=w

height=h

cells=c

 

[cells]

num=c

1=seed(rx1,ry1)

1=poly(1,2,3)  

2=seed(rx2,ry2)

2=poly(1,2,3,4)

3=seed(rx3,ry3)

3=poly(4,2,3)

4=seed(rx4,ry4)

4=poly…

. . .

 

[vertices]

num=4

1=point(x,y)

2=point(a,b)

3=point(i,j)

4=point(s,t)

. . .

[David Schwartz 426]

What exactly are you intending to do with this data?

 

All you've said was this: 

Quote

Polygon/coordinates is needed for export to i.e. SVG scalable big print "art"-work.

 

It's really not very inforamtive.

 

I mean, if these are records or classes, you could make a TList of each one and then export each list as a CSV file, which can be imported in practically anything.

 

Is that all you need?

Edited January 21, 2023 by David Schwartz

[cwangdk 1]

Artwork posters up to size A0 🙂

 

[cwangdk 1]

Ok.

My DELPHI application (under development) has nonfigurative graphic "art"-work as output, in various patterns, various sizes/width-height formats and using different color-palettes.

So no need for precision  data - and any simple text-file-format/syntax will do for output. But I need to have access to the soucecode to make my own changes underway ..

 

The enclosed triangle tesselation data could also be intereseting to have in the textfile 🙂

 

brgds /cwangdk

 

 

Edited January 21, 2023 by cwangdk

[cwangdk 1]

I ask Chat-GPT:

 

Delphi code that generates texfile with coordinates for voronoi polygons

 

Chat-GPT answers:

 

====================================================

 

To create a Voronoi diagram with polygon coordinates output to a text file in Delphi, you can use the open-source library PolyVoronoi (https://github.com/tkoolen/polyvoronoi). The library provides functions to compute the Voronoi diagram of a set of points and to output the resulting polygons to a file in various formats.

Here is an example of how you can use the library to compute the Voronoi diagram of a set of points and output the resulting polygons to a text file in Delphi:

 

<Copy code>

 

uses

  PolyVoronoi;

 

var

  points: TArrayOfArrayOfFloat;

  polygons: TArrayOfArrayOfArrayOfFloat;

  i, j, k: Integer;

  fileName: string;

  f: TextFile;

begin

  // Define the set of points for which to compute the Voronoi diagram

  SetLength(points, 3, 2);

  points[0][0] := 0;

  points[0][1] := 0;

  points[1][0] := 1;

  points[1][1] := 1;

  points[2][0] := 2;

  points[2][1] := 2;

 

  // Compute the Voronoi diagram

  polygons := VoronoiDiagram(points);

 

  // Output the resulting polygons to a text file

  fileName := 'voronoi.txt';

  AssignFile(f, fileName);

  Rewrite(f);

  for i := 0 to High(polygons) do

  begin

    WriteLn(f, 'Polygon ', i, ':');

    for j := 0 to High(polygons) do

    begin

      WriteLn(f, '  Vertex ', j, ':');

      for k := 0 to High(polygons[j]) do

        WriteLn(f, '    ', polygons[j][k]);

    end;

  end;

  CloseFile(f);

end;

 

This is a basic example and you can customize it as per your requirement.

====================================================

 

But I can't finde the mentioned library ...

 

Edited January 21, 2023 by cwangdk

[toms 29]

Ask ChatGPT for an alternative

[xstrider 1]

Some time ago I had a similar task und came up with this approach:

• each of the seeds is assigned a unique color
• from each seed the pixels to the left are checked until a pixel of another color is found or the border is reached
• from this pixel a walking square algorithm tries to detect directional changes of the border of the respective polygon i. e. the corners.

The code attached works just fine for me but probably can be optimized in many ways.

 

 

 

Voronoi.txt

[cwangdk 1]

2 hours ago, cwangdk said:

 

xstrider: ok, but if 2 polygons have the same color we have a problem - right?

its far better for me to be able to use the coordinates and not be depentant of the pixel-based intermediate output.

thanks anyway ...  

 

toms:

(right now) ChatGPT stucks if no ref to units or libraies can be used ... af far as I have tried ...

Edited January 21, 2023 by cwangdk

[xstrider 1]

but if 2 polygons have the same color we have a problem - right?

 

That's why I wrote: "each of the seeds is assigned a unique color".

 

But this is only to find the edges of the polygons. Once you have the coordinates of the polygons you can color these any way you like.

[cwangdk 1]

Oh, yes - correct ..

[programmerdelphi2k 237]

@cwangdk

this dont help you?

 

 

Demonstrate how to generate and display a Voroni diagram. ... translated to many languages, including Delphi!

https://rosettagit.org/tasks/voronoi-diagram/

https://rosettagit.org/tasks/voronoi-diagram/#delphi

 

here im using a PaintBox as target: using a main thread!

• now you needs use "maybe" a parallelism to better performance!
• this code (from site) can raise some "bug"... fix it! 
• THIS CODE IS NOT MINE, IS FROM SITE!!!

{$R *.dfm}

uses
  System.Generics.Collections;

procedure Voronoi;
const
  p     = 3;
  cells = 100;
  size  = 1000;

var
  aCanvas    : TCanvas;
  px, py     : array of integer;
  color      : array of Tcolor;
  Img        : TBitmap;
  lastColor  : integer;
  auxList    : TList<TPoint>;
  poligonlist: TDictionary<integer, TList<TPoint>>;
  pointarray : array of TPoint;

  n, i, x, y, k, j: integer;
  d1, d2          : double;

  function distance(x1, x2, y1, y2: integer): double;
  begin
    result := sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    /// Euclidian
    // result :=  abs(x1 - x2) + abs(y1 - y2); // Manhattan
    // result := power(power(abs(x1 - x2), p) + power(abs(y1 - y2), p), (1 / p)); // Minkovski
  end;

begin

  poligonlist := TDictionary < integer, TList < TPoint >>.create;

  n := 0;
  Randomize;

  Img        := TBitmap.create;
  Img.Width  := 1000;
  Img.Height := 1000;

  setlength(px, cells);
  setlength(py, cells);
  setlength(color, cells);

  for i := 0 to cells - 1 do
    begin
      px[i] := Random(size);
      py[i] := Random(size);

      color[i] := Random(16777215);
      auxList  := TList<TPoint>.create;
      poligonlist.Add(i, auxList);
    end;

  for x := 0 to size - 1 do
    begin
      lastColor := 0;
      for y     := 0 to size - 1 do
        begin
          n := 0;

          for i := 0 to cells - 1 do
            begin
              d1 := distance(px[i], x, py[i], y);
              d2 := distance(px[n], x, py[n], y);

              if d1 < d2 then
                begin
                  n := i;
                end;
            end;
          if n <> lastColor then
            begin
              poligonlist[n].Add(Point(x, y));
              poligonlist[lastColor].Add(Point(x, y));
              lastColor := n;
            end;
        end;

      //poligonlist[n].Add(Point(x, y));  // why this 2x???
      //poligonlist[lastColor].Add(Point(x, y));
      //lastColor := n;
    end;

  for j := 0 to cells - 1 do
    begin

      setlength(pointarray, poligonlist[j].Count);
      for i := 0 to poligonlist[j].Count - 1 do
        begin
          //if Odd(i) then /// why this? and...
          //  pointarray[i] := poligonlist[j].Items[i];
        //end;
      //for i := 0 to poligonlist[j].Count - 1 do
        //begin
          //if not Odd(i) then  // why this?
            pointarray[i] := poligonlist[j].Items[i];
        end;
      Img.Canvas.Pen.color   := color[j];
      Img.Canvas.Brush.color := color[j];
      Img.Canvas.Polygon(pointarray);

      Img.Canvas.Pen.color   := clBlack;
      Img.Canvas.Brush.color := clBlack;
      Img.Canvas.Rectangle(px[j] - 2, py[j] - 2, px[j] + 2, py[j] + 2);
    end;
  //
  Form1.PaintBox1.Canvas.Draw(0, 0, Img);
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  Voronoi;
end;

Edited January 21, 2023 by programmerdelphi2k

[programmerdelphi2k 237]

NOTE: I think that using "ARRAYS" will be better than "TLIST and TDictionary!" !!!

• in my i7 16GB in can create a array with +/-90.000.000 (integers) before "out of memory"
• of course, you can find a better value using some technic to avoid "local var" usage!

 

maybe it can be more quickly using Arrays to store the values!

• or better, a array with all values (coordenates, color, points, etc...) ...
• more confused, of course! Is the math simple? 😁

type
  TMyArrays        = TArray<integer>; // or any other type
  TMyArraysOnArray = TArray<TMyArrays>;
  //
  TMyDic = TArray<TMyArrays>;
  //
  TMyDic2 = TArray<TMyArraysOnArray>;

procedure TForm1.Button1Click(Sender: TObject);
var
  LMyList: TMyArrays;
  LMyDict: TMyDic;
  //
  LMyDic2: TMyDic2;
begin
  LMyList := LMyList + [1];
  LMyList := LMyList + [2]; // ...
  //
  LMyDict := LMyDict + [LMyList];
  //
  Memo1.Lines.Add(LMyList[0].ToString + ' --- ' + LMyDict[0][1].ToString);
  //
  LMyDic2 := LMyDic2 + [[[1], [2]]];
  //
  Memo1.Lines.Add(LMyDic2[0][0][0].ToString + ' ---- ' + LMyDic2[0][1][0].ToString);
  //
  // Voronoi;
end;

Edited January 21, 2023 by programmerdelphi2k