### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: [SOLVED] Voronoi diagram  (Read 2215 times)

#### Phoenix

• Jr. Member
• Posts: 98
##### [SOLVED] Voronoi diagram
« on: June 08, 2024, 07:07:25 pm »
Hi, I tried to convert the https://github.com/983/df source but there is an error that I can't see. I attach a picture demonstrating the failure  . I saw from the forum that there is another implementation but I would like to fix this one. If it works correctly, any optimizations are also welcome.
« Last Edit: June 12, 2024, 12:52:32 pm by Phoenix »

#### Eugene Loza

• Hero Member
• Posts: 708
##### Re: Voronoi diagram
« Reply #1 on: June 09, 2024, 08:19:01 am »
I'm not sure what exactly is the problem you are having. This is exactly how Voronoi diagrams look like

Note that you are (to as much as I understand the code) initializing points to

Code: Pascal  [Select][+][-]
1. x:= rand mod nx;
2. y:= rand mod ny;

with rand being a random number from 0 to 254 and nx=640, ny=360 -> x and y will always be within 0..254 range, i.e. your points crowd to top-left corner of the image, which is exactly what you observe in the image and I guess this is the part you are calling "error" and "failure" (otherwise please specify what exactly doesn't work for you). Everything beyond this range is just a "tail" of those points, exactly as it should be.

e.g. replacing those for

Code: Pascal  [Select][+][-]
1. x:= Round(Random * nx);
2. y:= Round(Random * ny);

And not forgetting Randomize before calling Random results in attached image.

Do not rush into optimizations. First make sure you understand the code well and/or the code does exactly what you need it to do. Optimizations most often "reduce the ability to read the code", which is exactly the opposite of what you need now.
My FOSS games in FreePascal&CastleGameEngine: https://decoherence.itch.io/ (Sources: https://gitlab.com/EugeneLoza)

#### Phoenix

• Jr. Member
• Posts: 98
##### Re: Voronoi diagram
« Reply #2 on: June 09, 2024, 10:09:03 am »
Quote
I'm not sure what exactly is the problem you are having
the appearance was different from the one presented in the link and this made it unusable to use as a generator in a game. Now I understand the error in the code, thank you very much

Quote
First make sure you understand the code well and/or the code does exactly what you need it to do.
in fact, looking at it now, the problem was trivial

#### Boleeman

• Hero Member
• Posts: 563
##### Re: Voronoi diagram
« Reply #3 on: June 09, 2024, 12:59:33 pm »
Made a little unfilled/Filled sampler of it rendered to a TPaintbox.

#### Phoenix

• Jr. Member
• Posts: 98
##### Re: Voronoi diagram
« Reply #4 on: June 09, 2024, 04:07:54 pm »
Quote
Made a little unfilled/Filled sampler of it rendered to a TPaintbox.
Thanks, I appreciated the extended application

#### Boleeman

• Hero Member
• Posts: 563
##### Re: Voronoi diagram
« Reply #5 on: June 10, 2024, 02:45:50 am »
You are welcome.

The Tcheckbox logic still needs a further tweak, but the main parts are working (hopefully).

I thought of converting to BgraBmp (and making the non-filled version Anti-aliased)
and speeding it up a bit.

Also:
There was a nice Vb6 version here which I may try to convert:

#### Dzandaa

• Sr. Member
• Posts: 327
• From C# to Lazarus
##### Re: Voronoi diagram
« Reply #6 on: June 10, 2024, 01:43:56 pm »
Hi,

This is a BGRABitmap version of Voronoi.

B->
Regards,
Dzandaa

#### circular

• Hero Member
• Posts: 4295
##### Re: Voronoi diagram
« Reply #7 on: June 10, 2024, 09:57:55 pm »
It's a pleasure to see all these wonderful rendering with BGRABitmap.

About Voronoi, I remember there is a geometrical way of computing the polygons. This can then be used to draw the diagram with antialiasing.

Note that contiguous polygons without border won't render perfectly when drawn sequentially. To get an antialiasing between the polygons, I've provided TBGRAMultishapeFiller class. It can be set up with many shapes and they can be drawn together according to the PolygonOrder property.
Conscience is the debugger of the mind

#### Phoenix

• Jr. Member
• Posts: 98
##### Re: Voronoi diagram
« Reply #8 on: June 11, 2024, 12:33:54 am »
Code: Pascal  [Select][+][-]
1. x:= Round(Random * nx);
2. y:= Round(Random * ny);
Considering the limit. So:
Code: Pascal  [Select][+][-]
1. x:= Trunc(Random * nx);
2. y:= Trunc(Random * ny);
Anyway @Dzandaa introduced an optimization

Also:
There was a nice Vb6 version here which I may try to convert:
Nice link, the graphic aspect is fantastic, it looks like a mosaic window
but I can't evaluate the speed of the algorithm

This is a BGRABitmap version of Voronoi.
Thanks for this additional application which is more performing thanks to BGRABitmap avoiding "pixels[ ]"  .

I saw that you removed the while loop so you also have to consider the +1
Code: Pascal  [Select][+][-]
1. ..
2. for x1:= x1+1 to Pred(nx) do //# +1
3. begin
4.  // Load new parabola (x1, dy1).
5.  dy1:= Distances[x1 + y*nx];
6.  ..
7.

I've seen that sometimes lines appear, I don't know if this is the optimal solution but they disappear
Code: Pascal  [Select][+][-]
1. ..
2. if k = 0.0 then
3.   x_intersections[n] := 0//Math.Infinity
4. ..
5.

It's a pleasure to see all these wonderful rendering with BGRABitmap.
+1

#### Josh

• Hero Member
• Posts: 1315
##### Re: Voronoi diagram
« Reply #9 on: June 11, 2024, 11:26:37 am »
made a quick 'code and go' version, it is very very slow(too much calculations), and in no way complete was going to add other things but it got even slower so stopped.
I have left that code in even though it is not used.

So I posted just for people to have a play and fix/speedup/complete it.

« Last Edit: June 11, 2024, 11:45:04 am by Josh »
The best way to get accurate information on the forum is to post something wrong and wait for corrections.

#### Dzandaa

• Sr. Member
• Posts: 327
• From C# to Lazarus
##### Re: Voronoi diagram
« Reply #10 on: June 11, 2024, 11:38:13 am »
Hi,
@Phoenix:

Here is the modified code.

B->

Regards,
Dzandaa

#### Dzandaa

• Sr. Member
• Posts: 327
• From C# to Lazarus
##### Re: Voronoi diagram
« Reply #11 on: June 11, 2024, 02:29:21 pm »
Hi,

@Josh:

This is a version using TBGRAVirtualScreen, a little faster

B->

Regards,
Dzandaa

#### Boleeman

• Hero Member
• Posts: 563
##### Re: Voronoi diagram
« Reply #12 on: June 11, 2024, 04:06:25 pm »
I found that resizing the form on 'Josh/DZandaa latest 3D version produces some pretty impressive results, even on my really slow AMD computer. Amazing.

It is great seeing all of these different variations in Voronoi.

Like the last picture below in the next thread, with Bubble FX.

Wondered if we could get shiny metallic chromium effect, like an all Gold or all Silver effect?

My attached Voronoi picture below has the bevels done with the 2nd version of my Bevel Maker.
« Last Edit: June 12, 2024, 08:27:07 am by Boleeman »

#### Dzandaa

• Sr. Member
• Posts: 327
• From C# to Lazarus
##### Re: Voronoi diagram
« Reply #13 on: June 11, 2024, 04:58:09 pm »
Hi,

Here is a new version with Bubble Fx.

B->
Regards,
Dzandaa

#### Phoenix

• Jr. Member
• Posts: 98
##### Re: Voronoi diagram
« Reply #14 on: June 12, 2024, 12:51:49 pm »
thank you all