Алгоритм бентли оттмана python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

An implementation of the Bentley-Ottmann algorithm in Python 3

alexandre-pod/bentley-ottmann

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

This is an implementation of the Bentley Ottmann algorithm in Python 3.

Launch program with default parameters

files are binary file composed of segments (a succession of 4 points).

example files are present on the test folder.

The program display the result in the treminal if tycat (on terminology) and save images on temporary folder.

The script test.py test the algorithm on files present in the tests folder and check the number of intersections.

About

An implementation of the Bentley-Ottmann algorithm in Python 3

Источник

bentley_ottmann

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

Developer

Download the latest version from GitHub repository

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

python -m pip install -r requirements.txt

Usage

we can check if they intersect

we can check if they are self-intersecting or not

Preparation

Pre-release

Choose which version number category to bump following semver specification.

bump2version --dry-run --verbose where $CATEGORY is the target version number category name, possible values are patch / minor / major .

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

Release

bump2version --dry-run --verbose release

bump2version --verbose release

This will set version to major.minor.patch .

Running tests

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

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

docker-compose --file docker-compose.pypy.yml up

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

BentleyOttmann sweep-line implementation (for finding all intersections in a set of line segments)

License

ideasman42/isect_segments-bentley_ottmann

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

readme.rst

This is a single-file, Python3 implementation of the Bentley-Ottmann sweep-line algorithm for listing all intersections in a set of line segments.

This aims to be portable & self-contained, (move to other lower languages such as C & C++).

Test-case with showing all 73,002 intersections from 14,880 segments.

At the time of writing, all the open-source implementation of Bentley-Ottmann’s sweep-line I couldn’t find a good reference implementation which performed well and could be reused or ported to different environments.

So this is my attempt to write a reference implementation with comprehensive tests.

• CompGeom (Java).
• CGAL SweepLine (C++). Not Bentley-Ottmann strictly speaking, but the method is very similar.
• The geomalgorithms.com, while a great introduction, and frequently linked to as a reference, it only detects weather the polygon is self-intersecting or not.

• Keep the library small, robust & reusable.
• Use mainly language-agnostic features. (Even though classes are used, theres no problem moving this to a language without OO).

poly_point_isect is a single Python module, exposing 2 functions.

isect_polygon(points, validate=True) Where points are a sequence of number pairs. isect_segments(segments, validate=True) Where segments is list of point-pairs.

Both return a list of intersections.

The validate argument ensures duplicate or zero length segments are ignored.

# Show the result of a simple bow-tie quad import poly_point_isect poly = ( (1.0, 0.0), (0.0, 1.0), (0.0, 0.0), (1.0, 1.0), ) isect = poly_point_isect.isect_polygon(poly) print(isect) # [(0.5, 0.5)]

There are also: isect_polygon_include_segments(points) and isect_segments_include_segments(segments) , versions of the functions described above which return a tuple for each intersection: (point, list_of_segments) so you can find which segments belong to an intersection.

• Permissive MIT license. Note that both bintrees and CompGeom are MIT Licensed too.
• Written in Python3 and runs in PyPy as well.
• Runs in vanilla Python without any dependencies.
• Uses bintrees Python module, with modifications to support a custom comparator function. Also removed some unused code.

Note Using another binary-tree library shouldn’t be a problem as long as you can override its comparison. Ideally allow passing a custom argument too (as is done here), to avoid using globals to access the sweep-line.

• Intersecting segments.
• Non intersecting segments.
• Degenerate segments (overlapping & zero length)

Test output can be optionally written to SVG files, see: tests/data_svg/ directory.

For the purpose of this section, errors in detecting intersections are defined by any discrepancy with the result compared to testing every segment against every other segment.

Very small step sizes over near-vertical lines can cause errors (note that _exactly_ vertical lines are supported but have to be handled separately).

So far I didn’t find a good general solution to this, though there are some ways to work-around the problem.

One way to resolve the problem is to use higher precision calculation for the sweep-line then the input data.

In my own tests I found for double precision floating point, ensuring at least 4e-06 between steps gives stable results * (rounding the input segments X axis to 5 decimal places).

* Checked with the included test-set at 3.6e-06 degree rotation increments from the initial rotation.

About

BentleyOttmann sweep-line implementation (for finding all intersections in a set of line segments)

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Detection of line segments & polygon edges intersections

License

lycantropos/bentley_ottmann

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

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

Download the latest version from GitHub repository

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

python -m pip install -r requirements.txt

>>> from ground.base import get_context >>> context = get_context() >>> Point, Segment = context.point_cls, context.segment_cls >>> unit_segments = [Segment(Point(0, 0), Point(1, 0)), . Segment(Point(0, 0), Point(0, 1))]

we can check if they intersect

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

>>> Contour = context.contour_cls >>> triangle = Contour([Point(0, 0), Point(1, 0), Point(0, 1)]) >>> degenerate_triangle = Contour([Point(0, 0), Point(2, 0), Point(1, 0)])

we can check if they are self-intersecting or not

>>> from bentley_ottmann.planar import contour_self_intersects >>> contour_self_intersects(triangle) False >>> contour_self_intersects(degenerate_triangle) True

Источник