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

Returning not just points, but the lines that created the intersections? #3

Closed nedbat closed 7 years ago

nedbat commented 7 years ago

Hi, I was about to embark on implementing this algorithm myself, but I'd love to use someone else's hard work. But I need to get back not just a list of intersection points, but for each point, the lines that created the intersection. Actually, it should be an arbitrary object that I associate with the lines. Then the return would be a list of (point, [my-object1, my-object2]) tuples.

Is this possible now? Would it be difficult to retrofit in? Is it a useful addition to this repo?

Thanks for writing it in the first place! :)

ideasman42 commented 7 years ago

Yes, this is definitely useful, committed d583f3bb5406bb30a36236d13384b85f4503c02b and ba41884f2456f5f59c10dbbcef31af07860e8d1a

If you want to associate arbitrary data you could modify the code to attach values to segments but this isn't such a small change.

To do this without changing the intersection code you could use a segment as a key for segment -> custom_object lookups, which should be OK as long as you don't have exact duplicate segments with different custom-values.

Note that this code will always re-order segments so the first point has a lower X axis.

nedbat commented 7 years ago

Wow, thanks for the fast turnaround! :)