lycantropos/clipping

Segments & polygons clipping

clipping

In what follows python is an alias for python3.6 or pypy3.6 or any later version (python3.7, pypy3.7 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 clipping

Developer

Download the latest version from GitHub repository

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

Install dependencies

python -m pip install -r requirements.txt

Install

python setup.py install

Usage

>>> from ground.base import get_context
>>> context = get_context()
>>> EMPTY = context.empty
>>> Mix = context.mix_cls
>>> Multipoint = context.multipoint_cls
>>> Multisegment = context.multisegment_cls
>>> Point = context.point_cls
>>> Segment = context.segment_cls
>>> left_edge = Segment(Point(0, 0), Point(0, 1))
>>> right_edge = Segment(Point(1, 0), Point(1, 1))
>>> bottom_edge = Segment(Point(0, 0), Point(1, 0))
>>> top_edge = Segment(Point(0, 1), Point(1, 1))
>>> main_diagonal = Segment(Point(0, 0), Point(1, 1))
>>> trident = Multisegment([left_edge, main_diagonal, bottom_edge])
>>> square_edges = Multisegment([bottom_edge, right_edge, top_edge, left_edge])
>>> from clipping.planar import intersect_multisegments
>>> (intersect_multisegments(trident, square_edges)
...  == intersect_multisegments(square_edges, trident)
...  == Multisegment([left_edge, bottom_edge]))
True
>>> from clipping.planar import complete_intersect_multisegments
>>> (complete_intersect_multisegments(trident, square_edges)
...  == complete_intersect_multisegments(square_edges, trident)
...  == Mix(Multipoint([Point(1, 1)]), Multisegment([left_edge, bottom_edge]),
...         EMPTY))
True
>>> from clipping.planar import unite_multisegments
>>> (unite_multisegments(trident, square_edges)
...  == unite_multisegments(square_edges, trident)
...  == Multisegment([left_edge, bottom_edge, main_diagonal, top_edge,
...                   right_edge]))
True
>>> from clipping.planar import subtract_multisegments
>>> subtract_multisegments(trident, square_edges) == main_diagonal
True
>>> (subtract_multisegments(square_edges, trident)
...  == Multisegment([top_edge, right_edge]))
True
>>> from clipping.planar import symmetric_subtract_multisegments
>>> (symmetric_subtract_multisegments(trident, square_edges)
...  == symmetric_subtract_multisegments(square_edges, trident)
...  == Multisegment([main_diagonal, top_edge, right_edge]))
True
>>> Contour = context.contour_cls
>>> Multipolygon = context.multipolygon_cls
>>> Polygon = context.polygon_cls
>>> first_square = Contour([Point(0, 0), Point(1, 0), Point(1, 1),
...                         Point(0, 1)])
>>> second_square = Contour([Point(1, 0), Point(2, 0), Point(2, 1),
...                          Point(1, 1)])
>>> third_square = Contour([Point(1, 1), Point(2, 1), Point(2, 2),
...                         Point(1, 2)])
>>> fourth_square = Contour([Point(0, 1), Point(1, 1), Point(1, 2),
...                          Point(0, 2)])
>>> from clipping.planar import intersect_multipolygons
>>> (intersect_multipolygons(Multipolygon([Polygon(first_square, []),
...                                        Polygon(third_square, [])]),
...                          Multipolygon([Polygon(second_square, []),
...                                        Polygon(fourth_square, [])]))
...  is EMPTY)
True
>>> (intersect_multipolygons(Multipolygon([Polygon(first_square, []),
...                                        Polygon(third_square, [])]),
...                          Multipolygon([Polygon(first_square, []),
...                                        Polygon(third_square, [])]))
...  == Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]))
True
>>> from clipping.planar import complete_intersect_multipolygons
>>> (complete_intersect_multipolygons(
...      Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]),
...      Multipolygon([Polygon(second_square, []),
...                    Polygon(fourth_square, [])]))
...  == Multisegment([Segment(Point(0, 1), Point(1, 1)),
...                   Segment(Point(1, 0), Point(1, 1)),
...                   Segment(Point(1, 1), Point(2, 1)),
...                   Segment(Point(1, 1), Point(1, 2))]))
True
>>> (complete_intersect_multipolygons(
...      Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]),
...      Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]))
...  == Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]))
True
>>> from clipping.planar import unite_multipolygons
>>> (unite_multipolygons(Multipolygon([Polygon(first_square, []),
...                                    Polygon(third_square, [])]),
...                      Multipolygon([Polygon(second_square, []),
...                                    Polygon(fourth_square, [])]))
...  == Polygon(Contour([Point(0, 0), Point(2, 0), Point(2, 2), Point(0, 2)]),
...             []))
True
>>> (unite_multipolygons(Multipolygon([Polygon(first_square, []),
...                                    Polygon(third_square, [])]),
...                      Multipolygon([Polygon(first_square, []),
...                                    Polygon(third_square, [])]))
...  == Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]))
True
>>> from clipping.planar import subtract_multipolygons
>>> (subtract_multipolygons(Multipolygon([Polygon(first_square, []),
...                                       Polygon(third_square, [])]),
...                         Multipolygon([Polygon(first_square, []),
...                                       Polygon(third_square, [])]))
...  is EMPTY)
True
>>> (subtract_multipolygons(Multipolygon([Polygon(first_square, []),
...                                       Polygon(third_square, [])]),
...                         Multipolygon([Polygon(second_square, []),
...                                       Polygon(fourth_square, [])]))
...  == Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]))
True
>>> from clipping.planar import symmetric_subtract_multipolygons
>>> (symmetric_subtract_multipolygons(
...      Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]),
...      Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]))
...  is EMPTY)
True
>>> (symmetric_subtract_multipolygons(
...      Multipolygon([Polygon(first_square, []), Polygon(third_square, [])]),
...      Multipolygon([Polygon(second_square, []),
...                    Polygon(fourth_square, [])]))
...  == Polygon(Contour([Point(0, 0), Point(2, 0), Point(2, 2), Point(0, 2)]),
...             []))
True

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 -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:

