2

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?

Community
  • 1
  • 1
Elazar Leibovich
  • 32,750
  • 33
  • 122
  • 169
  • 1
    Any reason that you can't use, say, symmetricIntersection(A,B)=(intersection(A,B)+intersection(B,A))/2 ? Floating point addition is commutative. – brainjam Apr 12 '10 at 15:21
  • @brainjam, it's really nice and mathematically sound, but it requires me to calculate intersection twice, and to rely on floating point rounding, so I'm not sure it's much better than ordering on segments in practice. Anyhow thumbs up! Liked it. – Elazar Leibovich Apr 12 '10 at 15:42
  • @brainjam, once error creeps in, any operation can amplify the error. So if already comparing `X`==`Y` came out false, `X`==`(X+Y)/2` will likely also come out false. Moreover, in cases when `X`==`Y` could have come out true, `X`==`(X+Y)/2` may come out false (e.g when `X` and `Y` can be represented without error, but `X+Y` can no longer be represented without error.) – vladr Apr 12 '10 at 15:46

1 Answers1

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.)

vladr
  • 65,483
  • 18
  • 129
  • 130
  • Thanks, that's what I thought of. However, if there was a method that always choose the computational path that gives the least precision error, that would be symmetric, and would reduce the precision error. Maybe it is not possible to do that though. – Elazar Leibovich Apr 11 '10 at 16:51
  • @Vlad, You start off with "You do not want to compare segment lengths". Why do you say that? Is it computational cost, or something else? – brainjam Apr 12 '10 at 14:51
  • @brainjam, while I can't speak for Vlad, I think he don't want the precision lost and the computational cost of the square root function. – Elazar Leibovich Apr 12 '10 at 15:43
  • @barinjam, multiple reasons, both computational cost and correctness. In the end what you want is for the *oredering* of non-commutative terms in the intersection formula http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/ to be the same irrespective of the order in which the 4 endpoint `(x,y)` pairs are presented, which can be resolved by ordering them (the points.) Segment length is a *naive* criterion which does not guarantee non-commutative term ordering in the calculation which ultimately generates the errors. – vladr Apr 12 '10 at 15:43