summaryrefslogtreecommitdiffstats
path: root/share/extensions/voronoi2svg.py
diff options
context:
space:
mode:
Diffstat (limited to '')
-rwxr-xr-xshare/extensions/voronoi2svg.py310
1 files changed, 310 insertions, 0 deletions
diff --git a/share/extensions/voronoi2svg.py b/share/extensions/voronoi2svg.py
new file mode 100755
index 0000000..e4cf802
--- /dev/null
+++ b/share/extensions/voronoi2svg.py
@@ -0,0 +1,310 @@
+#!/usr/bin/env python
+# coding=utf-8
+#
+# Copyright (C) 2011 Vincent Nivoliers and contributors
+#
+# Contributors
+# ~suv, <suv-sf@users.sf.net>
+# - 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/
+#
+# 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
+#
+"""
+Create Voronoi diagram from seeds (midpoints of selected objects)
+"""
+
+import random
+
+import inkex
+from inkex import Group, Rectangle, PathElement, Vector2d as Point
+
+import voronoi
+
+
+class Voronoi(inkex.EffectExtension):
+ """Extension to create a Voronoi diagram."""
+
+ def add_arguments(self, pars):
+ pars.add_argument("--tab")
+ pars.add_argument(
+ "--diagram-type",
+ default="Voronoi",
+ dest="diagramType",
+ choices=["Voronoi", "Delaunay", "Both"],
+ help="Defines the type of the diagram",
+ )
+ pars.add_argument(
+ "--clip-box",
+ choices=["Page", "Automatic from seeds"],
+ default="Page",
+ dest="clip_box",
+ help="Defines the bounding box of the Voronoi diagram",
+ )
+ pars.add_argument(
+ "--show-clip-box",
+ type=inkex.Boolean,
+ default=False,
+ dest="showClipBox",
+ help="Set this to true to write the bounding box",
+ )
+ pars.add_argument(
+ "--delaunay-fill-options",
+ default="delaunay-no-fill",
+ dest="delaunayFillOptions",
+ help="Set the Delaunay triangles color options",
+ )
+
+ def dot(self, x, y):
+ """Clipping a line by a bounding box"""
+ return x[0] * y[0] + x[1] * y[1]
+
+ def intersect_line_segment(self, line, vt1, vt2):
+ """Get the line intersection of the two verticies"""
+ sc1 = self.dot(line, vt1) - line[2]
+ sc2 = self.dot(line, vt2) - line[2]
+ if sc1 * sc2 > 0:
+ return 0, 0, False
+
+ tmp = self.dot(line, vt1) - self.dot(line, vt2)
+ if tmp == 0:
+ return 0, 0, False
+ und = (line[2] - self.dot(line, vt2)) / tmp
+ vt0 = 1 - und
+ return und * vt1[0] + vt0 * vt2[0], und * vt1[1] + vt0 * vt2[1], True
+
+ def clip_edge(self, vertices, lines, edge, bbox):
+ # bounding box corners
+ bbc = [
+ (bbox[0], bbox[2]),
+ (bbox[1], bbox[2]),
+ (bbox[1], bbox[3]),
+ (bbox[0], bbox[3]),
+ ]
+
+ # record intersections of the line with bounding box edges
+ if edge[0] >= len(lines):
+ return []
+ line = lines[edge[0]]
+ interpoints = []
+ for i in range(4):
+ pnt = self.intersect_line_segment(line, bbc[i], bbc[(i + 1) % 4])
+ if pnt[2]:
+ interpoints.append(pnt)
+
+ # 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
+ vt1 = vertices[edge[1]]
+ interpoints.append((vt1[0], vt1[1], False))
+ vt2 = vertices[edge[2]]
+ interpoints.append((vt2[0], vt2[1], False))
+
+ # sorting the points in the widest range to get them in order on the line
+ minx = interpoints[0][0]
+ miny = interpoints[0][1]
+ maxx = interpoints[0][0]
+ 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
+ start_write = 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 start_write:
+ return [[start[0], start[1]], [point[0], point[1]]]
+ return []
+ else:
+ if start_write:
+ start = point
+ inside = not inside
+ else: # The point is a segment endpoint
+ if start_write:
+ if inside:
+ # a vertex ends the line inside the bounding box
+ return [[start[0], start[1]], [point[0], point[1]]]
+ return []
+ else:
+ if inside:
+ start = point
+ start_write = not start_write
+
+ def effect(self):
+ # Check that elements have been selected
+ if not self.svg.selection:
+ inkex.errormsg(_("Please select objects!"))
+ return
+
+ linestyle = {
+ "stroke": "#000000",
+ "stroke-width": str(self.svg.to_dimensionless("1px")),
+ "fill": "none",
+ "stroke-linecap": "round",
+ "stroke-linejoin": "round",
+ }
+
+ facestyle = {
+ "stroke": "#000000",
+ "stroke-width": str(self.svg.to_dimensionless("1px")),
+ "fill": "none",
+ "stroke-linecap": "round",
+ "stroke-linejoin": "round",
+ }
+
+ parent_group = self.svg.selection.first().getparent()
+ trans = parent_group.composed_transform()
+
+ invtrans = None
+ if trans:
+ invtrans = -trans
+
+ # Recovery of the selected objects
+ pts = []
+ nodes = []
+ seeds = []
+ fills = []
+
+ for node in self.svg.selection.values():
+ nodes.append(node)
+ bbox = node.bounding_box()
+ if bbox:
+ center_x, center_y = bbox.center
+ point = [center_x, center_y]
+ if trans:
+ point = trans.apply_to_point(point)
+ pts.append(Point(*point))
+ if self.options.delaunayFillOptions != "delaunay-no-fill":
+ fills.append(node.style.get("fill", "none"))
+ seeds.append(Point(center_x, center_y))
+
+ # Creation of groups to store the result
+ if self.options.diagramType != "Delaunay":
+ # Voronoi
+ group_voronoi = parent_group.add(Group())
+ group_voronoi.set("inkscape:label", "Voronoi")
+ if invtrans:
+ group_voronoi.transform @= invtrans
+ if self.options.diagramType != "Voronoi":
+ # Delaunay
+ group_delaunay = parent_group.add(Group())
+ group_delaunay.set("inkscape:label", "Delaunay")
+
+ # Clipping box handling
+ if self.options.diagramType != "Delaunay":
+ # Clipping bounding box creation
+ group_bbox = sum([node.bounding_box() for node in nodes], None)
+
+ # Clipbox is the box to which the Voronoi diagram is restricted
+ if self.options.clip_box == "Page":
+ width = self.svg.viewbox_width
+ height = self.svg.viewbox_height
+ clip_box = (0, width, 0, height)
+ else:
+ clip_box = (
+ group_bbox.left,
+ group_bbox.right,
+ group_bbox.top,
+ group_bbox.bottom,
+ )
+
+ # Safebox adds points so that no Voronoi edge in clip_box is infinite
+ safe_box = (
+ 2 * clip_box[0] - clip_box[1],
+ 2 * clip_box[1] - clip_box[0],
+ 2 * clip_box[2] - clip_box[3],
+ 2 * clip_box[3] - clip_box[2],
+ )
+ pts.append(Point(safe_box[0], safe_box[2]))
+ pts.append(Point(safe_box[1], safe_box[2]))
+ pts.append(Point(safe_box[1], safe_box[3]))
+ pts.append(Point(safe_box[0], safe_box[3]))
+
+ if self.options.showClipBox:
+ # Add the clip box to the drawing
+ rect = group_voronoi.add(Rectangle())
+ rect.set("x", str(clip_box[0]))
+ rect.set("y", str(clip_box[2]))
+ rect.set("width", str(clip_box[1] - clip_box[0]))
+ rect.set("height", str(clip_box[3] - clip_box[2]))
+ rect.style = linestyle
+
+ # Voronoi diagram generation
+ if self.options.diagramType != "Delaunay":
+ vertices, lines, edges = voronoi.computeVoronoiDiagram(pts)
+ for edge in edges:
+ vindex1, vindex2 = edge[1:]
+ if (vindex1 < 0) or (vindex2 < 0):
+ continue # infinite lines have no need to be handled in the clipped box
+ else:
+ segment = self.clip_edge(vertices, lines, edge, clip_box)
+ # segment = [vertices[vindex1],vertices[vindex2]] # deactivate clipping
+ if len(segment) > 1:
+ x1, y1 = segment[0]
+ x2, y2 = segment[1]
+ cmds = [["M", [x1, y1]], ["L", [x2, y2]]]
+ path = group_voronoi.add(PathElement())
+ path.set("d", str(inkex.Path(cmds)))
+ path.style = linestyle
+
+ if self.options.diagramType != "Voronoi":
+ triangles = voronoi.computeDelaunayTriangulation(seeds)
+ i = 0
+ if self.options.delaunayFillOptions == "delaunay-fill":
+ random.seed("inkscape")
+ for triangle in triangles:
+ pt1 = seeds[triangle[0]]
+ pt2 = seeds[triangle[1]]
+ pt3 = seeds[triangle[2]]
+ cmds = [
+ ["M", [pt1.x, pt1.y]],
+ ["L", [pt2.x, pt2.y]],
+ ["L", [pt3.x, pt3.y]],
+ ["Z", []],
+ ]
+ if (
+ self.options.delaunayFillOptions == "delaunay-fill"
+ or self.options.delaunayFillOptions == "delaunay-fill-random"
+ ):
+ facestyle = {
+ "stroke": fills[triangle[random.randrange(0, 2)]],
+ "stroke-width": str(self.svg.to_dimensionless("0.005px")),
+ "fill": fills[triangle[random.randrange(0, 2)]],
+ "stroke-linecap": "round",
+ "stroke-linejoin": "round",
+ }
+ path = group_delaunay.add(PathElement())
+ path.set("d", str(inkex.Path(cmds)))
+ path.style = facestyle
+ i += 1
+
+
+if __name__ == "__main__":
+ Voronoi().run()
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 11:28:53 +0000