尋找一個有效的結構來檢查哪個圓圈包圍一個點

我有一大堆重疊的圓，每個圓都在一個具有特定半徑的隨機位置。尋找一個有效的結構來檢查哪個圓圈包圍一個點

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）。

什麼某種改性四叉樹的。那麼你可以做O（log n） – 2013-04-04 08:46:20

是的，但是四叉樹是用於不與幾何對象重疊的點。我不知道如何繼續。 – bradgonesurfing 2013-04-04 08:47:36

你至少可以將事物縮小到與地區重疊的一小部分圓圈。 – 2013-04-04 08:48:27

如果我們假設界分佈在一些矩形面積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)

2013-04-04 09:01:21

四叉樹是有效的基本面搜索的結構。你可以用它來保存飛機的細分。

例如，您可以創建具有以下屬性的四叉樹： 1.四叉樹的每個單元格都包含圓圈索引，並與它重疊。 2.每個細胞確實含有不於K圓圈（例如，10）更//可能被打破 3.樹的高度由M爲界（通常爲O（log n））的

可以構建四叉樹，由迭代重疊的單元格，如果單元格內的圓圈數量超過K，則將該單元格細分爲四個（如果不超過最大高度）。對於圓圈內的單元格也應該考慮一些事情，因爲它的細分是毫無意義的。

找到圓時，應該對四叉樹進行本地化，然後遍歷重疊的圓圈並找到包含點的圓。

如果稀疏圓分佈搜索將非常有效。

我有一個學士論文，我在那裏適應四叉樹，爲最接近段的位置，與預期時間O（log n）的，我想類似的方法可以在這裏使用

2013-04-04 09:03:50 kassak

圓形分佈將是重疊的圓是delaunay三角形的外接圓。這是否有所作爲？ – bradgonesurfing 2013-04-04 14:31:32

@bradgonesurfing爲什麼你不能找到delaunay三角剖分？我認爲在三角形的三角形處可以找到包含外接圓的外接圓，與三角形共享點。 – kassak 2013-04-04 14:48:21

@bradgonesurfing另外我認爲你的案例對於算法在答案中沒有那麼壞。在度數> K的三角頂點處可以達到最大的細分。但是，沒關係，在頂點附近，你不會做任何事情都不會比通過事件圓圈進行迭代=） – kassak 2013-04-04 14:57:02

其實你搜索的三角形，其外接圓包括新的點p。因此，您的Delaunay三角剖分已經是您需要的數據結構：首先搜索包含p的三角形t（「delaunay walk」）。 t的外接圓肯定包括p。然後從t開始，生長外接圓包含p的三角形（連接）區域。

以一種快速可靠的方式實現它是一項很多工作。除非你想創建一個新的庫，否則你可能想使用現有的庫。我的C++方法是Fade2D [1]，但也有很多其他方法，這取決於您的具體需求。

2013-04-04 13:14:32 Geom

回答