algorithm - 相交 n 条线段(在整数网格上)

Question

我有一个问题看起来几乎像一个经典的 CS 问题，即找到给定线段的所有交点。

稍作修改的事实是:
1. 我需要在交点处拆分所有线段
2.生成的分割线段必须具有整数坐标。

如果我只是应用标准扫掠线算法来找到所有交点，而不是将这些点的坐标转换为整数，我有时会因为交点移动到整数网格而得到新的交点。

我可能会重复应用此算法，并且可能(我无法证明)在有限的步数内达到我找不到新交叉点的状态。但我相信一定有更简单、更优雅的解决方案。

我试图找到一篇关于这种算法的论文，但不知何故找不到能够准确解决这个问题的论文。

你能告诉我这样一篇论文，或者图形库(例如 Boost Polygon Library)使用的算法的描述吗？

谢谢。

Answer 1

这是线段相交问题的一个有趣变体。寻找这些线段交点坐标的原始问题可以使用线扫描算法来解决。

Here是一篇深入讨论上述问题的线扫描技术实现的文章。这样，就可以在 O(n*logn) 时间内找到交集。

现在，为了找到整数坐标，您可以计算交点。但是在这里你需要确定类型转换的方向(这将有助于收敛)。

如果C在线段AB上的交点，则将其拆分为AC和CB。在 AC 中，您将 C 转换到 A 的方向，而在 CB 中，您将其转换到 的方向>B。 (方向不是指沿线段方向，而是指沿包含另一个端点的半平面。)这样可以保证每次相交后线段的长度都会减少。

证明: 考虑，M 是线段的最大长度。每有一个交点落在其上，新线段的长度至少减少一个单位。所以迭代次数受 M
限制因此，您的算法的总迭代次数不能超过 M。

复杂度 = O(M* n *logn)