3

我正在尝试找到一种算法，该算法将找到一组线的所有交点，并在 O(n log n) 时间内计算包含所有交点的最小矩形。到目前为止，我猜测它与对偶性和凸包有关，但我有点坚持它实际上如何帮助我解决这个问题。

如果有人对此有任何想法，请告诉我。谢谢 ：）

4

2 回答 2

3

让我们从一个最小限制三角形中三个交点的框 B[0] 开始。

如果找不到三角形，那么我们有以下特殊情况之一，可以单独处理：

  1. 所有的线都是平行的。
  2. 所有的交叉点都在一条线上。如果除一条之外的所有线都是平行的，则可能会发生这种情况。
  3. 所有线相交于一个点。

所以让我们忽略这些情况作为细节并假设可以找到一个三角形并且找到它不会给算法增加太多时间。

第 1 阶段 - 扩大框以包含每条线的一个交叉点：

  1. 标记形成初始三角形的三条线。
  2. 选择一条未标记的线，并找到与标记线的交点 P。这始终是可能的，因为至少存在三个不相互平行的标记线。
  3. 扩大框以包含 P。
  4. 从 2 开始重复，直到所有行都被标记，即它们都在框中至少有一个交点。

调用结果框 B[0]。

第 2 阶段 - 检测线是否在框外有交叉点：

这是关键的观察：对于在盒子内相交的两条线 A 和 B，顺时针绕盒子走，我们会遇到交替的线：例如 ABA B。对于在盒子外相交的两条线，顺时针走不交替：例如 ABB A. 当然也有可能是线在box边界上相交，或者是并发的，但是在描述了主要算法之后会作为一个细节来处理。

  1. 选择线条的方向：如果线条不水平，让线条指向 +y 方向，让水平线条指向 +x 方向。线作为箭头的一件事，然后箭头都被选择为尽可能多地指向，或者如果它们是水平的，则指向右侧。有了这个方向，每条线都有一个进入盒子的点（定向线指向盒子的地方，还有一个出口点。这些可能是同一个点。
  2. 通过绕边界顺时针方向走 EXITING 交叉点，从右上角开始，创建线路的“退出序列”。
  3. 通过从框的右上角开始顺时针走 ENTERING 交叉点来创建线条的“输入序列”。
  4. 如果所有交点都在盒子内部，则进入和退出序列将相互循环，B[i] 是交点的最小边界框。
  5. 否则，将两个序列对齐到任意元素（通过循环旋转）。
  6. 在序列中找到它们首先不同的元素。这两条线必须在框外有一个交点 P，因此通过增加 B[i] 以包含 P 来形成 B[i+1]。
  7. 从 2 开始重复。

这并不完整，因为如果组线在边界上有一个共同的进入点或退出点，则进入和退出序列没有明确定义。对于具有公共入口或出口点的每组线 L，请使用稍大的框来订购 L。

请注意，此算法不会发出所有的交叉点，但它确实保证（我希望）盒子包含所有交叉点。

于 2012-06-11T09:35:56.970 回答
1

在 O(n log n) 时间内？哇。我没想到这是可能的。

我在这里没有看到任何其他答案，所以这里有一个想法——诚然，在黑暗中开枪。你可以随心所欲。

想法：首先按方位或坡度对线条进行排序。在其他条件相同的情况下，几乎平行的线似乎很可能在偏远点相交；当然，您感兴趣的是外围点。

您的凸包想法听起来应该是正确的，但考虑到凸包可能具有几乎平行的边，其切线或延伸与感兴趣的区域相交很远。总而言之，这听起来像是一项主要的编程工作。祝你好运。

于 2012-06-09T00:43:51.177 回答