Skip to content
An implementation of Fortune's algorithm in python
Python
Branch: master
Clone or download
Latest commit 55bc844 Jun 27, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
voronoi Fixed two errors. Jun 27, 2019
.gitignore
.travis.yml Added travis file. Jun 27, 2019
LICENSE Added license Mar 28, 2018
Pipfile
Pipfile.lock Fixed Pipefile. Jun 27, 2019
README.md Added build status badge. Jun 27, 2019
example.png Better visualization, separated coordnate and point, and added get_co… Mar 28, 2018
example.py Added example, a fix for clipping and removed duouble tree visualizat… Nov 16, 2018
setup.cfg Converted to package. Mar 28, 2018
setup.py
triangle.gif Better visualization. Mar 28, 2018

README.md

Voronoi

Build Status

A Python implementation of Fortune's algorithm based on the description of "Computational Geometry: Algorithms and Applications" by de Berg et al. The algorithm handles the special cases described in the book. The bounding box is generalized to handle a convex polygon.

Manual Installation

First, clone the repository and then install the package.

git clone https://github.com/Yatoom/voronoi.git
cd voronoi
python setup.py install

Note: you need to use sudo python3 setup.py install on most Linux distributions.

Example usage

Example that uses a polygon as a bounding box.

from voronoi import Voronoi, Polygon

# Define a set of points
points = [
    (2.5, 2.5),
    (4, 7.5),
    (7.5, 2.5),
    (6, 7.5),
    (4, 4),
    (3, 3),
    (6, 3),
]

# Define a bounding box
polygon = Polygon([
    (2.5, 10),
    (5, 10),
    (10, 5),
    (10, 2.5),
    (5, 0),
    (2.5, 0),
    (0, 2.5),
    (0, 5),
])

# Initialize the algorithm
v = Voronoi(polygon)

# Create the diagram
v.create_diagram(points=points, vis_steps=False, verbose=False, vis_result=True, vis_tree=True)

# Get properties
edges = v.edges
vertices = v.vertices
arcs = v.arcs
points = v.points

Calculate the shell size for each point

for point in v.points:
    print(f"{(point.x, point.y)} \t {point.cell_size()}")

Output:

(2.5, 2.5) 	 11.529761904761905
(4, 7.5) 	 15.064062500000006
(7.5, 2.5) 	 11.75
(6, 7.5) 	 10.520833333333329
(4, 4) 	     7.640625
(3, 3) 	     5.946354166666666
(6, 3) 	     9.423363095238095

Get coordinates for a point

v.points[0].get_coordinates()

Output:

[(0.167, 5.333), (4.5, 1.0), (4.643, 0.0), (2.5, 0), (0, 2.5), (0, 5)]

Testing

To run unit tests, run the following comand.

python3 -m "nose" voronoi/tests/unit.py
You can’t perform that action at this time.