Skip to main content

Polygon decomposition

Project description

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:

python setup.py install

Usage

>>> from pode import divide, Point, Polygon, Requirement
>>> polygon = Polygon.from_raw(([(0, 0), (1, 0), (1, 1), (0, 1)], []))
>>> 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.

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.

Notes

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

Running tests

Plain:

python setup.py test

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

Project details


Download files

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

Files for pode, version 0.1.1
Filename, size File type Python version Upload date Hashes
Filename, size pode-0.1.1-py3-none-any.whl (14.0 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size pode-0.1.1.tar.gz (15.3 kB) File type Source Python version None Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page