bentley-ottmann 0.0.1a0

Bentley-Ottmann algorithm for searching line segments intersections.

bentley_ottmann

In what follows

• python is an alias for python3.5 or any later version (python3.6 and so on),
• pypy is an alias for pypy3.5 or any later version (pypy3.6 and so on).

Installation

Install the latest pip & setuptools packages versions:

• with CPython

  python -m pip install --upgrade pip setuptools
  

• with PyPy

  pypy -m pip install --upgrade pip setuptools
  

User

Download and install the latest stable version from PyPI repository:

• with CPython

  python -m pip install --upgrade bentley_ottmann
  

• with PyPy

  pypy -m pip install --upgrade bentley_ottmann
  

Developer

Download the latest version from GitHub repository

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

Install dependencies:

• with CPython

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

• with PyPy

  pypy -m pip install --force-reinstall -r requirements.txt
  

Install:

• with CPython

  python setup.py install
  

• with PyPy

  pypy setup.py install
  

Usage

With segments

>>> unit_segments = [((0., 0.), (1., 0.)), 
...                  ((0., 0.), (0., 1.))]

we can check if they intersect

>>> from bentley_ottmann.base import segments_intersect
>>> segments_intersect(unit_segments)
True

we can also find in which points segments intersect

>>> from bentley_ottmann.base import segments_intersections
>>> segments_intersections(unit_segments)
{(0.0, 0.0): {(0, 1)}}

here we can see that 0th and 1st segments intersect at point (0.0, 0.0).

With polygons (defined as sequence of vertices)

>>> triangle = [(0., 0.), (1., 0.), (0., 1.)]
>>> degenerate_triangle = [(0., 0.), (2., 0.), (1., 0.)]

we can check if they self-intersecting or not

>>> from bentley_ottmann.base import edges_intersect
>>> edges_intersect(triangle)
False
>>> edges_intersect(degenerate_triangle)
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:

• with CPython

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

• with PyPy

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