I'm trying to implement Fortune's algorithm in Julia to find the Voronoi polygons of an array of random points, but I'm really struggling with the beachline.
I know that the beachline is the union of several parabolas. Each parabola has a point from the array as it's focus, so the intersection of the parabolas that are next to each other gives out the "edge" between the two Voronoi regions. Each Point in the array will be an event for the beachline to be in, but there will be also something called "circle points" which correspond to a pole (the lowest in this case) of a circle that passes through three "real points", and the real points are the points in the array of random points.
I know how to intersect parabolas, I also know that when the beachline goes through a real point, its parabola will be half a line that intersects the parabolas of previous points, and that interseccion is easy to find.
How do you store the beachline? do you just store the points of intersections as you go through the events calculating every intersection of neighbors parabolas?
I'm reading Computational Geometry algorithms and applications by Mark de Berg, but my native language is not english, so it's a little hard for me to understand a few things.
So it would be great if you could help me on this, thanks in advance.
When deciding how to represent the beach line, the important consideration is that each "event" that you process in the course of the algorithm must make only local modifications to it. If the sweep line moves a little bit, but doesn't cross any events, then your representation of the beach line should not need to change.
Therefore, the beach line data structure should not include any actual points on the beach line!
It's also important that you can find the parts to modify in O(log N) time.
The simplest representation is just a binary search tree containing the input points that contribute parabolas to the beach line, in order. The modifications made during each event then consist of adding or removing single points.