- 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).
- 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. - 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),
After the event:
Now beachlines-array is: (p1; u2; u8; u6; p4): desmos - 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).
After event:
Now beachlines-array is: (p1; u2; u8; u9): - 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).
After event:
Now beachlines-array is: (u10; u8; u9): https://www.desmos.com/calculator/nuetvgpfwc
Voronoi Fortune Additional Events in Lua
Voronoi Fortune Additional Events in Lua
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:
Last edited by darkfrei on Tue Apr 23, 2024 11:49 am, edited 34 times in total.
Re: Voronoi Fortune Events
- 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) - 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): https://www.desmos.com/calculator/mabn8rl2eb - Event 8:
- Event 9:
Re: Voronoi Fortune Additional Events in Lua
Another desmos graphic solutions:
https://www.desmos.com/calculator/kzff2hb9d3
https://www.desmos.com/calculator/onvynga3da
https://www.desmos.com/calculator/kzff2hb9d3
https://www.desmos.com/calculator/onvynga3da
Re: Voronoi Fortune Additional Events in Lua
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)
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)
Who is online
Users browsing this forum: Google [Bot] and 5 guests