# Fast Calculation of Voronoi Polygons in PovRay

Yet further abuse to follow in the application of PovRay for spatial analyses– be forwarned… .

Calculating Voronoi polygons is a useful tool for calculating the initial approximation of a medial axis. We densify the vertices on the polygon for which we want a medial axis, and then calculate Voronoi polygons on said vertices. I’ll confess– I’ve been using ArcGIS for this step. There. I said it. My name is smathermather, and I use ArcGIS. It’s a darn useful tool, and, and, I’m not ashamed to say that I use it all the time.

But, I do like the idea of doing this with non-proprietary, open source tools. I’ve contemplated using the approach that Regina Obe blogs about using PL/R + PostGIS to calculate them, but the installation of PL/R on my system failed my initial Yak Shaving Test.

So, with some google-fu, I stumbled upon articles on using 3D approaches to calculate 2D Voronoi diagrams, and my brain went into high gear. Right cones of equal size, viewed orthogonally generate lovely Voronoi diagrams, the only caveat being you need to know what your maximum distance you want to calculate in your diagram. For my use cases, this isn’t a limitation at all.

And so we abuse PovRay, yet again, to do our dirty work in analyses. I’ll undoubtedly have some follow up posts on this, but in the mean time, some diagrams and really dirty code:

```
global_settings {
ambient_light rgb <0.723364, 0.723368, 0.723364>
}

camera {
orthographic
location < 0.0, 5, 0>
right x * 3
up y * 3
look_at < 0.0, 0.0, 0.0>
}

light_source {
< 0.0, 100, 0>
rgb <0.999996, 1.000000, 0.999996>
parallel
point_at < 0.0, 0.0, 0.0>
}

light_source {
< 0.0, 100, 100>
rgb <0.999996, 1.000000, 0.999996>
parallel
point_at < 0.0, 0.0, 0.0>
}

light_source {
< 100, 100, 0>
rgb <0.999996, 1.000000, 0.999996>
parallel
point_at < 0.0, 0.0, 0.0>
}

cone {
<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
hollow
material {
texture {
pigment {
rgb <0.089677, 0.000000, 1.000000>
}
finish {
diffuse 0.6
brilliance 1.0
}
}
interior {
ior 1.3
}
}
}

cone {
<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
hollow
material {
texture {
pigment {
rgb <1, 0.000000, 1.000000>
}
finish {
diffuse 0.6
brilliance 1.0
}
}
interior {
ior 1.3
}
}
translate <-0.5,0,-0.5>
}

cone {
<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
hollow
material {
texture {
pigment {
rgb <1, 0.000000, 000000>
}
finish {
diffuse 0.6
brilliance 1.0
}
}
interior {
ior 1.3
}
}
translate <-0.5,0,0.5>
}

cone {
<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
hollow
material {
texture {
pigment {
rgb <1, 1.000000, 000000>
}
finish {
diffuse 0.6
brilliance 1.0
}
}
interior {
ior 1.3
}
}
translate <0.3,0,0.3>
}

cone {
<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
hollow
material {
texture {
pigment {
rgb <0, 1.000000, 000000>
}
finish {
diffuse 0.6
brilliance 1.0
}
}
interior {
ior 1.3
}
}
translate <0.4,0,-0.2>
}

cone {
<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
hollow
material {
texture {
pigment {
rgb <1, 1.000000, 1.000000>
}
finish {
diffuse 0.6
brilliance 1.0
}
}
interior {
ior 1.3
}
}
translate <0,0,-.7>
}
```

## 2 thoughts on “Fast Calculation of Voronoi Polygons in PovRay”

1. By the way, one might implement something similar directly in PostGIS using the 3D capabilities, and then just extract the intersections, much as we do here with orthogonal rendering. But, that’s another post altogether.

This site uses Akismet to reduce spam. Learn how your comment data is processed.