使用常用公式计算两个 2D 线段之间的交集时，即 此处，如果将结果四舍五入为整数，则会得到非对称结果。
也就是说，有时，由于舍入错误，我会得到 intersection(A,B)!=intersection(B,A)。
最好的解决方案是继续使用浮点数，并以一定的精度比较结果。但是，在计算交集后，我必须将结果舍入为整数，我不能继续使用浮点数。
到目前为止，我最好的解决方案是对平面上的线段使用一些完整的顺序，并使用交集来始终将较小的线段与较大的线段进行比较。
有更好的方法吗？我错过了什么吗？
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?
发布评论
评论（1）
您不想比较段长度。
另外，我假设将
intersection(A',B')与intersection(B",A")进行比较时，可以理解A'的坐标代表性与相同A"（同上B'和B"），否则无解。话虽这么说，请考虑段
[PQ]和[RS]，其中P、Q、R和S是平面上的点。您需要线段的交集：[PQ][RS][QP][RS][PQ][SR][QP][SR][RS][PQ][SR][PQ][RS][QP][SR][QP]...始终返回相同的坐标对。
首先对每个段上的端点进行排序，然后对段本身进行排序（基于每个段的最小端点），这是保证可重现结果的唯一解决方案。排序本身在计算上可能是微不足道的，例如
P当且仅当 Px<<。 Qx || Px == Qx && py < Qy，尽管如果处理数百万个段，分支可能会变得昂贵（如果可能的话，请参阅如何利用 SIMD 就地交换段坐标来生成排序。）You do not want to compare segment lengths.
Also, I assume that when comparing
intersection(A',B')tointersection(B",A")it is understood thatA''s coordinates are representationally identical toA"'s (idem forB'andB"), or else there is no solution.This being said, consider segments
[PQ]and[RS], whereP,Q,RandSare 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<QiffP.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.)