AssertionError

[nedbat]

from poly_point_isect import *

isect_segments([
 ((-281.28544884362674, 317.6137532740669),
  (-265.13898636953286, 261.3043468249764)),
 ((-281.2854488436267, 317.6137532740669),
  (-337.59485529271734, 301.46729079997294)),
 ((-1149.6129916392008, 165.83369085939785),
  (-1163.7844481799289, 108.99508316541483)),
 ((-549.7909078231165, -373.0494512387376),
  (11.946694838912322, -684.4256889356793)),
])

produces:

Traceback (most recent call last):
  File "/Users/ned/zellij/poly_point_isect.py", line 284, in remove
    self._events_current_sweep.remove(event)
  File "/Users/ned/zellij/poly_point_isect.py", line 1197, in remove
    raise KeyError(str(key))
KeyError: 'Event(0x10d66be88, s0=(-337.59485529271734, 301.46729079997294), s1=(-281.2854488436267, 317.6137532740669), p=(-281.2854488436267, 317.6137532740669), type=0, slope=0.28674538575880665)'

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "bad_isect.py", line 11, in <module>
    (11.946694838912322, -684.4256889356793))]
  File "/Users/ned/zellij/poly_point_isect.py", line 526, in isect_segments
    return isect_segments_impl(segments, include_segments=False)
  File "/Users/ned/zellij/poly_point_isect.py", line 509, in isect_segments_impl
    sweep_line.handle(p, events_current)
  File "/Users/ned/zellij/poly_point_isect.py", line 331, in handle
    self.handle_event(e)
  File "/Users/ned/zellij/poly_point_isect.py", line 355, in handle_event
    self.remove(event)
  File "/Users/ned/zellij/poly_point_isect.py", line 293, in remove
    assert(event.in_sweep == False)
AssertionError

I'm not sure what is special about these four segments. They are the smallest set that produces the crash from a much larger set that I started with.

[ideasman42]

I don't have time to investigate this just now, but quickly checked whats going on.

• Current tests uses values between 0-1, values over 1k range I didnt try yet.
• The file contains a near duplicate point with an X value of, -281.28544884362674 and -281.2854488436267 (the second value has one less digit, it should work of course)
• Setting global EPS = 1e-13 (or smaller) in poly_point_isect.py is a temporary workaround.

In general I'd like to look in ways to get better precision from the sweep-line, however cases I ran into were corner cases and this looks to be trivial, so it should work without so much trouble.

[ideasman42]

Committed test fix in temp branch, EPS_SCALE may need tweaking though. It passes all tests as well as a new test added from your data. 1a6254af8c31a6b3ebd0cd53f54bed09a93aac23 - otherwise this feels like a weak solution, hence committing to temp branch for further investigation.

As a workaround (if you just want to use the library as-is) it may be best to normalize coords to -1..1 range since this is well tested.

[nedbat]

@ideasman42 again, thanks for the quick turnaround, and the fix/workaround. BTW, new in Python 3 is the math.isclose() function which deals with relative epsilon values. That might be helpful.

[nedbat]

I hadn't noticed that the two points weren't identical. I can also fix that on my end (https://nedbatchelder.com/blog/201707/finding_fuzzy_floats.html).

[nedbat]

On my current data, sometimes this fix works better, and sometimes master works better. ("better" meaning, doesn't fail an assertion.)

Have you considered Hypothesis as a tool for testing? I can take a stab at writing a test with it.

[ideasman42]

Regarding Hypothesis, I'd like to keep the version in master using vanilla Python (or other 3rd party Python modules optional at least). If theres some significant advantage maybe having tests using an extra module is ok - as long as the module its self remains standalone.

[nedbat]

I totally agree about not introducing third-party modules that would be required to use the code. This would only be for testing the code. If I get a test written, I'll share it, and you can decide whether it is worth the dependency.

[ideasman42]

Note that I've committed support for swapping out different number implementations (decimal, numpy, gmpy) - may be useful when investigating precision issues. see: 0457b4fd6d327ea15f1d77eabd60b84e88f0bbdb