小编Any*_*lse的帖子

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

我能想出的唯一解决方案是循环遍历点的样本，然后遍历每个点的矩形。但是因为我的空间是连续的，所以很痛苦。我基本上只对一个不相交的点感到满意，但也会有不存在这样的点的情况。在后一种情况下，我最好尝试找到一个交叉点最少的点，或者能够找到不存在这样的点的答案。

有谁知道有什么算法可以在小于 O(n^2) 的时间内完成这个任务？任何有助于确定好的候选点的东西也会很棒。

这种情况的一个典型例子是：很多大矩形和小圆圈，我希望在其中找到一个点（这里用蓝色表示）。许多矩形完全落在圆之外是很常见的，而且圆被完全覆盖也是很常见的。只有一小组长度和宽度往往用于矩形。