2

当使用常用公式计算两个 2D 线段之间的交集时，即此处，如果将结果四舍五入为整数，则会得到非对称结果。

也就是说，有时，由于舍入错误，我得到了intersection(A,B)!=intersection(B,A).

最好的解决方案是继续使用浮点数，并将结果比较到一定的精度。但是，我必须在计算交点后将结果舍入为整数，我不能继续使用浮点数。

到目前为止，我最好的解决方案是在飞机的各个部分上使用一些完整的顺序，并且必须intersection始终将较小的部分与较大的部分进行比较。

有没有更好的方法？我错过了什么吗？

4

1 回答 1

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<Qiff P.x < Q.x || P.x == Q.x && P.y < Q.y，尽管如果处理数百万个段，分支可能会变得很昂贵（如果可能的话，请参阅如何利用 SIMD 就地交换段坐标以生成排序。）

于 2010-04-11T05:50:06.603 回答