Welcome to bentley_ottmann’s documentation!

Note

If object is not listed in documentation it should be considered as implementation detail that can change and should not be relied upon.

bentley_ottmann.planar.contour_self_intersects(contour: Contour[ScalarT], /, *, context: Context[ScalarT]) → bool

Checks if contour has self-intersection.

Based on Bentley-Ottmann algorithm.

Time complexity:

O(len(contour.vertices) * log len(contour.vertices))

Memory complexity:

O(len(contour.vertices))

Reference:

https://en.wikipedia.org/wiki/Sweep_line_algorithm

Parameters:

• contour – contour to check.

• context – geometrical context.

Returns:

true if contour is self-intersecting, false otherwise.

Note

Consecutive equal vertices like Point(2, 0) in

Contour([Point(0, 0), Point(2, 0), Point(2, 0), Point(2, 2)])

will be considered as self-intersection, if you don’t want them to be treated as such – filter out before passing as argument.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Contour, Point = context.contour_cls, context.point_cls
>>> contour_self_intersects(
...     Contour([Point(0, 0), Point(2, 0), Point(2, 2)]), context=context
... )
False
>>> contour_self_intersects(
...     Contour([Point(0, 0), Point(2, 0), Point(1, 0)]), context=context
... )
True

bentley_ottmann.planar.segments_intersect(segments: Sequence[Segment[ScalarT]], /, *, context: Context[ScalarT]) → bool

Checks if segments have at least one intersection.

Based on Shamos-Hoey algorithm.

Time complexity:

O(len(segments) * log len(segments))

Memory complexity:

O(len(segments))

Reference:

https://en.wikipedia.org/wiki/Sweep_line_algorithm

Parameters:

• segments – sequence of segments.

• context – geometrical context.

Returns:

true if segments intersection found, false otherwise.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments_intersect([], context=context)
False
>>> segments_intersect(
...     [Segment(Point(0, 0), Point(2, 2))], context=context
... )
False
>>> segments_intersect(
...     [
...         Segment(Point(0, 0), Point(2, 0)),
...         Segment(Point(0, 2), Point(2, 2)),
...     ],
...     context=context,
... )
False
>>> segments_intersect(
...     [
...         Segment(Point(0, 0), Point(2, 2)),
...         Segment(Point(0, 0), Point(2, 2)),
...     ],
...     context=context,
... )
True
>>> segments_intersect(
...     [
...         Segment(Point(0, 0), Point(2, 2)),
...         Segment(Point(2, 0), Point(0, 2)),
...     ],
...     context=context,
... )
True

bentley_ottmann.planar.segments_cross_or_overlap(segments: Sequence[Segment[ScalarT]], /, *, context: Context[ScalarT]) → bool

Checks if at least one pair of segments crosses or overlaps.

Based on Bentley-Ottmann algorithm.

Time complexity:

O(len(segments) * log len(segments))

Memory complexity:

O(len(segments))

Reference:

https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm

Parameters:

• segments – sequence of segments.

• context – geometrical context.

Returns:

true if segments overlap or cross found, false otherwise.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments_cross_or_overlap([], context=context)
False
>>> segments_cross_or_overlap(
...     [Segment(Point(0, 0), Point(2, 2))], context=context
... )
False
>>> segments_cross_or_overlap(
...     [
...         Segment(Point(0, 0), Point(2, 0)),
...         Segment(Point(0, 2), Point(2, 2)),
...     ],
...     context=context,
... )
False
>>> segments_cross_or_overlap(
...     [
...         Segment(Point(0, 0), Point(2, 2)),
...         Segment(Point(0, 0), Point(2, 2)),
...     ],
...     context=context,
... )
True
>>> segments_cross_or_overlap(
...     [
...         Segment(Point(0, 0), Point(2, 2)),
...         Segment(Point(0, 2), Point(2, 0)),
...     ],
...     context=context,
... )
True