Freesteel Blog » OpenVoronoi in twistcodewiki

OpenVoronoi in twistcodewiki

Thursday, October 9th, 2014 at 3:43 pm Written by:

I’m casting around for some little long term geometric projects which I could be good at. I’m very bad at the sysops stuff and compilers (which seems to be a breeze for every other hacker in the world). Plotting the geometry which you have calculated is also a drag.

For me, twistcodewiki does it all.

I followed the instructions to compile OpenVoronoi on this very small under-powered linux netbook I have kicking around, and got twistcodewiki to work. Here is me entering a polygon and plotting a voronoi structure from it:

ovdscreenshot

The code is as follows:

import openvoronoi as ovd
far = 1    # maximum radius containing all the points
vd = ovd.VoronoiDiagram(far, 120)
print vd

pts = [(0,0), (10,-2), (9,5), (5,7), (2,6)]
div = 20.0

ppts = [ ovd.Point(pt[0]/div, pt[1]/div)  for pt in pts ]
ipts = [ vd.addVertexSite(p)  for p in ppts ]
for i in range(1, len(ipts)):
    vd.addLineSite(ipts[i-1], ipts[i])
vd.addLineSite(ipts[-1], ipts[0])

ves = vd.getVoronoiEdges()
conts = [ [(ve[0][0].x, ve[0][0].y, 0.0), (ve[0][1].x, ve[0][1].y, 0.0)]  \
          for ve in ves  if len(ve[0]) == 2 ]
sendactivity("contours", contours=conts)

Inspection of the OpenVoronoi code behind the function VoronoiDiagram::insert_line_site() indicates it’s an implementation of Martin Held’s VRONI: Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments.

When I was at NCGraphics, I implemented his original 2D polygon voronoi algorithm as described in the 1991 book “On the Computational Geometry of Pocket Machining”, and then subsequently reimplemented his slightly improved algorithm outlined in the 1998 paper Voronoi Diagrams and Offset Curves of Curvilinear Polygons which involved finding the partial voronoi structures of two sides of the polygonal sections (recursively) and zipping them up.

[The Voronoi diagrams were crucial for the offset area clearing routines, where you can use the diagram to (a) quickly produce a contour at any offset d, (b) calculate the optimal values of d necessary to clear the contours (where the stepovers were somewhere between the radius and the diameter of the clearing cutter, depending on the angularity of the contour), and (c) rounding off the corners in a racing car path between the contours at d and d+epsilon.]

The problems with these Voronoi calculating algorithms are they are unstable and prone to crashing. At NC Graphics I had to work around this by detecting a failure, and then randomly perturbing every third point inwards by a small distance and trying again, since either you’d get an answer, or you get nothing.

The current state of the art implementations (vroni and OpenVoronoi) calculate the Voronoi diagram incrementally, so you start with a blank area and keep adding point and edge geometry step by step, always maintaining the consistency. This means if you have a crash, you can roll back one step and try again with a slightly different edge, so you are not having to randomly perturb everything because you don’t know where it crashed. It also makes it easier to debug, because the individual steps in the process are much simpler recreate and verify.

I still don’t feel this is the last word on the matter, and have entertained the idea of making an implementation based on the constant scallop algorithm where I embed the structure into a weave and calculate all the points of intersection between perfectly vertical or horizontal lines and the theoretical Voronoi structure. This would allow me to subdivide and localize any vertex into its own cell without any contradictions or failures.

However I just realized this won’t work as there’s a possibility of disagreement if I have two vertical lines very close to a Voronoi node that cut two Voronoi edges corresponding to a very short polygon edge. It’s possible that the two intersections would get out of order disagree with one another. I can really only safely state what Voronoi cell I am within at each point in a grid by measuring to the closest polygon edge or vertex. This can be done in parallel on a GPU. A topology can be inferred from it by plotting joining cell edge half points when the nodes are in different Voronoi polygons, and then projecting them to the analytic positions for the Voronoi edges without changing the topology. So it looks like I should ditch the weave structures which have served me so well, and start examining point structures on their own.

There’s a question of whether such functions should be developed in pure Python for portability and hackability, and then compiled down to C++ only when necessary using Cython or Nuitka — or even have their inner core deployed as PyOpenCL.

All I know is I don’t intend to spend the rest of my life writing and debugging C++ code, as I have done for the last 20 years. It’s time we had another way.

Meanwhile, I keep losing this link to my point cloud house tracing youtube demo. And I should be working on my temperature exponential curve detection functions on the data before I got distracted today. I better tidy up and cycle back to the house on this knacked bike I’ve borrowed before it gets too dark here.

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>