calculate intersection between two segments in a symmetric way

Question

When using the usual formulas to calculate intersection between two 2D segments, ie here, if you round the result to an integer, you get non-symmetric results.

That is, sometimes, due to rounding errors, I get that intersection(A,B)!=intersection(B,A).

The best solution is to keep working with floats, and compare the results up to a certain precision. However, I must round the results to integers after calculating the intersection, I cannot keep working with floats.

My best solution so far was to use some full order on the segments in the plane, and have intersection to always compare the smaller segment to the larger segment.

Is there a better method? Am I missing something?

Answer 1

You do not want to compare segment lengths.

Also, I assume that when comparing intersection(A',B') to intersection(B",A") it is understood that A''s coordinates are representationally identical to A"'s (idem for B' and B"), or else there is no solution.

This being said, consider segments [PQ] and [RS], where P, Q, R and S are points in the plane. You want the intersections of the segments:

• [PQ] [RS]
• [QP] [RS]
• [PQ] [SR]
• [QP] [SR]
• [RS] [PQ]
• [SR] [PQ]
• [RS] [QP]
• [SR] [QP]

... to always return the same coordinate pair.

Ordering, first of the endpoints on each segment, then of the segments themselves (based on each segments' least endpoint), is the only solution that guarantees reproducible results. The ordering itself can be computationally trivial, e.g. P<Q iff P.x < Q.x || P.x == Q.x && P.y < Q.y, although branching could get expensive if dealing with millions of segments (see how you can make use of SIMD to swap segment coordinates in-place if possible to generate the ordering.)