FortunesAlgorithm is a Swift package for building Voronoi diagrams using Steven Fortune's algorithm. Algorithm guarantees
O(n log n) worst-case running time and uses
FortunesAlgorithm can be installed as any other Swift package. Add the following to the
dependencies section of your
.package(url: "https://github.com/fewlinesofcode/FortunesAlgorithm", from: "1.0.0")
- Add package dependency
- Add diagram computation code in appropriate place:
let fortuneSweep = FortunesAlgorithm() var diagram = Diagram() let clippingRect = Rectangle( origin: Vertex(x: 20, y: 20), size: Size(width: 100, height: 100) ) var sites = Set<Site>([Site(x: 10, y: 10), Site(x: 50, y: 50)/* Generate sites you need ... */]) fortuneSweep.compute( sites: sites, diagram: &diagram, clippingRect: clippingRect ) // `diagram.cells` now contains doubly linked list of `HalfEdges` and their twins allowing you to continue diagram usage drawing.
- "Computational Geometry Algorithms and Applications. Third Edition" by Mark de Berg, Otfried Cheong Marc van Kreveld, Mark Overmars (Voronoi diagrams section)
- "Introduction to Algorithms. Third Edition" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (RedBlack Trees section)
- A Sweepline Algorithm for Voronoi Diagrams - Steven Fortune's paper
This project would not be possible without following articles:
- (Fortunes Algorithm. Part 1 and Fortunes Algorithm Part 2 by Jacques Heunis (@jacquesh)
- Fortune's algorithm, the details by Pierre Vigier (@pvigier)
Feel free to ask questions, report bugs and submit pull requests!
You may find interesting
Logger and Watcher and steps limit - 2020-03-28 18:51:24
Add Logging and Diagram building progress possibilities.
When passed, receives messages produced when certain events occur in the Algorithm.
When passed receives information produced during algorithm work. Data received from the Watcher is sufficient for scaffolding debug and process visualisation.