Path: news.mathworks.com!not-for-mail
From: "Damian Sheehy" <Damian.Sheehy@mathworks.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Voronoi diagram on a sphere
Date: Fri, 6 Nov 2009 09:00:57 -0500
Organization: The MathWorks, Inc.
Lines: 68
Message-ID: <hd1a6r$rq0$1@fred.mathworks.com>
References: <hd0e8h$c9$1@fred.mathworks.com>
Reply-To: "Damian Sheehy" <Damian.Sheehy@mathworks.com>
NNTP-Posting-Host: sheehyd.dhcp.mathworks.com
X-Trace: fred.mathworks.com 1257516059 28480 172.31.44.102 (6 Nov 2009 14:00:59 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 6 Nov 2009 14:00:59 +0000 (UTC)
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2900.5843
X-RFC2646: Format=Flowed; Original
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.5579
Xref: news.mathworks.com comp.soft-sys.matlab:583006


Hi Abel,

If you have release in R2009a or later, the computational geometry tools 
make this task relatively easy.
The Voronoi diagram is the dual of the Delaunay triangulation; the 
triangulation lying on the on the surface of the sphere.

% Create the points on the surface of the sphere
theth_a = 2*pi*rand(100,1);
phi = pi*rand(100,1);
x = cos(theth_a).*sin(phi);
y = sin(theth_a).*sin(phi);
z = cos(phi);

% Create a Delaunay triangulation of the point set.
% This is a solid triangulation composed of tetrahedra.
dt = DelaunayTri(x,y,z);

% Extract the surface (boundary) triangulation, in this instance it is 
actually the convex hull
% so you could use the convexHull method also.
ch = dt.freeBoundary();

% Create a Triangulation Representation from this surface triangulation
% We will use  it to compute the location of the voronoi vertices 
(circumcenter of the triangles),
% and the dual edges from the triangle neighbor information.

tr = TriRep(ch,x,y,z);
numt = size(tr,1);
T = (1:numt)';
neigh = tr.neighbors();
cc = tr.circumcenters();
xcc = cc(:,1);
ycc = cc(:,2);
zcc = cc(:,3);
idx1 = T < neigh(:,1);
idx2 = T < neigh(:,2);
idx3 = T < neigh(:,3);
neigh = [T(idx1) neigh(idx1,1); T(idx2) neigh(idx2,2); T(idx3) 
neigh(idx3,3)]';
plot3(xcc(neigh), ycc(neigh), zcc(neigh),'-r');
axis equal;

This is just a 3D extension of the following example;
http://www.mathworks.com/products/demos/shipping/matlab/demoDelaunayTri.html#24

Best regards,

Damian


"Abel Brown" <brown.2179@osu.edu> wrote in message 
news:hd0e8h$c9$1@fred.mathworks.com...
> iv been able to make voronoi diagrams easily on 2D plane but can not seem 
> to get it right for a sphere.
>
> iv googled around and found some spherical V. diagrams but cant seem to 
> get matlab to do this
>
> http://people.sc.fsu.edu/~%20burkardt/f_src/sxyz_voronoi/gen_00100.png
>
> I have some points (lat, lon, ht  or x, y, z) and would like to make 
> sphereical Voronoi diagram and plot it.  Any help would be awesome!
>
> cheers!