algorithm - 检查直线形状的有效性

Question

给定一个直线形状，我如何有效地检查它是否有效 并指出无效的部分？

这里的validity是指宽度约束，即形状的每一部分 宽度应不小于某个值 d。正式地， 如果从形状的顶部到底部垂直扫过一条线，则所有 线和形状之间的交叉点的长度不应小于 d。 纵向情况类似。 (请注意，形状内部可能有孔。但为了简单起见， 我们可以先忽略它。)

任何人都可以建议一个有效的算法或向我展示一些解决此问题的方法吗？

Answer 1

我认为您可以使用相当典型的扫描线方法来解决这个问题。

首先考虑水平扫描线，从图形的顶部扫描到底部。观察扫描线穿过的宽度只能在它穿过垂直线段的端点时发生变化。

所以对于水平扫描线，可以忽略水平线段。获取垂直线段的所有端点并按其垂直位置对它们进行排序。 (每个端点都知道它是其段的“顶部”端点还是“底部”端点)。

处理排序列表以模拟扫描线。维护一个“事件集”S，初始化为空。当您击中“顶部”端点时，将其段添加到 S。当您击中“底部”端点时，从 S 中删除其段。验证事件集的宽度是否始终满足您的约束，您就完成了。

使用平衡二叉树(如 C++ std::set)来表示事件集，使用水平位置作为比较功能。这允许 O(1) 检索集合中最左边和最右边的段，因此宽度计算为 O(1)。它还允许 O(log n) 的插入和删除，并且由于您只插入和删除每个垂直线段一次，因此整个扫描需要 O(n log n)。

垂直扫描线对称重复。

每次排序是 O(n log n)，每次扫描是 O(n log n)，每个方向乘以两倍...所以整个算法是 O(n log n)。