寻找一个不在任何旋转矩形内的点

Question

我正在寻找一种算法，可以快速（由于性能受到严格限制）找到一个圆内的点，其中此点在提供的矩形集合中都在外部（这些矩形可能会旋转）。或者，查找一个圆A，其中心位于圆B内部，其中圆A不与一组线段相交。

我能想到的唯一解决方案就是循环遍历样本点，然后为每个样本点循环遍历矩形。但由于我的空间是连续的，所以这非常麻烦。我基本上满意的是只有一个不相交的点，但也会有没有这样的点存在的情况。在后一种情况下，我理想地会尝试找到具有最少交点的点，或者能够找到不存在这样的点的答案。

有人知道任何可以在小于O(n^2)的时间内完成此任务的算法吗？任何有助于识别好的候选点的东西都很棒。

典型的情况是：许多大矩形，其中希望找到一个点的小圆圈（这里用蓝色表示）。许多矩形完全落在圆圈外面，圆圈完全被覆盖也很常见。通常仅使用一小组长度和宽度的矩形。

- AnythingElse

---

你能进行预处理吗？你可以展示一张典型情况下的图片吗？ - harold

在 OP 中添加了一张典型图片。我认为很少有预处理可以做，因为矩形始终在波动。重计算也不太可能。 - AnythingElse

如果仅保留一个记录哪些网格单元完全没有矩形的细网格（或更好的四叉树）会消耗太多内存，我会通过多边形来近似圆形，并将其“剪辑”到所有附近的矩形上（您可以使用更粗糙的网格来查找所有需要剪辑的矩形）。 如果剪辑后仍有任何区域剩余，则可以选择其内部的任何点（请注意，其顶点的平均值不一定保证在其中，因为剪辑后的残留物不一定是凸的，但当它是凸的时这将是一个不错的选择）。 - j_random_hacker

哎呀，夹取（clipping）能否以良好的性能完成呢？至少需要考虑圆被分成两部分的情况。 - AnythingElse

听起来在某些情况下可能是可行的解决方案。不幸的是，对于我的情况来说，可能仍然太重了，因为弄清楚哪些网格部分要涂色以形成矩形似乎与检查一堆点是否包含在矩形中并没有太大区别。 - AnythingElse

Answer 1

这个问题可能有很多有趣的解决方法。我能想到的最简单的算法是以下算法，它能够得到一个不错的运行时间：

1. 将所有矩形视为线段集。
2. 使用高效算法找到所有线段的交点（例如Bentley-Ottmann算法）。
3. 创建一个感兴趣点（POI）列表，这些点要么是矩形的角落，要么是在步骤2中计算出的交点。
4. 创建一个更细的线段集，使得每个线段都以3中定义的POI为终点。
5. 使用步骤4中的POI和更细的线段集，计算受限制的三角剖分（例如约束Delaunay三角剖分）。
6. 选择任意（未标记的）三角形作为起点。确定该三角形是否位于至少一个矩形内（将其标记为COVERED三角形），或者不在任何矩形内（将其标记为FREE三角形）。为此，您可以使用任何点在多边形内算法，例如射线投射。
7. 从该三角形开始运行深度或广度优先搜索，并扩展到邻居，注意不要穿过需要跨越4中定义的线段的任何三角形对之间的线段。对于访问的每个三角形，将其标记为与起始三角形相同的标签。
8. 重复6-7，直到所有三角形都被标记（或所有覆盖感兴趣圆的三角形都被标记）。

所有自由三角形的并集与感兴趣的圆相交，恰好得到那些既不被任何矩形覆盖且在圆内的点。

请注意，此算法有些通用，可以通过仅关注圆周围的区域来改进（例如，只考虑一个边界框区域，该边界框包含所有与圆相交的矩形）。

要分析运行时间，请考虑每个关键步骤的运行时间：

• 2. 具有 O((n+k) log n) 的运行时间，其中 k 是交点数量，n 是线段数量。
• 5. 具有 O(m log m) 的运行时间，其中 m 是 POI 数量，m 是 O(n+k)。
• 6. 7. 应与 6. 一起分析。在最坏情况下，每个三角形需要 O(n) 计算以检查其是否被包含在矩形中。鉴于可能会有 O(m) 个三角形，这将产生 O(nm) 的上限。但是，三角剖分的目的是重复使用点和多边形计算来标记尽可能多的相邻三角形。在实践中，需要进行点和多边形计算的三角形数量应该可以忽略不计。因此，此步骤的运行时间为 O(tn)，其中 t 是执行点和多边形计算的三角形数。

运行时预期为O((n+k) log n + t(n+k))，其中k是第2步中的交点数量，t是执行点在多边形计算的三角形数量。在最坏情况下，这是O(n^2 log n)，因为您可以创建一个具有n^2交点的病态示例，但如果不可能的话，这应该是不太可能的。同样，应尽量将t的数量保持最少，以使其尽可能高效。如果t << n且k << n^2，则这将非常高效。

一种可能会提高性能的近似方法：

- 考虑通过一组r条线段来近似圆，并将这些线段包含在步骤1-5中。虽然这是一种近似，但它有可能提高运行时间，因为只有圆内部的三角形才需要考虑。

- ldog