simplefeatures
simplefeatures copied to clipboard
peterstace
Use Bently-Ottmann algorithm for LineString's IsSimple
We're currently using a line sweep intersection algorithm, but it's not the most efficient. This is because we're just using a slice as the status data structure (which has linear lookup and insert time complexity).
For very particularly constructed inputs, this could result in long runtimes.
Tasks:
- Add a benchmark test to exhibit the bad runtime for specially constructed inputs. This will basically be a linestring that is a zigzag 'stacked' vertically.
- Implement the Bently-Ottmann algorithm for LineString's IsSimple method.
- Confirm using the benchmark the improved result.
Resources:
- https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm
- https://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf
The original Bently Ottmann paper is http://www.itseng.org/research/papers/topics/VLSI_Physical_Design_Automation/Physical_Verification/DRC/Geometric_Intersection_Problems/1979-Bentley.pdf
Note that we're now using an R-Tree for LineString's IsSimple method. This isn't as good as using the Bently-Ottmann algorithm, but does avoid the nasty O(n^2) behaviour we were seeing before (this change was made some time ago).
It would actually make more sense to use the Shamos Hoey algorithm here, rather than the Bently-Ottmann algorithm.
Some details on the Shamos Hoey algorithm can be found here:
- https://github.com/rowanwins/shamos-hoey/blob/master/ShamosHoey.pdf
- https://github.com/rowanwins/shamos-hoey
- http://geomalgorithms.com/a09-_intersect-3.html#Shamos-Hoey-Algorithm
- https://www.npmjs.com/package/shamos-hoey
- https://codereview.stackexchange.com/questions/69/shamos-hoey-algorithm-for-checking-the-self-intersection-of-a-closed-shape
We don't actually care where the intersections are, we only care if they exist or not. The Shamos Hoey algorithm is much simpler than the Bently-Ottmann algorithm.