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: ground.hints.Contour, *, context: Optional[ground.base.Context] = None)bool[source]

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.

>>> from ground.base import get_context
>>> context = get_context()
>>> Contour, Point = context.contour_cls, context.point_cls
>>> contour_self_intersects(Contour([Point(0, 0), Point(2, 0),
...                                  Point(2, 2)]))
False
>>> contour_self_intersects(Contour([Point(0, 0), Point(2, 0),
...                                  Point(1, 0)]))
True
bentley_ottmann.planar.segments_intersect(segments: Sequence[ground.hints.Segment], *, context: Optional[ground.base.Context] = None)bool[source]

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.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments_intersect([])
False
>>> segments_intersect([Segment(Point(0, 0), Point(2, 2))])
False
>>> segments_intersect([Segment(Point(0, 0), Point(2, 0)),
...                     Segment(Point(0, 2), Point(2, 2))])
False
>>> segments_intersect([Segment(Point(0, 0), Point(2, 2)),
...                     Segment(Point(0, 0), Point(2, 2))])
True
>>> segments_intersect([Segment(Point(0, 0), Point(2, 2)),
...                     Segment(Point(2, 0), Point(0, 2))])
True
bentley_ottmann.planar.segments_cross_or_overlap(segments: Sequence[ground.hints.Segment], *, context: Optional[ground.base.Context] = None)bool[source]

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.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments_cross_or_overlap([])
False
>>> segments_cross_or_overlap([Segment(Point(0, 0), Point(2, 2))])
False
>>> segments_cross_or_overlap([Segment(Point(0, 0), Point(2, 0)),
...                            Segment(Point(0, 2), Point(2, 2))])
False
>>> segments_cross_or_overlap([Segment(Point(0, 0), Point(2, 2)),
...                            Segment(Point(0, 0), Point(2, 2))])
True
>>> segments_cross_or_overlap([Segment(Point(0, 0), Point(2, 2)),
...                            Segment(Point(0, 2), Point(2, 0))])
True
bentley_ottmann.planar.segments_intersections(segments: Sequence[ground.hints.Segment], *, context: Optional[ground.base.Context] = None)Dict[Tuple[int, int], Union[Tuple[ground.hints.Point], Tuple[ground.hints.Point, ground.hints.Point]]][source]

Returns mapping between intersection points and corresponding segments indices.

Based on Bentley-Ottmann algorithm.

Time complexity:

O(len(segments) * log len(segments) + len(intersections))

Memory complexity:

O(len(segments) + len(intersections))

Reference:

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

Parameters
  • segments – sequence of segments.

  • context – geometrical context.

Returns

mapping between intersection points and corresponding segments indices.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments_intersections([]) == {}
True
>>> segments_intersections([Segment(Point(0, 0), Point(2, 2))]) == {}
True
>>> segments_intersections([Segment(Point(0, 0), Point(2, 0)),
...                         Segment(Point(0, 2), Point(2, 2))]) == {}
True
>>> (segments_intersections([Segment(Point(0, 0), Point(2, 2)),
...                          Segment(Point(0, 0), Point(2, 2))])
...  == {(0, 1): (Point(0, 0), Point(2, 2))})
True
>>> (segments_intersections([Segment(Point(0, 0), Point(2, 2)),
...                          Segment(Point(2, 0), Point(0, 2))])
...  == {(0, 1): (Point(1, 1),)})
True