# 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.

# Installing

`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

- Add package dependency
- Import
`import FortunesAlgorithm`

- 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.
```

# Literature

### Must read:

- "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)

# Contact

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

## Github

link |

Stars: 5 |

## You may find interesting

## Dependencies

## Used By

Total: 0

## Releases

## Logger and Watcher and steps limit - 2020-03-28 18:51:24

Add Logging and Diagram building progress possibilities.

## Logger

When passed, receives messages produced when certain events occur in the Algorithm.

## Watcher

When passed receives information produced during algorithm work. Data received from the Watcher is sufficient for scaffolding debug and process visualisation.