voronoi2svg.py revision 6ed90202378068e77619b6e8b259ad064dd3fd2b
3427N/A#!/usr/bin/env python
1710N/A"""
3427N/A
1710N/Avoronoi2svg.py
3427N/ACreate Voronoi diagram from seeds (midpoints of selected objects)
1710N/A
1710N/A- Voronoi Diagram algorithm and C code by Steven Fortune, 1987, http://ect.bell-labs.com/who/sjf/
1710N/A- Python translation to file voronoi.py by Bill Simons, 2005, http://www.oxfish.com/
1710N/A
1710N/ACopyright (C) 2011 Vincent Nivoliers and contributors
1710N/A
1710N/AContributors
1710N/A ~suv, <suv-sf@users.sf.net>
1710N/A
1710N/AThis program is free software; you can redistribute it and/or modify
1710N/Ait under the terms of the GNU General Public License as published by
1710N/Athe Free Software Foundation; either version 2 of the License, or
1710N/A(at your option) any later version.
1710N/A
1710N/AThis program is distributed in the hope that it will be useful,
1710N/Abut WITHOUT ANY WARRANTY; without even the implied warranty of
1710N/AMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1710N/AGNU General Public License for more details.
1710N/A
1710N/AYou should have received a copy of the GNU General Public License
1710N/Aalong with this program; if not, write to the Free Software
1710N/AFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
1710N/A
1710N/A"""
1710N/Aimport sys, os
1710N/Aimport inkex, simplestyle, simplepath, simpletransform
1710N/Aimport voronoi
1710N/Aimport gettext
1710N/A_ = gettext.gettext
1710N/A
1710N/Aclass Point:
1710N/A def __init__(self,x,y):
1710N/A self.x = x
1710N/A self.y = y
1710N/A
1710N/Aclass Voronoi2svg(inkex.Effect):
1710N/A def __init__(self):
1710N/A inkex.Effect.__init__(self)
1710N/A
1710N/A #{{{ Additional options
1710N/A
1710N/A self.OptionParser.add_option(
1710N/A '--diagram-type',
1710N/A action = 'store',
1710N/A type = 'choice', choices=['Voronoi','Delaunay','Both'],
1710N/A default = 'Voronoi',
1710N/A dest='diagramType',
1710N/A help = 'Defines the type of the diagram')
1710N/A self.OptionParser.add_option(
1710N/A '--clip-box',
1710N/A action = 'store',
1710N/A type = 'choice', choices=['Page','Automatic from seeds'],
1710N/A default = 'Page',
1710N/A dest='clipBox',
1710N/A help = 'Defines the area bounding the Voronoi diagram')
1710N/A self.OptionParser.add_option(
1710N/A '--show-clip-box',
1710N/A action = 'store',
1710N/A type = 'inkbool',
1710N/A default = False,
1710N/A dest='showClipBox',
1710N/A help = 'Set this to true to write the bounding box of the bounding area')
1710N/A
1710N/A #}}}
1710N/A
1710N/A #{{{ Clipping a line by a bounding box
1710N/A def dot(self,x,y):
1710N/A return x[0]*y[0] + x[1]*y[1]
1710N/A
1710N/A def intersectLineSegment(self,line,v1,v2):
1710N/A s1 = self.dot(line,v1) - line[2]
1710N/A s2 = self.dot(line,v2) - line[2]
1710N/A if s1*s2 > 0:
1710N/A return (0,0,False)
1710N/A else:
1710N/A tmp = self.dot(line,v1)-self.dot(line,v2)
1710N/A if tmp == 0:
1710N/A return(0,0,False)
1710N/A u = (line[2]-self.dot(line,v2))/tmp
1710N/A v = 1-u
1710N/A return (u*v1[0]+v*v2[0],u*v1[1]+v*v2[1],True)
1710N/A
1710N/A def clipEdge(self,vertices, lines, edge, bbox):
1710N/A #bounding box corners
1710N/A bbc = []
1710N/A bbc.append((bbox[0],bbox[2]))
1710N/A bbc.append((bbox[1],bbox[2]))
1710N/A bbc.append((bbox[1],bbox[3]))
1710N/A bbc.append((bbox[0],bbox[3]))
1710N/A
1710N/A #record intersections of the line with bounding box edges
1710N/A line = (lines[edge[0]])
1710N/A interpoints = []
1710N/A for i in range(4):
1710N/A p = self.intersectLineSegment(line,bbc[i],bbc[(i+1)%4])
1710N/A if (p[2]):
1710N/A interpoints.append(p)
1710N/A
1710N/A #if the edge has no intersection, return empty intersection
1710N/A if (len(interpoints)<2):
1710N/A return []
1710N/A
1710N/A if (len(interpoints)>2): #happens when the edge crosses the corner of the box
1710N/A interpoints = list(set(interpoints)) #remove doubles
1710N/A
1710N/A #points of the edge
1710N/A v1 = vertices[edge[1]]
1710N/A interpoints.append((v1[0],v1[1],False))
1710N/A v2 = vertices[edge[2]]
1710N/A interpoints.append((v2[0],v2[1],False))
1710N/A
1710N/A #sorting the points in the widest range to get them in order on the line
1710N/A minx = interpoints[0][0]
1710N/A maxx = interpoints[0][0]
1710N/A miny = interpoints[0][1]
1710N/A maxy = interpoints[0][1]
1710N/A for point in interpoints:
1710N/A minx = min(point[0],minx)
1710N/A maxx = max(point[0],maxx)
1710N/A miny = min(point[1],miny)
1710N/A maxy = max(point[1],maxy)
1710N/A
1710N/A if (maxx-minx) > (maxy-miny):
1710N/A interpoints.sort()
1710N/A else:
1710N/A interpoints.sort(key=lambda pt: pt[1])
1710N/A
1710N/A start = []
1710N/A inside = False #true when the part of the line studied is in the clip box
1710N/A startWrite = False #true when the part of the line is in the edge segment
1710N/A for point in interpoints:
1710N/A if point[2]: #The point is a bounding box intersection
1710N/A if inside:
1710N/A if startWrite:
1710N/A return [[start[0],start[1]],[point[0],point[1]]]
1710N/A else:
1710N/A return []
1710N/A else:
1710N/A if startWrite:
1710N/A start = point
1710N/A inside = not inside
1710N/A else: #The point is a segment endpoint
1710N/A if startWrite:
1710N/A if inside:
1710N/A #a vertex ends the line inside the bounding box
1710N/A return [[start[0],start[1]],[point[0],point[1]]]
1710N/A else:
1710N/A return []
1710N/A else:
1710N/A if inside:
1710N/A start = point
1710N/A startWrite = not startWrite
1710N/A
1710N/A #}}}
1710N/A
1710N/A #{{{ Transformation helpers
1710N/A
1710N/A def invertTransform(self,mat):
1710N/A det = mat[0][0]*mat[1][1] - mat[0][1]*mat[1][0]
1710N/A if det !=0: #det is 0 only in case of 0 scaling
1710N/A #invert the rotation/scaling part
1710N/A a11 = mat[1][1]/det
1710N/A a12 = -mat[0][1]/det
1710N/A a21 = -mat[1][0]/det
1710N/A a22 = mat[0][0]/det
1710N/A
1710N/A #invert the translational part
1710N/A a13 = -(a11*mat[0][2] + a12*mat[1][2])
1710N/A a23 = -(a21*mat[0][2] + a22*mat[1][2])
1710N/A
1710N/A return [[a11,a12,a13],[a21,a22,a23]]
1710N/A else:
1710N/A return[[0,0,-mat[0][2]],[0,0,-mat[1][2]]]
1710N/A
1710N/A def getGlobalTransform(self,node):
1710N/A parent = node.getparent()
1710N/A myTrans = simpletransform.parseTransform(node.get('transform'))
1710N/A if myTrans:
1710N/A if parent is not None:
1710N/A parentTrans = self.getGlobalTransform(parent)
1710N/A if parentTrans:
1710N/A return simpletransform.composeTransform(parentTrans,myTrans)
1710N/A else:
1710N/A return myTrans
1710N/A else:
1710N/A if parent is not None:
1710N/A return self.getGlobalTransform(parent)
1710N/A else:
1710N/A return None
1710N/A
1710N/A
1710N/A #}}}
1710N/A
1710N/A def effect(self):
1710N/A svg = self.document.getroot()
1710N/A
1710N/A #{{{ Drawing styles
1710N/A
1710N/A linestyle = {
1710N/A 'stroke' : '#000000',
1710N/A 'linewidth' : '1',
1710N/A 'fill' : 'none'
3427N/A }
facestyle = {
'stroke' : '#ff0000',
'linewidth' : '1',
'fill' : 'none'
}
#}}}
#{{{ Handle the transformation of the current group
trans = self.getGlobalTransform(self.current_layer)
invtrans = None
if trans:
invtrans = self.invertTransform(trans)
#}}}
#{{{ Recovery of the selected objects
pts = []
nodes = []
seeds = []
for id in self.options.ids:
node = self.selected[id]
nodes.append(node)
bbox = simpletransform.computeBBox([node])
if bbox:
cx = 0.5*(bbox[0]+bbox[1])
cy = 0.5*(bbox[2]+bbox[3])
pt = [cx,cy]
if trans:
simpletransform.applyTransformToPoint(trans,pt)
pts.append(Point(pt[0],pt[1]))
seeds.append(Point(cx,cy))
if not seeds:
inkex.errormsg("Please select seed objects!")
return
#}}}
#{{{ Creation of groups to store the result
if self.options.diagramType != 'Delaunay':
# Voronoi
groupVoronoi = inkex.etree.SubElement(self.current_layer,inkex.addNS('g','svg'))
groupVoronoi.set(inkex.addNS('label', 'inkscape'), 'Voronoi')
if invtrans:
simpletransform.applyTransformToNode(invtrans,groupVoronoi)
if self.options.diagramType != 'Voronoi':
# Delaunay
groupDelaunay = inkex.etree.SubElement(self.current_layer,inkex.addNS('g','svg'))
groupDelaunay.set(inkex.addNS('label', 'inkscape'), 'Delaunay')
#}}}
#{{{ Clipping box handling
if self.options.diagramType != 'Delaunay':
#Clipping bounding box creation
gBbox = simpletransform.computeBBox(nodes)
#Clipbox is the box to which the Voronoi diagram is restricted
clipBox = ()
if self.options.clipBox == 'Page':
w = inkex.unittouu(svg.get('width'))
h = inkex.unittouu(svg.get('height'))
clipBox = (0,w,0,h)
else:
clipBox = (2*gBbox[0]-gBbox[1],
2*gBbox[1]-gBbox[0],
2*gBbox[2]-gBbox[3],
2*gBbox[3]-gBbox[2])
#Safebox adds points so that no Voronoi edge in clipBox is infinite
safeBox = (2*clipBox[0]-clipBox[1],
2*clipBox[1]-clipBox[0],
2*clipBox[2]-clipBox[3],
2*clipBox[3]-clipBox[2])
pts.append(Point(safeBox[0],safeBox[2]))
pts.append(Point(safeBox[1],safeBox[2]))
pts.append(Point(safeBox[1],safeBox[3]))
pts.append(Point(safeBox[0],safeBox[3]))
if self.options.showClipBox:
#Add the clip box to the drawing
rect = inkex.etree.SubElement(groupVoronoi,inkex.addNS('rect','svg'))
rect.set('x',str(clipBox[0]))
rect.set('y',str(clipBox[2]))
rect.set('width',str(clipBox[1]-clipBox[0]))
rect.set('height',str(clipBox[3]-clipBox[2]))
rect.set('style',simplestyle.formatStyle(linestyle))
#}}}
#{{{ Voronoi diagram generation
if self.options.diagramType != 'Delaunay':
vertices,lines,edges = voronoi.computeVoronoiDiagram(pts)
for edge in edges:
line = edge[0]
vindex1 = edge[1]
vindex2 = edge[2]
if (vindex1 <0) or (vindex2 <0):
continue # infinite lines have no need to be handled in the clipped box
else:
segment = self.clipEdge(vertices,lines,edge,clipBox)
#segment = [vertices[vindex1],vertices[vindex2]] # deactivate clipping
if len(segment)>1:
v1 = segment[0]
v2 = segment[1]
cmds = [['M',[v1[0],v1[1]]],['L',[v2[0],v2[1]]]]
path = inkex.etree.Element(inkex.addNS('path','svg'))
path.set('d',simplepath.formatPath(cmds))
path.set('style',simplestyle.formatStyle(linestyle))
groupVoronoi.append(path)
if self.options.diagramType != 'Voronoi':
triangles = voronoi.computeDelaunayTriangulation(seeds)
for triangle in triangles:
p1 = seeds[triangle[0]]
p2 = seeds[triangle[1]]
p3 = seeds[triangle[2]]
cmds = [['M',[p1.x,p1.y]],
['L',[p2.x,p2.y]],
['L',[p3.x,p3.y]],
['Z',[]]]
path = inkex.etree.Element(inkex.addNS('path','svg'))
path.set('d',simplepath.formatPath(cmds))
path.set('style',simplestyle.formatStyle(facestyle))
groupDelaunay.append(path)
#}}}
if __name__ == "__main__":
e = Voronoi2svg()
e.affect()
# vim: expandtab shiftwidth=2 tabstop=2 softtabstop=2 fileencoding=utf-8 textwidth=99