optimization - 寻找一种有效的结构来检查哪些圆圈包围了一个点

Question

我有一大组重叠的圆圈，每个圆圈都位于具有特定半径的随机位置。

type Circle =
    struct 
      val x: float
      val y: float
      val radius: float
    end

给定一个带有类型的新点

type Point =
    struct
      val x: float
      val y: float
    end

我想知道我的集合中的哪些圆圈包围了新点。线性搜索是微不足道的。我正在寻找一种结构，它可以容纳圆圈并返回比 O(N) 更好的封闭圆圈。

理想情况下，该结构应该能够快速插入新圆圈和移除圆圈。

我想在 F# 中实现它，但任何语言的想法都可以。

为了您的信息，我正在寻找实施

但如果我使用简单的方法扫描所有圆圈以查找每个新点，那将是 O(N^2)。

score 2 · Accepted Answer

四叉树是一种高效平面搜索的结构。您可以使用它来保持平面的细分。

例如，您可以创建具有以下属性的四叉树： 1. 四叉树的每个单元格都包含圆圈的索引，并与其重叠。2. 每个单元格包含不超过 K 个圆圈（例如 10 个）// 可能会损坏 3. 树的高度以 M 为界（通常为 O(log n)）

您可以通过迭代重叠的单元格来构造四叉树，如果单元格内的圆数超过 K，则将该单元格细分为四个（如果不超过最大高度）。如果单元格在圆圈内，也应该考虑一些事情，因为它的细分是没有意义的。

查找圆时，您应该定位四叉树，然后遍历重叠的圆并找到包含点的圆。

在稀疏圆分布的情况下搜索将非常有效。

我有一个学士论文，我在其中调整了四叉树，用于最近的段位置，预期时间为 O(log n)，我认为可以在这里使用类似的方法

score 2 · Accepted Answer

如果我们假设圆分布在某个面积为矩形的矩形上，1而一个圆的平均面积是a一个四叉树，那么带有m层的四叉树将为您留下一个大小为的面积1/2^m。这离开

O(Na/2^m)

作为剩余区域中剩余的预期圆圈数。

但是，我们已经进行了O(log(m))比较以达到这一点。这使得比较的总数为

O(log(m)) + O(N/2^m)

log(m)如果与成比例，则第二项将是常数N。

这表明四叉树可以将事物缩减到O(log n)

score 1 · Accepted Answer

实际上，您搜索其外接圆包含新点 p 的三角形。因此，您的 Delaunay 三角剖分已经是您需要的数据结构：首先搜索包含 p 的三角形 t（谷歌搜索“delaunay walk”）。t 的外接圆当然包括 p。然后从 t 开始，增大外接圆包括 p 的三角形的（连通）面积。

以快速可靠的方式实施它需要大量工作。除非您想创建一个新库，否则您可能需要使用现有库。我的 C++ 方法是 Fade2D [1]，但还有许多其他方法，这取决于您的具体需求。

3 回答 3