生成點不在對方範圍內？

我正在嘗試生成一組不落在彼此的範圍內的固定區域。我的方法如下：生成點不在對方範圍內？

import collections 
from random import uniform 

X = 100.0 
Y = 100.0 
points = 10 
radius = 10 

def in_circle(c_x, c_y, radius, x, y): 
    dist_squared = (c_x - x)**2 + (c_y - y)**2 
    return dist_squared <= radius ** 2 

current = collections.defaultdict(lambda: []) 

threshold = 0  

for point in range(1, points+1): 
    cX = uniform(1.0, X) 
    cY = uniform(1.0, Y) 

    for cur in current: 
     while in_circle(current[cur][0], current[cur][1], 2*radius, cX, cY): 
      cX = uniform(1.0, X) 
      cY = uniform(1.0, X) 

      threshold += 1 
      if threshold >= 1e+05: 
       print "Cannot satisfy constraints" 
       sys.exit(1) 

    threshold = 0 

    current[point] = [cX, cY] 
    print cX, cY

有沒有一種很好的方法來終止這種算法，而不會進入無限循環？我確實有門檻檢查，但有沒有更好的方法來做到這一點？

來源

2011-10-28 Legend

This article約泊松盤採樣可能是有趣的你。作者解釋了選擇彼此不太接近的點的策略，甚至用幾種語言提供了示例代碼，包括Python。

正如你所提到的，你列出的策略存在的問題是，如果你想選擇很多點，或者你希望點距離很遠，那麼表現可能會變得非常糟糕。我相信，泊松盤方案具有更好的性能特點。

來源

2011-10-28 11:13:08

你能把這個區域細分成正方形嗎？side> =最小允許距離之間的距離，然後隨機挑選其中的幾個？

例如，這些都是你的觀點 - 約束廣場「編號爲」從0到J：

0 1 2 3 4 
5 6 7 8 9 
a b c d e 
f g h i j

然後你（在本例中爲0至j）使廣場索引數組，randomly shuffle it，以bc4j25e1670dfgh89ai3結尾，並從最開始的多個指數開始，例如您需要的點數，例如5：bc4j2。然後您將在選定的正方形的中心（或者左上邊角）你的觀點：

0 1 * 3 * 
5 6 7 8 9 
a * * d e 
f g h i *

來源

2011-10-28 11:11:19

這類問題被稱爲circle packing。關於數學世界的文章指出已知密度最大的單位正方形的填料（這個問題可以通過縮放x和y來轉化爲那個問題）。該文章中的圖像展示了兩個密集球形填料（正方形和六邊形）。

至於是否可以插入一個新的圓圈，voronoi diagram有可能用作最大剩餘未採樣面積的度量值。在某些情況下，評估諸如四叉樹或空間散列的未佔用區域的其他近似方法也可能是足夠的

來源

2011-10-28 11:15:35

生成點不在對方範圍內？

回答

相關問題