#!/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.selected:
            inkex.errormsg(_("Please select objects!"))
            return

        linestyle = {
            'stroke': '#000000',
            'stroke-width': str(self.svg.unittouu('1px')),
            'fill': 'none',
            'stroke-linecap': 'round',
            'stroke-linejoin': 'round'
        }

        facestyle = {
            'stroke': '#000000',
            'stroke-width': str(self.svg.unittouu('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.selected.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':
                svg = self.document.getroot()
                width = self.svg.unittouu(svg.get('width'))
                height = self.svg.unittouu(svg.get('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.unittouu('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()