Non-deterministic failure

[nedbat]

I've been experimenting with a Hypothesis test: https://github.com/nedbat/isect_segments-bentley_ottmann/tree/hypothesis

It found this case that fails, but only sometimes:

>>> import poly_point_isect
>>> segments = [((2, 0), (0, 0)), ((1, 0), (0, 0)), ((2, 1), (1, 0))]
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
Traceback (most recent call last):
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 334, in remove
    self._events_current_sweep.remove(event)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 1279, in remove
    raise KeyError(str(key))
KeyError: 'Event(0x106b51a08, s0=(1, 0), s1=(2, 1), p=(1, 0), 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 "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 598, in isect_segments_include_segments
    return isect_segments_impl(segments, include_segments=True)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 573, in isect_segments_impl
    sweep_line.handle(p, events_current)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 381, in handle
    self.handle_event(e)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 421, in handle_event
    if self.remove(e):
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 343, in remove
    assert(event.in_sweep == False)
AssertionError
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
Traceback (most recent call last):
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 334, in remove
    self._events_current_sweep.remove(event)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 1279, in remove
    raise KeyError(str(key))
KeyError: 'Event(0x106b623a8, s0=(1, 0), s1=(2, 1), p=(1, 0), 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 "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 598, in isect_segments_include_segments
    return isect_segments_impl(segments, include_segments=True)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 573, in isect_segments_impl
    sweep_line.handle(p, events_current)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 381, in handle
    self.handle_event(e)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 421, in handle_event
    if self.remove(e):
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 343, in remove
    assert(event.in_sweep == False)
AssertionError
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
Traceback (most recent call last):
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 334, in remove
    self._events_current_sweep.remove(event)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 1279, in remove
    raise KeyError(str(key))
KeyError: 'Event(0x106b62828, s0=(1, 0), s1=(2, 1), p=(1, 0), 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 "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 598, in isect_segments_include_segments
    return isect_segments_impl(segments, include_segments=True)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 573, in isect_segments_impl
    sweep_line.handle(p, events_current)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 381, in handle
    self.handle_event(e)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 421, in handle_event
    if self.remove(e):
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 343, in remove
    assert(event.in_sweep == False)
AssertionError
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
>>> isects = poly_point_isect.isect_segments_include_segments(segments)
Traceback (most recent call last):
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 334, in remove
    self._events_current_sweep.remove(event)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 1279, in remove
    raise KeyError(str(key))
KeyError: 'Event(0x106b603a8, s0=(1, 0), s1=(2, 1), p=(1, 0), 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 "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 598, in isect_segments_include_segments
    return isect_segments_impl(segments, include_segments=True)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 573, in isect_segments_impl
    sweep_line.handle(p, events_current)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 381, in handle
    self.handle_event(e)
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 421, in handle_event
    if self.remove(e):
  File "/src/isect_segments-bentley_ottmann/poly_point_isect.py", line 343, in remove
    assert(event.in_sweep == False)
AssertionError
>>>

[ideasman42]

From testing higher precision numbers and looking into these issues further, I think this algorithm only works with quantized input.

I'd like to check on using cgal's method since its very robust, its roughly similar (uses a sweepline to track intersections) http://doc.cgal.org/latest/Sweep_line_2/index.html

[nedbat]

What do you mean by quantized input? What is the source of the non-determinism?

[joernheissler]

In line 418, event_set is

{
    Event(0x7f205de2c828, s0=(0, 0), s1=(2, 0), p=(0, 0), type=2, slope=0.0),
    Event(0x7f205de2cdc8, s0=(1, 0), s1=(2, 1), p=(1, 0), type=2, slope=1.0),
}

Or with reversed order.

[nedbat]

9 makes the behavior consistent, though it always asserts. Is there a way to make it produce results?