cwangdk 1 Posted January 17 (edited) 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 by cwangdk Share this post Link to post

Rollo62 399 Posted January 17 Have you considered Python4Delphi, I would assume that Python has all the modern libraries easily available. Share this post Link to post

Stefan Glienke 1565 Posted January 17 Not tested for correctness but translating this C++ code into Delphi should be easy enough: https://de.wikipedia.org/wiki/Voronoi-Diagramm#Programmierung Share this post Link to post

Der schöne Günther 231 Posted January 17 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. Share this post Link to post

cwangdk 1 Posted January 17 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 🙂 Share this post Link to post

cwangdk 1 Posted January 17 And to Rollo: I'm not capable of Python ... rgds cwang Share this post Link to post

Rollo62 399 Posted January 18 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. Share this post Link to post

David Schwartz 329 Posted January 19 (edited) 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 by David Schwartz Share this post Link to post

cwangdk 1 Posted January 19 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 .. Share this post Link to post

cwangdk 1 Posted January 19 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 🙂 Share this post Link to post

David Schwartz 329 Posted January 20 (edited) 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 by David Schwartz Share this post Link to post

cwangdk 1 Posted January 20 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) Share this post Link to post

cwangdk 1 Posted January 20 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) . . . Share this post Link to post

cwangdk 1 Posted January 20 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) . . . Share this post Link to post

David Schwartz 329 Posted January 21 (edited) 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 by David Schwartz Share this post Link to post

cwangdk 1 Posted January 21 (edited) 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 by cwangdk Share this post Link to post

cwangdk 1 Posted January 21 (edited) 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 by cwangdk Share this post Link to post

xstrider 1 Posted January 21 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 Share this post Link to post

cwangdk 1 Posted January 21 (edited) 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 by cwangdk Share this post Link to post

xstrider 1 Posted January 21 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. Share this post Link to post

programmerdelphi2k 75 Posted January 21 (edited) @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 by programmerdelphi2k Share this post Link to post

programmerdelphi2k 75 Posted January 21 (edited) 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 by programmerdelphi2k Share this post Link to post