Voronoi diagram

Voronoi diagram是一種圖，指的是離某一物體最近點的集合。下圖中綠色部分離其中的黑點最近，這一部分所有點離其他的黑點都比之遠。圖中的紅色線是離兩個黑點（叫site）同樣遠點組成的。Voronoi diagram在自動假設的路徑規劃中有著比較好的運用。

我給出一段Matlab代碼實現離散空間的Voronoi diagram求法，所謂離散空間就是不是所有點都能取得只有固定網格上的點才能取得的，如果照片，只有若干個像素點，像素點的位置不是任意的，而是分布在一定的網格上。

global DistTable Grids OpenList%% Define a structureGridCell.Pos = [0,0];GridCell.Parent = [0,0];GridCell.Dist = Inf;GridCell.Distnew = Inf;GridCell.ObstIdx = 0;GridCell.isObst = false;%% InitializationOpenList = [];rows = 100;cols = 100;raw = zeros(rows,cols);Grids = cell(rows,cols);out = raw;DistTable = raw;raw(1,1) = 1;raw(30,30) = 2;raw(100,100) = 3;raw(10,50) = 4;for i = 1:rows for j = 1:cols DistTable(i,j) = norm([i,j]-[1,1]); tg = GridCell; tg.Pos = [i,j]; if raw(i,j) ~= 0 tg.Parent = [i,j]; tg.Distnew = 0; tg.ObstIdx = raw(i,j); tg.isObst = true; OpenList = [OpenList; i, j]; end Grids{i,j} = tg; endend%% Update distancewhile(1) workCell = Grids{OpenList(1,1),OpenList(1,2)}; if workCell.Distnew < workCell.Dist workCell.Dist = workCell.Distnew; Propagate(workCell); end dim = size(OpenList); if dim(1) >= 2 OpenList = OpenList(2:end,:); else break endendfor i = 1:rows for j = 1:cols tg = Grids{i,j}; if tg.isObst == false out(i,j) = tg.ObstIdx; end endendimagesc(out)function Propagate(workCell)global Grids DistTable OpenListfor i = -1:1 for j = -1:1 adjCellIdx = workCell.Pos+[i,j];% If is valid idx of grid and not the same idx as workCell itself if (sum(adjCellIdx >= [1,1]) == 2) && ((sum(adjCellIdx <= size(Grids)) == 2)) && (norm([i,j]) ~= 0) adjCell = Grids{adjCellIdx(1),adjCellIdx(2)}; if adjCell.Distnew > workCell.Distnew tIdx = abs(adjCellIdx - workCell.Parent)+[1,1]; tDist = DistTable(tIdx(1),tIdx(2)); if tDist < adjCell.Distnew adjCell.Distnew = tDist; adjCell.Parent = workCell.Parent; adjCell.ObstIdx = workCell.ObstIdx; Grids{adjCellIdx(1),adjCellIdx(2)} = adjCell; OpenList = [OpenList;adjCellIdx]; end end end endendend

上圖是運行結果，圖中共設置了四個site，得到了四個區域。詳細以後再填坑吧。

下面給出一個動畫來展示Voronoi diagram的生成過程，注意一開始有4個site，但是中途移除了右下角的site，Voronoi diagram又生成一次，但是是增量生成的，沒有全部更新一次，這節省了計算量和時間。但是增量生成的過程沒有在上面體現，等什麼時候有時間了再不上詳細過程吧。

https://www.zhihu.com/video/980968427606945792
推薦閱讀：