境界が重ならない閉じた曲線の中に点を均等に分配するための高速アルゴリズム

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

重心ボロノイの表記法[1,2]を使用することができます。次のように アルゴリズムは動作します：私は研究開発をしていますGEOGRAMライブラリで実装があり

(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 

[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