Get the latest tech news
Generating Voronoi diagrams using Fortune's algorithm
This article is about using Fortune’s Algorithm to generate Voronoi Diagrams in O(nlogn) time. If I’d known how hard it would be I wouldn’t have started it.
Processing a circle event results in an arc being removed from the beach line, and a Voronoi Vertex and two half edges being created. This is probably the hardest concept in the algorithm to grok, so I’m going to spend some time on it, before talking about what happens when our sweepline passes a circle point. A couple of sections ago I started adding those orange lines to the diagram to indicate the equiedges, but I didn’t talk about what they were exactly.
Or read this on Hacker News