algorithm - Matlab: 楕円のボロノイ図のアルゴリズム

Question

楕円を囲むボロノイ図を実装するアルゴリズムはありますか? 図は、ここの写真のようになります楕円のボロノイ図

それに関連するリンク、チュートリアル、コードなどを共有できますか?

前もって感謝します。

Answer 1

これは、距離変換と流域アルゴリズムを組み合わせて楕円のボロノイ図を描画するアルゴリズムです。

%# first, define some ellipses (for simplicity, I use 0/90 orientation)
ellipses = [10,20,5,10;30,10,10,7;40,40,8,3];

%# put the ellipses into an image (few pixels, therefore pixelated)
img = false(50);
[xx,yy]=ndgrid(1:50,1:50);
for e = 1:size(ellipses,1),img = img | (xx-ellipses(e,1)).^2/ellipses(e,3)^2 + (yy-ellipses(e,2)).^2/ellipses(e,4)^2 <= 1;end

%# perform the distance transform
dt = bwdist(img);

%# apply the watershed algorithm. 
%# ws==0 are the lines for the Voronoi diagram
ws = watershed(dt);

%# create a RGB image and display
%# note: for yellow lines, replace the last
%# "ws==0" by "zeros(size(ws))", so that you
%# only put ws into the red and green channel (=yellow)
rgb = cat(3,ws==0,ws==0,ws==0)); 
%# add the ellipses into the red channel
rgb(:,:,1) = rgb(:,:,1) | img;
imshow(rgb)

Answer 2

最近の質問の追跡に基づいて、RGB 画像の上にラスタライズされた楕円を描画することに取り組んでいることを理解しています。楕円の位置、形状、色を指定できるようにしたいと考えています。楕円を境界でクリップし、重なり合わないようにしたいと考えました。ここで、ボロノイ図に似た方法で空間を分割する線を描画しようとしています (ただし、点ではなく楕円を使用します)。

@Jonasが示したように、この特定の質問の解決策は、距離変換を流域アルゴリズムと一緒に使用することです。

前の例を続けて、Jonas のアイデアで拡張し、プロセス全体を紹介したいと思いました。お役に立てば幸いです..

このコードでは、このcalculateEllipse関数を使用して、楕円を構成する点の座標を計算したりimoverlay、画像の指定したピクセルを選択した色に設定したりする関数を使用します。

%# color image (canvas to draw on)
I = imread('pears.png');
sz = size(I);

%# random ellipses
num = 20;
centers = bsxfun(@times, rand(num,2), sz([2 1]));   %# center x/y-coords
radii = bsxfun(@times, rand(num,2), [300 50])+10;   %# major/minor axis length
angles = rand(num,1) .* 360;                        %# angle of rotation
ex = cell(num,1);                                   %# vertices x-coords
ey = cell(num,1);                                   %# vertices y-coords

%# label image, used to hold rasterized ellipses
L = zeros(sz(1),sz(2));

%# randomly place ellipses one-at-a-time, skip if overlaps previous ones
flag = false(num,1);
for i=1:num
    %# ellipse we would like to draw directly on image matrix
    [ex{i},ey{i}] = calculateEllipse(centers(i,1),centers(i,2), ...
        radii(i,1),radii(i,2), angles(i), 100);

    %# create mask for image pixels inside the ellipse polygon
    mask = poly2mask(ex{i},ey{i}, sz(1),sz(2));

    %# check if there is no existing overlapping ellipse
    if all( L(mask)==0 )
        %# use the mask to place the ellipse in the label image
        L(mask) = sum(flag)+1;    %# assign value using an increasing counter
        flag(i) = true;
    end
end

%# filter ellipses to only those that made through the overlap test
num = sum(flag);
centers = centers(flag,:);
radii = radii(flag,:);
angles = angles(flag);
ex = ex(flag);
ey = ey(flag);

%# rasterized voroni diagram of the ellipses [Jonas]
E = (L ~= 0);                             %# ellipses as binary image
WS = watershed( bwdist(E) );              %# distance transform + watershed
WS = (WS == 0);                           %# WS==0 corresponds voronoi diagram
WS = bwmorph(WS, 'thicken',1);            %# thicken the lines

%# set pixels corresponding to voronoi diagram to white
II = I;
II = imoverlay(II, WS, [1 1 1]);          %# you can customize the color here

%# set pixels corresponding to ellipses using specified colors
clr = hsv(num);                           %# color of each ellipse
for i=1:num
    mask = bwperim(L==i,8);               %# get perimeter of the ellipse mask
    mask = bwmorph(mask, 'thicken',1);    %# thicken the ellipse perimeter
    II = imoverlay(II, mask, clr(i,:));   %# set those pixels with RGB color
end

%# show final rasterized image (image + ellipses + voronoi diagram)
figure, imshow(II, 'InitialMagnification',100, 'Border','tight')

Answer 3

ここでの「楕円」の意味がわかりません。しかし、Stephan Fortune / Shane O'Sullivan による C++ のボロノイ図の実装があります。

http://www.skynet.ie/~sos/mapviewer/voronoi.php