Voronoi diagrams

Discuss interdimensional programming, Java applets and so forth.

Voronoi diagrams

Postby quickfur » Tue Dec 06, 2011 3:17 am

What's a good algorithm for generating voronoi diagrams on a 2-torus? More specifically, the torus is the ridge of a duocylinder (identically deformed at all points), so the distance metric is simple (it can just be the 2D Euclidean metric).
quickfur
Pentonian
 
Posts: 2435
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Voronoi diagrams

Postby quickfur » Wed Dec 07, 2011 6:24 am

*cough* Thanks for the helpful feedback. :P

I've found the answer in Atsuyuki Okabe's book Spatial Tesselations: starting with some seed points in a square region, assemble 9 copies of this square along with the seed points into a 3x3 grid, and compute the Voronoi diagram for the grid (using the usual 2D Voronoi diagram algorithms). After you're done, cut out the center square, and you have a Voronoi diagram for the 2-torus. Neato. :)
quickfur
Pentonian
 
Posts: 2435
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Voronoi diagrams

Postby Mrrl » Wed Dec 07, 2011 2:12 pm

But you didn't said that it's square torus! I've looked for algorithm that will work for arbitrary aspect. Tried to start with Delanay triangulation, but was not sure what to do if the picture will be non-periodic.
Mrrl
Trionian
 
Posts: 165
Joined: Sun May 29, 2011 7:37 am

Re: Voronoi diagrams

Postby quickfur » Wed Dec 07, 2011 3:00 pm

Oh. OK. :oops: But I thought it was clear enough when I said it was the ridge of the duocylinder with a 2D metric.

As for arbitrary aspect, it seems very complicated; kudos to you if you can figure it out. :)
quickfur
Pentonian
 
Posts: 2435
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Voronoi diagrams

Postby Mrrl » Wed Dec 07, 2011 4:17 pm

Easy :) In rectangular case 3x3 grid works for any aspect: if you have point (x,y) and look for the closest point in set (x_i+dx*m,y_i+dy*n), where (x_i,y_i) - given points and dx,dy - torus dimensions, in will be one of points (x_i+dx*round((x-x_i)/dx),y_i+dy*round((y-y_i)/dy). If (x,y) and (x_i,y_i) are in the same fundamental region, then |x-x_i|<dx, |y-y_i|<dy, so |round((x-x_i)/dx)|<=1. Actually you need only 2x2 grid :)
Non-rectangular torus case is more complicated: if shifts are (a,0) and (b,c), where |b|<a/2, b^2+c^2<a^2, take d=sqrt((a+|b|)^2+c^2)/2 and points from periodic pattern in the rectangular [min(0,b)-d,a+max(0,b)+d]*[-d,c+d]. Intersection of their Voronoi diagram with the fundamental region gives the answer.
Mrrl
Trionian
 
Posts: 165
Joined: Sun May 29, 2011 7:37 am

Re: Voronoi diagrams

Postby quickfur » Wed Dec 07, 2011 6:33 pm

Молодец!

By "arbitrary aspect" I was referring to unevenly-deformed tori, though. Like torus embedded in 3D with 3D distance metric. But I'm not really interested in that case right now, so it's probably not worth the trouble to solve it. :)
quickfur
Pentonian
 
Posts: 2435
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North


Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest