Voronoi Fortune Additional Events in Lua

[darkfrei]

I've tried to make the Fortune's algorithm in Lua, but within limited frame, so it needs flat beach line and several new events:

1. Event 1: First site event.
   Creating frame with x, y, w, h and finding any highest site (point with x, y).
   Adding first site to the diagram.
   Creating the beach line, first parabola arc and two flat beach lines: one is left from arc, another right from arc.
   The beachlines-array has three beachlines:
   flat-left (p1; u2),
   parabola arc (u2; u3)
   flat-right (u3; p4).
   
   Beachline:
   1) Create flat beachline (p1, p4).
   2) Create arc beachline (u2, u3).
   3) Split the flat beachline (p1, p4) with arc beachline (u2, u3):
   new beachline will be: (p1, u2, u3, p4).
   
   Events:
   4) Create parabola vertex event for event 6.
   
   5) Create corner event for left flat beachline (for event 5).
   6) Create corner event for right flat beachline (for event 4, but it will be updated in event 2).
   

   

   voronoi-1-1.png (50.42 KiB) Viewed 6270 times

2. Event 2: point event. (here is special case with same x, it creates vertical edge)
   Add new site to the diagram:
   1) Split the flat beachline (u3, p4) with arc beachline (u5, u6):
   new beachline will be: (p1, u2, u3, u5, u6, p4).
   
   Events:
   2) Create parabola vertex event for event 6.
   
   3) Create flat collapse event for event 3.
   4) Update corner event for right flat beachline for event 4.

   

   voronoi-1-2.png (55.58 KiB) Viewed 6268 times

3. Event 3: Flat collapse.
   1) Removing flat beachline (u3; u5) from beachlines-array.
   2) Creating new vertex v7. Adding it to the cell1 (given with site = focus1) and to cell2 (given with site = focus2).
   3) Creating new point u8.
   4) Updating arc beachline (u2; u3) to be (u2; u8),
   5) Updating arc beachline (u5; u6) to be (u8; u6),
   

   

   voronoi-1-3.png (91.05 KiB) Viewed 6264 times

   After the event:
   Now beachlines-array is: (p1; u2; u8; u6; p4):

   

   voronoi-1-4.png (75.37 KiB) Viewed 6264 times

   desmos
4. Event 4: right corner event.
   1) Removing the right flat beachline (u6, u9) from beachlines-array.
   2) Creating new vertex v4; now it belongs to cell 2.
   3) Creating new point u9.
   4) Updating arc beachline (u8; u6) to be (u8; u9).
   

   

   voronoi-1-5.png (76.51 KiB) Viewed 6256 times

   After event:
   Now beachlines-array is: (p1; u2; u8; u9):

   

   voronoi-1-5a.png (76.73 KiB) Viewed 6247 times

5. Event 5: left corner event.
   1) Removing left flat beachline from beachlines-array.
   2) Creating new vertex v1; now it belongs to cell 1.
   3) Creating new point u10.
   4) Updating arc beachline (u2; u8) to be (u10; u8).
   

   

   voronoi-1-6.png (76.28 KiB) Viewed 6240 times

   After event:
   Now beachlines-array is: (u10; u8; u9):

   

   voronoi-1-6a.png (75.44 KiB) Viewed 6238 times

   https://www.desmos.com/calculator/nuetvgpfwc

See also: https://www.desmos.com/calculator/9ecvyrrpec

[darkfrei]

• Event 6: Parabola vertex event.
  1) Subdivide arc (u10, u8) to left arc (u10, u11), flat (u11, u12) and arc (u12, u8).
  (Left arc has event to be collapsed at point v16)
  
  2)Subdivide arc (u8, u9) to arc (u8, u13), flat (u13, u14) and right arc (u14, u9).
  (Right arc has event to be collapsed at point v15)
  
  Now the Beachlines-array looks like: (u10, u11, u12, u8, u13, u14, u9)

  

  voronoi-1-7.png (77.58 KiB) Viewed 6233 times

• Event 7: bottom side event.
  Parabola arcs (u12, u8) and (u8, u13) are collapsing in the vertex v8^
  1) Remove arc (u12, u8) from beachlines-array.
  2) Remove arc (u8, u13) from beachlines-array.
  3) Adding vertex v8. It belongs to cell1 and cell2.
  4) Update flat beachline (u11, u12) to (u11, v8).
  5) Update flat beachline (u13, u14) to (v8, u14).
  
  Now the Beachlines-array looks like: (u10, u11, v8, u14, u9):

  

  voronoi-1-8.png (75.19 KiB) Viewed 6208 times

  https://www.desmos.com/calculator/mabn8rl2eb
• Event 8:

  

  voronoi-1-9.png (71.33 KiB) Viewed 6205 times

• Event 9:

  

  voronoi-1-10.png (73.45 KiB) Viewed 6205 times

[darkfrei]

Another desmos graphic solutions:
https://www.desmos.com/calculator/kzff2hb9d3
https://www.desmos.com/calculator/onvynga3da

Animation (89).gif (951.14 KiB) Viewed 6180 times

[darkfrei]

First very special point event: vertical aligned beachline splitting.

The new focus3.x is exactly same as point u8.x, it creates vertical edge. No arc is splitted, but new vertex is inserted on the cross point of two arcs.
It creates no circle event.
Beachline after event: (p1, u2, u9, u10, u6, p4)

voronoi-1-11.png (82.13 KiB) Viewed 6071 times