• with CPython

  ./run-tests.sh

  or

  ./run-tests.sh cpython

• with PyPy

  ./run-tests.sh pypy

PowerShell script:

• with CPython

  .\run-tests.ps1

  or

  .\run-tests.ps1 cpython

• with PyPy

  .\run-tests.ps1 pypy

clipping's Issues

Invalid `symmetric_subtract_multipolygons` result

For 2 multipolygons

>>> left = [([(2, 2), (6, 2), (6, 6), (2, 6)], [])]
>>> right = [([(3, 0), (5, 0), (5, 3), (3, 3)], [])]

result of symmetric_subtract_multipolygons

>>> symmetric_subtract_multipolygons(left, right)
[([(2, 2), (3, 2), (3, 0), (5, 0), (5, 2), (6, 2), (6, 6), (2, 6)],
  [[(3, 3), (5, 3), (5, 2), (3, 2)]])]

or visualized

which is invalid, because hole cannot touch polygon border in more than one point, because it tears polygon apart.
Correct result should be multipolygon consisting of 2 polygons without holes

[([(2, 2), (3, 2), (3, 3), (5, 3), (5, 2), (6, 2), (6, 6), (2, 6)], []),
 ([(3, 0), (5, 0), (5, 2), (3, 2)], [])]

or visualized

Invalid `subtract_multipolygons` result

For 2 multipolygons

>>> left = [([(0, 0), (4, 0), (4, 4), (0, 4)], [])]
>>> right = [([(2, 4), (1, 3), (3, 3)], [])]

result of subtract_multipolygons

>>> subtract_multipolygons(left, right)
[([(0, 0), (4, 0), (4, 4), (2, 4), (3, 3), (1, 3), (2, 4), (0, 4)], [])]

or visualized

which is invalid, because polygon border can't have self-intersections, it should be a hole or separate polygon instead.
Correct result should be multipolygon consisting of 1 polygon with 1 hole

[([(0, 0), (4, 0), (4, 4), (0, 4)], [[(2, 4), (1, 3), (3, 3)]])]

or visualized