快速算法用於在具有不重疊邊界的閉合曲線內均勻分佈點

Question

問題是我需要在任意形狀的辦公室中分配一些人。每個人的要求是一樣的：儘可能遠離辦公室的牆壁和其他人。

將辦公室視爲空白圖像。因此，分配人員就像在圖像上分配點。

我想通了，該算法很慢：

for each people 
    do distance transform of the image 
    find a point that has the largest distance value 
    place a people here 
    mark the pixel where the people is as False in the image 

的算法並距離變換幾次地方的人反覆。

當有很多人時，算法變得非常慢，比如說距離變換的迭代使用500。我想知道是否有更好的算法或任何想法，我可以優化當前的算法？謝謝

Answer 1

你可以使用質心Voronoi tesselation [1,2]。 該算法的工作原理如下：

(1) distribute the points randomly in the office 
(2) Repeat until you are satisfied: 
    (2.1) compute the Voronoi diagram (see [3]) of the points 
    (2.2) compute the barycenter of the Voronoi cell of each point 
    (2.3) move each point to the barycenter of its Voronoi cell 

有一個在GEOGRAM庫，我深化發展的實現[4]。另見我的朋友開發的CGAL圖書館[5]。

[1] https://en.wikipedia.org/wiki/Centroidal_Voronoi_tessellation

[2] https://en.wikipedia.org/wiki/Lloyd%27s_algorithm

[3] https://en.wikipedia.org/wiki/Voronoi_diagram

[4] http://alice.loria.fr/software/geogram/doc/html/index.html

[5] http://www.cgal.org