Matlab: Thuật toán cho sơ đồ voronoi của các hình elip

Question

Có bất kỳ thuật toán nào để thực hiện sơ đồ Voronoi gắn các dấu ba chấm không? Sơ đồ sẽ trông giống như hình ảnh ở đây voronoi diagram of ellipses

bất cứ ai có thể chia sẻ một số liên kết, hướng dẫn, mã vv liên quan đến nó?

Xin cảm ơn trước.

Answer 1

Dưới đây là một thuật toán có sử dụng các distance transform cùng với các thuật toán watershed để vẽ một sơ đồ Voronoi cho elip.

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

Tôi không biết ý bạn là gì với "dấu ba chấm" ở đây. Nhưng có một thực hiện cho sơ đồ Voronoi của trong C++ bởi Stephan tạp chí Fortune/Shane O'Sullivan,

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

Answer 3

Chỉ trong trường hợp, đây là một ví dụ từ Mathematica hệ thống trợ giúp:

(*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 

Nó không phải là một tính toán chính xác, nhưng đủ công bằng cho các mục đích thực tế.

Answer 4

Dựa trên các câu hỏi gần đây của bạn, tôi hiểu rằng bạn đã làm việc để vẽ các hình elip có kích thước rasterized hình elip trên đầu hình ảnh RGB. Bạn muốn có thể chỉ định vị trí, hình dạng và màu sắc của hình elip. Bạn muốn các dấu ba chấm là clipped ở ranh giới và cũng có thể là non-overlapping. Bây giờ bạn đang tìm cách vẽ các đường phân chia không gian theo cách tương tự như sơ đồ Voronoi (nhưng với các dấu ba chấm thay vì các điểm).

Đối với câu hỏi cụ thể này, như @Jonas cho thấy, giải pháp là sử dụng phép biến đổi khoảng cách cùng với thuật toán lưu vực.

Tôi nghĩ rằng tôi tiếp tục với ví dụ trước của mình và mở rộng nó với ý tưởng của Jonas, để giới thiệu toàn bộ quá trình. Hy vọng bạn sẽ thấy nó hữu ích ..

Mã sử ​​dụng chức năng calculateEllipse để tính toán tọa độ của các điểm tạo thành hình elip, cũng như chức năng đặt các pixel được chỉ định của hình ảnh cho một số màu được chọn.

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