Voronoi extension by Vincent Nivoliers (Bug 783922)

Fixed bugs:
  - https://launchpad.net/bugs/783922

(bzr r10243)

4 files changed, 383 insertions, 1 deletions

diff --git a/share/extensions/Makefile.am b/share/extensions/Makefile.am
index 6189427ca..cfe9ff970 100644
--- a/share/extensions/Makefile.am
+++ b/share/extensions/Makefile.am
@@ -161,6 +161,7 @@ extensions = \
 	uniconv-ext.py \
 	uniconv_output.py \
 	voronoi.py \
+	voronoi2svg.py \
 	webslicer_create_group.py \
 	webslicer_create_rect.py \
 	webslicer_effect.py \
@@ -322,6 +323,7 @@ modules = \
 	text_braille.inx \
 	triangle.inx \
 	txt2svg.inx \
+	voronoi2svg.inx \
 	webslicer_create_group.inx \
 	webslicer_create_rect.inx \
 	webslicer_export.inx \
diff --git a/share/extensions/voronoi.py b/share/extensions/voronoi.py
index be15fbe13..fb38df1b2 100644
--- a/share/extensions/voronoi.py
+++ b/share/extensions/voronoi.py
@@ -747,7 +747,7 @@ def computeDelaunayTriangulation(points):
     """
     siteList = SiteList(points)
     context  = Context()
-    context.triangulate = true
+    context.triangulate = True
     voronoi(siteList,context)
     return context.triangles
 
diff --git a/share/extensions/voronoi2svg.inx b/share/extensions/voronoi2svg.inx
new file mode 100644
index 000000000..f8806e1e6
--- /dev/null
+++ b/share/extensions/voronoi2svg.inx
@@ -0,0 +1,28 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<inkscape-extension xmlns="http://www.inkscape.org/namespace/inkscape/extension">
+	<_name>Voronoi Diagram</_name>
+  <id>org.inkscape.effect.voronoi</id>
+  <dependency type="executable" location="extensions">voronoi2svg.py</dependency>
+  <dependency type="executable" location="extensions">inkex.py</dependency>
+  <dependency type="executable" location="extensions">voronoi.py</dependency>
+  <param name="diagram-type" type="optiongroup" appearance="minimal" _gui-text="Select type of diagram">
+    <option value="Voronoi">Voronoi Diagram</option>
+    <option value="Delaunay">Delaunay Triangulation</option>
+    <option value="Both">Voronoi and Delaunay</option>
+  </param>
+  <param name="Voronoi Options" type="description" appearance="header">Options for Voronoi diagram</param>
+  <param name="clip-box" type="optiongroup" appearance="minimal" _gui-text="Area bounding the Voronoi diagram">
+    <option value="Page">Page</option>
+    <option value="Automatic from seeds">Automatic from seeds</option>
+  </param>
+  <param name="show-clip-box" type="boolean" _gui-text="Show the Voronoi bounding area"></param>
+  <effect>
+    <object-type>all</object-type>
+    <effects-menu>
+      <submenu _name="Generate from Path"/>
+    </effects-menu>
+  </effect>
+  <script>
+    <command reldir="extensions" interpreter="python">voronoi2svg.py</command>
+  </script>
+</inkscape-extension>
diff --git a/share/extensions/voronoi2svg.py b/share/extensions/voronoi2svg.py
new file mode 100644
index 000000000..706a37cde
--- /dev/null
+++ b/share/extensions/voronoi2svg.py
@@ -0,0 +1,352 @@
+#!/usr/bin/env python
+"""
+
+voronoi2svg.py
+Create Voronoi diagram from seeds (midpoints of selected objects)
+
+- Voronoi Diagram algorithm and C code by Steven Fortune, 1987, http://ect.bell-labs.com/who/sjf/
+- Python translation to file voronoi.py by Bill Simons, 2005, http://www.oxfish.com/
+
+Copyright (C) 2011 Vincent Nivoliers and contributors
+
+Contributors
+  ~suv, <suv-sf@users.sf.net>
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+"""
+import sys, os
+import inkex, simplestyle, simplepath, simpletransform
+import voronoi
+import gettext
+_ = gettext.gettext
+
+class Point:
+  def __init__(self,x,y):
+    self.x = x
+    self.y = y
+
+class Voronoi2svg(inkex.Effect):
+  def __init__(self):
+    inkex.Effect.__init__(self)
+
+    #{{{ Additional options
+
+    self.OptionParser.add_option(
+      '--diagram-type',
+      action = 'store',
+      type = 'choice', choices=['Voronoi','Delaunay','Both'],
+      default = 'Voronoi',
+      dest='diagramType',
+      help = 'Defines the type of the diagram')
+    self.OptionParser.add_option(
+      '--clip-box',
+      action = 'store',
+      type = 'choice', choices=['Page','Automatic from seeds'],
+      default = 'Page',
+      dest='clipBox',
+      help = 'Defines the area bounding the Voronoi diagram')
+    self.OptionParser.add_option(
+      '--show-clip-box',
+      action = 'store',
+      type = 'inkbool',
+      default = False,
+      dest='showClipBox',
+      help = 'Set this to true to write the bounding box of the bounding area')
+
+    #}}}
+
+  #{{{ Clipping a line by a bounding box
+  def dot(self,x,y):
+    return x[0]*y[0] + x[1]*y[1]
+
+  def intersectLineSegment(self,line,v1,v2):
+    s1 = self.dot(line,v1) - line[2]
+    s2 = self.dot(line,v2) - line[2]
+    if s1*s2 > 0:
+      return (0,0,False)
+    else:
+      tmp = self.dot(line,v1)-self.dot(line,v2)
+      if tmp == 0:
+        return(0,0,False)
+      u = (line[2]-self.dot(line,v2))/tmp
+      v = 1-u
+      return (u*v1[0]+v*v2[0],u*v1[1]+v*v2[1],True)
+  
+  def clipEdge(self,vertices, lines, edge, bbox):
+    #bounding box corners
+    bbc = []
+    bbc.append((bbox[0],bbox[2]))
+    bbc.append((bbox[1],bbox[2]))
+    bbc.append((bbox[1],bbox[3]))
+    bbc.append((bbox[0],bbox[3]))
+
+    #record intersections of the line with bounding box edges
+    line = (lines[edge[0]])
+    interpoints = []
+    for i in range(4):
+      p = self.intersectLineSegment(line,bbc[i],bbc[(i+1)%4])
+      if (p[2]):
+        interpoints.append(p)
+
+    #if the edge has no intersection, return empty intersection
+    if (len(interpoints)<2):
+      return []
+
+    if (len(interpoints)>2): #happens when the edge crosses the corner of the box
+      interpoints = list(set(interpoints)) #remove doubles
+
+    #points of the edge
+    v1 = vertices[edge[1]]
+    interpoints.append((v1[0],v1[1],False))
+    v2 = vertices[edge[2]]
+    interpoints.append((v2[0],v2[1],False))
+
+    #sorting the points in the widest range to get them in order on the line
+    minx = interpoints[0][0]
+    maxx = interpoints[0][0]
+    miny = interpoints[0][1]
+    maxy = interpoints[0][1]
+    for point in interpoints:
+      minx = min(point[0],minx)
+      maxx = max(point[0],maxx)
+      miny = min(point[1],miny)
+      maxy = max(point[1],maxy)
+
+    if (maxx-minx) > (maxy-miny):
+      interpoints.sort()
+    else:
+      interpoints.sort(key=lambda pt: pt[1])
+
+    start = []
+    inside = False #true when the part of the line studied is in the clip box
+    startWrite = False #true when the part of the line is in the edge segment
+    for point in interpoints:
+      if point[2]: #The point is a bounding box intersection
+        if inside:
+          if startWrite:
+            return [[start[0],start[1]],[point[0],point[1]]]
+          else:
+            return []
+        else: 
+          if startWrite:
+            start = point
+        inside = not inside
+      else: #The point is a segment endpoint
+        if startWrite:
+          if inside:
+            #a vertex ends the line inside the bounding box
+            return [[start[0],start[1]],[point[0],point[1]]]
+          else:
+            return []
+        else:
+          if inside:
+            start = point
+        startWrite = not startWrite
+          
+  #}}}
+
+  #{{{ Transformation helpers
+
+  def invertTransform(self,mat):
+    det = mat[0][0]*mat[1][1] - mat[0][1]*mat[1][0]
+    if det !=0: #det is 0 only in case of 0 scaling
+      #invert the rotation/scaling part
+      a11 =  mat[1][1]/det
+      a12 = -mat[0][1]/det
+      a21 = -mat[1][0]/det
+      a22 =  mat[0][0]/det
+
+      #invert the translational part
+      a13 = -(a11*mat[0][2] + a12*mat[1][2])
+      a23 = -(a21*mat[0][2] + a22*mat[1][2])
+
+      return [[a11,a12,a13],[a21,a22,a23]]
+    else:
+      return[[0,0,-mat[0][2]],[0,0,-mat[1][2]]]
+
+  def getGlobalTransform(self,node):
+    parent = node.getparent()
+    myTrans = simpletransform.parseTransform(node.get('transform'))
+    if myTrans:
+      if parent is not None:
+        parentTrans = self.getGlobalTransform(parent)
+        if parentTrans:
+          return simpletransform.composeTransform(parentTrans,myTrans)
+        else:
+          return myTrans
+    else:
+      if parent is not None:
+        return self.getGlobalTransform(parent)
+      else:
+        return None
+    
+
+  #}}}
+
+  def effect(self):
+    svg = self.document.getroot()
+
+    #{{{ Drawing styles
+
+    linestyle = {
+        'stroke'    : '#000000',
+        'linewidth' : '1',
+        'fill'      : 'none'
+        }
+
+    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