lycantropos/voronoi

Python port of boost/polygon Voronoi library (with separate C++ binding)

voronoi

In what follows python is an alias for python3.7 or pypy3.7 or any later version (python3.8, pypy3.8 and so on).

Installation

Install the latest pip & setuptools packages versions

python -m pip install --upgrade pip setuptools

User

Download and install the latest stable version from PyPI repository

python -m pip install --upgrade voronoi

Developer

Download the latest version from GitHub repository

git clone https://github.com/lycantropos/voronoi.git
cd voronoi

Install

python setup.py install

Usage

>>> from voronoi.diagram import Diagram
>>> diagram = Diagram()
>>> diagram.construct([], [])
>>> diagram.cells == diagram.edges == diagram.vertices == []
True
>>> from voronoi.point import Point
>>> diagram = Diagram()
>>> diagram.construct([Point(0, 0), Point(4, 0), Point(4, 4), Point(0, 4)], [])
>>> from voronoi.faces import Vertex
>>> diagram.vertices == [Vertex(2, 2)]
True
>>> from voronoi.segment import Segment
>>> diagram.construct([], [Segment(Point(0, 0), Point(4, 0)),
...                        Segment(Point(4, 4), Point(0, 4))])
>>> diagram.vertices == [Vertex(2, 2), Vertex(0, 2), Vertex(4, 2)]
True

for CPython original C++ implementation can be invoked by importing from _voronoi module instead.

Development

Bumping version

Preparation

Install bump2version.

Pre-release

Choose which version number category to bump following semver specification.

Test bumping version

bump2version --dry-run --verbose $CATEGORY

where $CATEGORY is the target version number category name, possible values are patch/minor/major.

Bump version

bump2version --verbose $CATEGORY

This will set version to major.minor.patch-alpha.

Release

Test bumping version

bump2version --dry-run --verbose release

Bump version

bump2version --verbose release

This will set version to major.minor.patch.

Running tests

Install dependencies

python -m pip install --force-reinstall -r requirements-tests.txt

Plain

pytest

Inside Docker container:

• with CPython

  docker-compose --file docker-compose.cpython.yml up

• with PyPy

  docker-compose --file docker-compose.pypy.yml up

Bash script (e.g. can be used in Git hooks):

• with CPython

  ./run-tests.sh

  or

  ./run-tests.sh cpython

• with PyPy

  ./run-tests.sh pypy

PowerShell script (e.g. can be used in Git hooks):

• with CPython

  .\run-tests.ps1

  or

  .\run-tests.ps1 cpython

• with PyPy

  .\run-tests.ps1 pypy

voronoi's Issues

How can I get medial axis to simplify a rectilinear polygon?

Thanks for last question, it works now. But the reason I use voronoi is to get the medial axis inside a single polygon so I can simplify the polygon just like the picture below. I'm a beginner at this. So I wonder if there exist a function or something that's able to generate the medial axis, or can I do a post-process using the diagram.vertices...etc to generate it myself?

diagram construct error：TypeError: '<' not supported between instances of 'Node' and 'Node'

This is my code for test ，and it gives me this error，what can I do to fix this？

diagram.construct([],[])
diagram.construct([Point(0, 0), Point(4, 0), Point(4, 4), Point(0, 4)], [])
print(diagram.vertices)```

_heappush(self._items, (self._sorting_key(value), value))
TypeError: '<' not supported between instances of 'Node' and 'Node'

What's the algorithm used to construct the voronoi diagram with segments as sites instead of points?

Hey, I noticed that this code can generate VDs with sites being line segments and I was curious to know what algorithm it uses to do that.

I know Fortune's algorithm is used with points as sites but I don't know if it would work for segments. Thanks