search

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

Docstring fix #2

Closed stephenmcd closed 8 years ago

stephenmcd commented 8 years ago

Presumably copied from isect_segments__naive.

PS: Thanks for releasing this, it's helping me learn the algorithm.

ideasman42 commented 8 years ago

Glad you found this useful, though I didn't see any examples of this method that doesn't give problems with near vertical lines, even the authors of the paper suggest to jitter the points to avoid problems (which seems very weak!).

From the wiki page:

. Bentley & Ottmann (1979) suggested perturbing the input slightly to avoid these kinds of numerical coincidences, but did not describe in detail how to perform these perturbations.

For lines which are continuous (not simply random edges), I found this method works quite well, and is significantly less complicated.

https://gitlab.com/ideasman42/isect_all_lines_1d_bintree/tree/master

For detailed lines which self-overlap a lot, it would be better to create a spatial tree (2D BVH for example), then detect overlapping nodes - see: https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;674756bfcecef5ca644978f4e208674f9cd3a6b6$28-47