6 posts
• Page **1** of **1**

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

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

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

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

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.

As for arbitrary aspect, it seems very complicated; kudos to you if you can figure it out.

- quickfur
- Pentonian
**Posts:**2482**Joined:**Thu Sep 02, 2004 11:20 pm**Location:**The Great White North

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.

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

Молодец!

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.

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

6 posts
• Page **1** of **1**

Users browsing this forum: No registered users and 1 guest