Skip to main content

Implementation of an algorithm for a polygon decomposition by Hert, S. and Lumelsky, V., 1998

Project description



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


Install the latest pip & setuptools packages versions:

python -m pip install --upgrade pip setuptools


Download and install the latest stable version from PyPI repository:

python -m pip install --upgrade pode


Download the latest version from GitHub repository

git clone
cd pode

Install dependencies:

poetry install


>>> 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)
assert parts[0].area == parts[1].area < polygon.area
assert Point(1, 1) in parts[1]

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.


Bumping version


Install bump2version.


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.


Test bumping version

bump2version --dry-run --verbose release

Bump version

bump2version --verbose release

This will set version to major.minor.patch.


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

Running tests



Inside Docker container:

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

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



./ cpython

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



.\run-tests.ps1 cpython

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pode-0.3.1.tar.gz (15.2 kB view hashes)

Uploaded source

Built Distribution

pode-0.3.1-py3-none-any.whl (13.7 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page