Question about overlapping / colinear lines

[vmario89]

Hi,

i am using your implementation to write a trim-line tool for Inkscape. Basically this already works really fine except that i am not able to handle colinear line segments (lines with same slope) which are overlapping each other. At the moment there are no intersections returned for such cases like in example:

Do you have some tip for me where to fork in adjusting the code properly to return intersection points, trimmed segments or merged segments?

https://stackoverflow.com/questions/48348228/overlapping-segments-in-bentley-ottmann-algorithm

best regards, Mario

[ideasman42]

in principle it should be possible to support this using the sweep-line, as news= segments the sweep encountered can be tested again segments already being tracked.

When adding any new segment to the sweep line each segment would need to be tested, to check if it's a continuation of with any existing segments. In principle these segments could then be either merged, or removed in the case of a complete overlap.

---

A solution that simpler to try out is to pre-process the line segments.

• sort segments by their gradient.

• when more than 1 segment shares gradient with others...

  • sort by two values:

  1) the dot product of the vector rotated 90degrees. 2) the minimum dot product of their vector (on either of the segments vertices).

  • values that share the first dot product are co-linear, the second value can then be used to test for exact overlaps.

[vmario89]

i fixed it by implementing another algorithm, found at https://gist.github.com/sbma44/dc34e5005d9827aa7b1c8c11e68b0c6b