Calculate the intersection between two segments symmetrically
When using normal formulas to calculate the intersection of two 2D segments, i.e. here , if you round the result to an integer, you get skewed results.
That is, sometimes due to rounding errors I get this intersection(A,B)!=intersection(B,A)
.
The best solution is to keep working with floats and compare the results with a certain precision. However, I have to round the results to whole numbers after calculating the intersection, I cannot keep working with floats.
My best solution so far has been to use some complete ordering on the segments in the plane and intersection
always compare the smaller segment with the larger segment.
Is there a better way? Did I miss something?
source to share
You don't want to compare segment lengths.
Also, I am assuming that when compared intersection(A',B')
with intersection(B",A")
, it is understood that the A'
coordinates are representatively identical A"
(idem for B'
and B"
), or no solution.
In this case, we consider the segments [PQ]
and [RS]
where P
, Q
, R
and S
- a point on the plane. You want the intersection of the segments:
-
[PQ]
[RS]
-
[QP]
[RS]
-
[PQ]
[SR]
-
[QP]
[SR]
-
[RS]
[PQ]
-
[SR]
[PQ]
-
[RS]
[QP]
-
[SR]
[QP]
... always return the same coordinate pair.
Ordering, first of the endpoints on each segment, then the segments themselves (based on the smallest endpoint of each segment) is the only solution that guarantees reproducible results. The ordering itself can be computationally trivial, for example. P<Q
iff P.x < Q.x || P.x == Q.x && P.y < Q.y
, although branching can be expensive when dealing with millions of segments (see how you can use SIMD to replace segment coordinates in place, if possible to generate an order).
source to share