Tektosyne 6.3.2 is now available for download. This release fixes another bug in the
MultiLineIntersection class, this time a rare search state corruption in the sweep line algorithm. Thanks again to Jeff Lockhart for his valuable efforts to identify these bugs!
What happened was a misordering of adjacent positions on the sweep line, caused by their converging on an intersection point. Since the sweep line positions are now identical, ordering is based on line slopes as per the definition of the sweep line comparator. Unfortunately it can happen that the line slope ordering is the inverse of the previous position ordering, and that’s when the search structure fails.
Specifically, my sweep line structure uses indices into precomputed position and slope arrays, for speed and better numerical stability. Should the ordering of pre-converged positions and line slopes for two adjacent indices disagree, those indices are not automatically reordered upon converging at an intersection point.
The straightforward solution is to copy out the sweep line indices before a global position update, then rebuild the sweep line structure (a
TreeSet) from those indices, ensuring correct sorting order. This works but caused a slowdown of 400% (!) in my worst-case benchmark. First scanning through the copied indices and rebuilding the sweep line only when an inverse ordering between two adjacent indices is detected reduced the worst-case slowdown to a much more acceptable 10%. Average and best cases are barely affected either way.