Swiftpack.co - Package - fewlinesofcode/FortunesAlgorithm


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 O(n) space.


FortunesAlgorithm can be installed as any other Swift package. Add the following to the dependencies section of your Package.swift:

.package(url: "https://github.com/fewlinesofcode/FortunesAlgorithm", from: "1.0.0")

Basic Usage

  1. Add package dependency
  2. Import import FortunesAlgorithm
  3. 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 ... */])
            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.


Must read:

  1. "Computational Geometry Algorithms and Applications. Third Edition" by Mark de Berg, Otfried Cheong Marc van Kreveld, Mark Overmars (Voronoi diagrams section)
  2. "Introduction to Algorithms. Third Edition" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (RedBlack Trees section)
  3. A Sweepline Algorithm for Voronoi Diagrams - Steven Fortune's paper

This project would not be possible without following articles:

  1. (Fortunes Algorithm. Part 1 and Fortunes Algorithm Part 2 by Jacques Heunis (@jacquesh)
  2. Fortune's algorithm, the details by Pierre Vigier (@pvigier)


Feel free to ask questions, report bugs and submit pull requests!

You can contact me by email: oglagoliev@gmail.com or follow me on Twitter: @fewlinesofcode


Stars: 5


Used By

Total: 0


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.