Matlab: Algorytm dla diagramu voronoi elipsy

Question

Czy istnieją jakieś algorytmy do implementacji diagramu Voronoi, który ogranicza elipsy? Schemat będzie wyglądał jak na zdjęciach tutaj voronoi diagram of ellipses

Czy ktoś może podzielić się linki, tutoriale, kody itp z nim związane?

Z góry dziękuję.

Answer 1

Oto algorytm, który wykorzystuje distance transform wraz z algorytmem z watershed narysować diagram Voronoi dla elips.

%# 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

Nie wiem, co masz na myśli mówiąc "elipsy" tutaj. Ale jest wdrożenie do diagramów Voronoi w języku C++ Stephan Fortune/Shane O'Sullivan,

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

Answer 3

Tylko w przypadku, jest to przykład z systemu pomocy Mathematica:

(*Generate ellipses*) 
p= Rasterize@Graphics@Table[ 
      Rotate[ 
       Disk[RandomReal[10, 2],   (*Rnd position*) 
        RandomReal[{.3, 1.5}, 2]], (*Rnd radii*) 
      RandomReal[Pi]], {i, 10}]   (*Rnd rotation*) 

(*Compute Voronoi*) 

LaplacianGaussianFilter[DistanceTransform[p], 2] // ImageAdjust 

To nie jest dokładna kalkulacja, ale na tyle sprawiedliwe dla praktycznych zastosowań.

Answer 4

Na podstawie ostatnich pytań, rozumiem, że pracujesz nad rysowaniem elips na zdjęciach RGB. Chciałbyś móc określić położenie, kształt i kolor elips. Chcesz, by elipsy były na granicach, a także non-overlapping. Teraz szukasz narysować linie, które dzielą przestrzeń w sposób podobny do diagramów Voronoi (ale z elipsami zamiast punktów).

Dla tego konkretnego pytania, jak pokazało @Jonas, rozwiązaniem jest użycie transformacji odległości wraz z algorytmem działu wodnego.

Pomyślałem, że kontynuuję mój poprzedni przykład i rozszerzam go o pomysł Jonasa, aby zaprezentować cały proces. Mam nadzieję, że okaże się przydatny ..

Kod wykorzystuje funkcję calculateEllipse do obliczania współrzędnych punktów składających się na elipsę, a także funkcję imoverlay do ustawiania określonych pikseli obrazu na wybrany kolor.

%# 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')