As a graduate student I had to work with Voronoi diagrams for 2D point sets coming from a homogeneous Poisson distribution.
Either for simulation purposes (I needed to manipulate Voronoi diagrams in my C++ code) or just to draw examples and figures I needed some software to do that.
I know there is Matlab out there that does something similar but for various technical reasons plus the urge of every software engineer to do things by himself I resisted the temptation.
So, I set out to write it myself!
A non-obvious choice that fit all the requirements is ... a combination of Python and Xfig!
Using Python I could very easily link my application to a C++ program and could use it as a portable standalone tool to draw diagrams.
Xfig is deep in my heart.
Its ridiculously simple yet powerful format plus the fact that it started from UT made it the choice for me.
As the core library for manipulating Voronoi diagrams in Python I used Bill Simons' translation in Python of Steve Fortune's algorithm.
An almost identical version of the module I use can be found in https://bitbucket.org/mozman/geoalg/src/5bbd46fa2270/geoalg/voronoi.py (you might have to do some adjustments to the code, I have not tried it).
My code follows.
Some parts are a testament of bad software engineering.
The most obvious limitation is that I was lazy enough to explicitly create arguments for all the parameters, manual editing is fine sometimes. :)
#!/usr/bin/python
import random
import sys
#
import voronoi
class Point:
def __init__(self, *args, **kwargs):
if 2==len(args):
self.x = args[0]
self.y = args[1]
self.text=''
elif 3==len(args):
self.x = args[0]
self.y = args[1]
self.text = args[2]
if kwargs.get('default'):
self.x = 0
self.y = 0;
def printYourself(self):
print "(point",self.x,self.y,")"
def __eq__(self,other):
return self.x == other.x and self.y == other.y
def closerThanCutOff(self,x,y):
return pow(self.x-x,2)+pow(self.y-y,2) < pow(cutOffDistance,2)
def createPoints():
global points;
global lx;
global ly;
global lload;
points = map(lambda x,y,z : Point(x,y,z), lx,ly,lload)
def computeVoronoiDiagram():
global points;
return voronoi.computeVoronoiDiagram(points);
def computeDelaunayTriangulation():
global points;
return voronoi.computeDelaunayTriangulation(points);
def preamble(printMethod):
map(lambda x : printMethod(x), ('#FIG 3.2','Landscape','Center','Inches','Letter','100.0','Single','-2','%d 2' % (SCALE,)))
def foo(x):
print x
def goo(file):
def boo(x):
import os
os.system("echo '%s' >> '%s'" % (x,file))
return boo
SCALE = 120
def drawVoronoiDiagram(printToFile, gridSideLength,*highlightedPoints):
global points;
hPoints = []
if len(highlightedPoints) > 0:
assert 0 == len(highlightedPoints) % 2
hPoints.append(Point(highlightedPoints[0],highlightedPoints[1]))
hPoints.append(Point(highlightedPoints[2],highlightedPoints[3]))
if printToFile:
printMethod=goo(printToFile)
else:
printMethod=foo
preamble(printMethod);
printMethod('# SCALE %d' % (SCALE,))
printMethod('# GRID_SIDE_LENGTH %d' % (gridSideLength))
radius_x = SCALE/60;
radius_y = radius_x;
for point in points:
if point in hPoints:
printMethod('1 3 0 1 0 18 50 -1 20 0.000 1 0.0000 %d %d %d %d %d %d %d %d' % (SCALE*point.x, SCALE*point.y, radius_x, radius_y, SCALE*point.x-radius_x, SCALE*point.y, SCALE*point.x+radius_x, SCALE*point.y))
else:
printMethod('1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 %d %d %d %d %d %d %d %d' % (SCALE*point.x, SCALE*point.y, radius_x, radius_y, SCALE*point.x-radius_x, SCALE*point.y, SCALE*point.x+radius_x, SCALE*point.y))
#printMethod('4 0 0 0 0 0 1 0 0 1 1 %d %d 65 66 65 66 \ 0 0 1' % (SCALE*point.x, SCALE*point.y))
pencolorVoronoiEdge = 0
linestyleVoronoiEdge = -1
printMethod('2 1 %s 2 %s 7 50 -1 -1 0.000 0 0 -1 0 0 2' % (linestyleVoronoiEdge,pencolorVoronoiEdge))
printMethod('\t 0 0 0 %d' % (SCALE*gridSideLength,))
printMethod('2 1 %s 2 %s 7 50 -1 -1 0.000 0 0 -1 0 0 2' % (linestyleVoronoiEdge,pencolorVoronoiEdge))
printMethod('\t 0 0 %d 0' % (SCALE*gridSideLength,))
printMethod('2 1 %s 2 %s 7 50 -1 -1 0.000 0 0 -1 0 0 2' % (linestyleVoronoiEdge,pencolorVoronoiEdge))
printMethod('\t %d %d %d 0' % (SCALE*gridSideLength,SCALE*gridSideLength,SCALE*gridSideLength))
printMethod('2 1 %s 2 %s 7 50 -1 -1 0.000 0 0 -1 0 0 2' % (linestyleVoronoiEdge,pencolorVoronoiEdge))
printMethod('\t %d %d 0 %d' % (SCALE*gridSideLength,SCALE*gridSideLength,SCALE*gridSideLength))
vertices,lines,edges = voronoi.computeVoronoiDiagram(points)
voronoiEdge = '2 1 %s 2 %s 7 50 -1 -1 0.000 0 0 -1 0 0 2' % (linestyleVoronoiEdge, pencolorVoronoiEdge)
for line,v1,v2 in edges:
if v1 != -1 and v2 != -1:
printMethod(voronoiEdge)
printMethod('\t %d %d %d %d' % (SCALE*vertices[v1][0], SCALE*vertices[v1][1], SCALE*vertices[v2][0], SCALE*vertices[v2][1]))
points = []
def readTopologyFromFile(inFile):
global points
inHandle = open(inFile, 'r')
for line in inHandle:
if line.startswith('1 '):
lineSplit = line.split()
points.append(Point(float(lineSplit[12])/float(SCALE),float(lineSplit[13])/float(SCALE)))
inHandle.close()
def createTopology(numPoints,gridDimension):
for point in range(numPoints):
point = Point(default='yes')
point.x = random.random()*gridDimension
point.y = random.random()*gridDimension
points.append(point)
if __name__ == "__main__":
""" The format of .fig files is described in http://www.xfig.org/userman/fig-format.html"""
createTopology(150,5)
drawVoronoiDiagram(None,5)
Have you ever thought how can something so nice come from something so ugly? :)