## Voronoi diagrams

Discuss interdimensional programming, Java applets and so forth.

### Voronoi diagrams

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: 2664
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

### Re: Voronoi diagrams

*cough* Thanks for the helpful feedback. 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: 2664
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

### Re: Voronoi diagrams

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

Oh. OK. 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: 2664
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

### Re: Voronoi diagrams

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

Молодец!

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: 2664
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North 