pode

Summary

pode is a Python library that implements an algorithm of Hert, S. and Lumelsky, V., 1998 for a polygon decomposition into separate parts depending on the area requirements.

Main features are

• all calculations are robust for floating point numbers & precise for integral numbers (like int)
• support for partition of convex/nonconvex polygons with/without holes
• support for anchored partition, free partition, and a mixture of both where anchored polygon partition requires the resulting polygon parts to contain specified points called "anchors" or "sites", and free partition does not have any constraints on the resulting geometries.
• most of the code is covered with property-based tests.

---

In what follows

• python is an alias for python3.8 or any later version (python3.9 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 pode

Developer

Download the latest version from GitHub repository

git clone https://github.com/LostFan123/pode.git
cd pode

Install dependencies:

poetry install

Usage

>>> from pode import divide, Contour, Point, Polygon, Requirement
>>> contour = Contour([Point(0, 0), Point(1, 0), Point(1, 1), Point(0, 1)])
>>> polygon = Polygon(contour)
>>> requirements = [Requirement(0.5), Requirement(0.5, point=Point(1, 1))]
>>> parts = divide(polygon, requirements)
>>> parts[0].area == parts[1].area < polygon.area
True
>>> Point(1, 1) in parts[1]
True

Currently, the algorithm uses constrained Delaunay triangulation to form convex parts which are used internally for a convex-polygon partition. This triangulation, however, affects the resulting partition. The resulting parts can have zigzag pattern separating different parts. In this way, the solution can be far from being optimal in sense of the number of sides of the resulting polygons. Alternatively, we implemented a helper function that would join neighboring triangles if they form a larger convex part. It can be imported as from pode import joined_constrained_delaunay_triangles and used as divide(polygon, requirements, joined_constrained_delaunay_triangles). But, in the future, a better algorithm should be implemented, like Greene, D.H., 1983 or Chazelle, B. and Dobkin, D., 1979.

Development

Bumping version

Preparation

Install bump-my-version.

Pre-release

Choose which version number category to bump following semver specification.

Test bumping version

bump-my-version bump --dry-run --verbose $CATEGORY

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

Bump version

bump-my-version bump --verbose $CATEGORY

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

Release

Test bumping version

bump-my-version bump --dry-run --verbose release

Bump version

bump-my-version bump --verbose release

This will set version to major.minor.patch.

Notes

To avoid inconsistency between branches and pull requests, bumping version should be merged into master branch as separate pull request.

Running tests

Plain:

pytest

Inside Docker container:

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

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

./run-tests.sh

or

./run-tests.sh cpython

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

.\run-tests.ps1

or

.\run-tests.ps1 cpython