Intersect n line segments (on integer grid)

Question

I have a problem that looks almost like a classic CS problem of finding all intersection points of given line segments.

The slight modification is the fact that:
1. I need to split all the segments at their intersection points
2. The resulting split segments must have integer coordinates.

If I just apply standard sweepline algorithm to find all the intersection points, and than cast coordinates of these points to integers, I sometimes get new intersections caused by the moving of intersections points to the integer grid.

I may apply this algorithm repeatedly, and probably (I can't prove it), in limited number of steps reach a state where I find no new intersections. But I'm convinced there must be a simpler, more elegant solution.

I was trying to find a paper about such algorithm, but somehow couldn't find one that would deal with exactly this problem.

Can you tell point me to such a pape, or a description of an algorithm used by graphics libraries (such as Boost Polygon Library)?

Thank you.

Answer 1

This is an interesting variation to Line-segment intersection problem. Original problem of finding co-ordinates of point of intersection of these segments can be done solved using Line Sweep algorithm.

Here is an in depth article talking about Line-Sweep technique implementation for above problem. With this, intersection can be found in O(n*logn) time.

Now, in order to find the integer co-ordinates, you can cast the intersection points. But here you need to make sure about the direction of casting (which will later help in convergence).

If C in an intersection point on line segment AB, then split it into AC and CB. In AC, you cast C in direction of A, while in CB you cast it in direction of B. (By direction, I don't mean along the line segment direction, but along the half plane containing another end point.) This ensures that length of line segment will be reduced after each intersection.

PROOF: Consider, M to be maximum length of an line segment. Every time an intersection point lies on it, the length of new line segment is reduced by at least one unit. So number of iterations is bounded by M
Thus, overall iterations of your algorithm cannot exceed M.

Complexity = O(M* n *logn)