ideasman42 / isect_segments-bentley_ottmann

BentleyOttmann sweep-line implementation (for finding all intersections in a set of line segments)
MIT License
91 stars 40 forks source link

AssertionError when USE_IGNORE_SEGMENT_ENDINGS is False #12

Open smichr opened 6 years ago

smichr commented 6 years ago
>>> isect_polygon([(0,0),(1,0),(2,1),(-1,1)])
Traceback (most recent call last):
  File "isect.py", line 337, in remove
    self._events_current_sweep.remove(event)
  File "isect.py", line 1282, in remove
    raise KeyError(str(key))
KeyError: 'Event(0x332b3e8, s0=(-1, 1), s1=(0, 0), p=(-1, 1), type=2, slope=-1.0
)'

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "isect.py", line 597, in isect_polygon
    return isect_polygon_impl(segments, include_segments=False)
  File "isect.py", line 589, in isect_polygon_impl
    return isect_segments_impl(segments, include_segments=include_segments)
  File "isect.py", line 576, in isect_segments_impl
    sweep_line.handle(p, events_current)
  File "isect.py", line 384, in handle
    self.handle_event(e)
  File "isect.py", line 424, in handle_event
    if self.remove(e):
  File "isect.py", line 346, in remove
    assert(event.in_sweep == False)
AssertionError

Skewing lines so none are horizontal doesn't raise the error but not all intersections/endpoints are detected:

>>> isect_polygon([(0,0),(1,1),(2,1),(-1,2)])
[(-1.0, 2.0), (2.0, 1.0)]