FortuneSwift is a swift framework that uses Fortune's Algorithm to generate Voronoi diagrams and Delaunay triangulations from a set of points on a 2D plane. Fortune's Algorithm has a time complexity of O(n log n)
, and a space complexity of O(n)
. This framework is compatible with iOS 8+, macOS 10.13+.
The FortuneSwift framework can be installed using the Swift Package Manager. In Xcode: File > Swift Packages > Add Package Dependency..
with URL: https://github.com/TateLiang/FortuneSwift.git
Or alternatively:
- Add
.package(url: "https://github.com/TateLiang/FortuneSwift.git", from: "1.1.6")
to yourPackage.swift
file'sdependencies
. - Update your packages using
$ swift package update
.
- Add package dependancy
- Import
import FortuneSwift
- Create a
Voronoi
object, specifying an array ofCoordinate
s and the rectangular area.
let points: [Coordinate] = [ ... ]
let rect = (x: 25, y: 25, width: 500, height: 500)
let voronoi = Voronoi(sites: points, numPoints: points.count, rect: rect)
Alternatively, if the array is not given, numPoints
of random points are generated within the rectangular area.
let voronoi = Voronoi(numPoints: 150, rect: rect)
FortuneSwift outputs a doubly connected edge list (DCEL) stored as arrays of sites, voronoi vertices and half-edges. This framework provides four classes for accessing the diagram: Coordinate
, Site
, Vertex
and HalfEdge
. This information can be used to draw a Voronoi diagram or Delaunay triangulation.
Once the voronoi object has been created, the resulting arrays can be obtained via the properties:
var voronoiVertices: [Vertex]
var voronoiEdges: [HalfEdge]
var voronoiSites: [Site]
The main properties of each class are detailed below.
var x: Double
var y: Double
var firstEdge: HalfEdge?
var surroundingEdges: [HalfEdge]?
var x: Double
var y: Double
var incidentEdges: [HalfEdge]
var origin: Vertex?
var destination: Vertex?
var twin: HalfEdge?
var next: HalfEdge?
var prev: HalfEdge?
var incidentSite: Site?
func walk() -> [HalfEdge]?
firstEdge
is an arbitrary edge defining the voronoi cell of a site.surroundingEdges
can be used for a list of all edges defining the cell.- The
HalfEdge
s trace out a voronoi cell counter-clockwise with the incidentSite to its left, assuming a coordinate system where y increases upward and x increases rightward. incidentSite
isnil
if it is an edge on the exterior border of the bounding rectangle.walk()
outputs an ring of theHalfEdges
defining the cell, ornil
if the edges don't form a ring (should not happen)
A voronoi diagram is a tesselation of cells in a plane, representing the points closest to a particular point. For each voronoi "site", its region is defined as the points closer to it than any other site. Voronoi diagrams are also dual-graphs of the Delaunay triangulation, where each edge of the Voronoi diagram corresponds to an adjacent edge in the Delaunay triangulation between the two incident points. Voronoi diagrams have a variety of applications including in Astronomy, Art, Biology, Robotics, and Physics.
Fortune's Algorithm is a sweep line algorithm in computational geometry. Like problems such as convex hulls or segment intersection, an event queue is maintained through a priority queue data structure. Fortune's Algorithm makes use of a binary search tree to also maintain a "beach line", representing the currently known cells based on the location of the sweep line. At the end of the algorithm, the infinite edges can be bounded by a polygon, in this case, a rectangle.
- Points outside of the bounding box will still effect the voronoi diagram, as the box simply bounds all of the infinite edges.
- The algorithm does not work with the edge case where all points are collinear.
- The algorithm does not work with the edge case where there are multiple sites at the same location.