# Copyright (C) 2013 -- CJlano < cjlano @ free.fr >
# Copyright (C) 2022 -- svg2mod developers < GitHub.com / svg2mod >

# 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.,
# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

'''
This module contains all the geometric classes and functions not directly
related to SVG parsing. It can be reused outside the scope of SVG.
'''

import math
import numbers
import operator

class Point:
    '''Define a point as two floats accessible by x and y'''
    def __init__(self, x=None, y=None):
        '''A Point is defined either by a tuple/list of length 2 or
           by 2 coordinates
        >>> Point(1,2)
        (1.000,2.000)
        >>> Point((1,2))
        (1.000,2.000)
        >>> Point([1,2])
        (1.000,2.000)
        >>> Point('1', '2')
        (1.000,2.000)
        >>> Point(('1', None))
        (1.000,0.000)
        '''
        if (isinstance(x, tuple) or isinstance(x, list)) and len(x) == 2:
            x,y = x

        # Handle empty parameter(s) which should be interpreted as 0
        if x is None: x = 0
        if y is None: y = 0

        try:
            self.x = float(x)
            self.y = float(y)
        except:
            raise TypeError("A Point is defined by 2 numbers or a tuple")

    def __add__(self, other):
        '''Add 2 points by adding coordinates.
        Try to convert other to Point if necessary
        >>> Point(1,2) + Point(3,2)
        (4.000,4.000)
        >>> Point(1,2) + (3,2)
        (4.000,4.000)'''
        if not isinstance(other, Point):
            try: other = Point(other)
            except: return NotImplemented
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        '''Subtract two Points.
        >>> Point(1,2) - Point(3,2)
        (-2.000,0.000)
        '''
        if not isinstance(other, Point):
            try: other = Point(other)
            except: return NotImplemented
        return Point(self.x - other.x, self.y - other.y)

    def __mul__(self, other):
        '''Multiply a Point with a constant.
        >>> 2 * Point(1,2)
        (2.000,4.000)
        >>> Point(1,2) * Point(1,2) #doctest:+IGNORE_EXCEPTION_DETAIL
        Traceback (most recent call last):
            ...
        TypeError:
        '''
        if not isinstance(other, numbers.Real):
            return NotImplemented
        return Point(self.x * other, self.y * other)
    def __rmul__(self, other):
        return self.__mul__(other)

    def __eq__(self, other):
        '''Test equality
        >>> Point(1,2) == (1,2)
        True
        >>> Point(1,2) == Point(2,1)
        False
        '''
        if not isinstance(other, Point):
            try: other = Point(other)
            except: return NotImplemented
        return (self.x == other.x) and (self.y == other.y)

    def __repr__(self):
        return '(' + format(self.x,'.3f') + ',' + format( self.y,'.3f') + ')'

    def __str__(self):
        return self.__repr__()

    def coord(self):
        '''Return the point tuple (x,y)'''
        return (self.x, self.y)

    def length(self):
        '''Vector length, Pythagoras theorem'''
        return math.sqrt(self.x ** 2 + self.y ** 2)

    def rot(self, angle, x=0, y=0):
        '''Rotate vector [Origin,self] '''
        if not isinstance(angle, Angle):
            try: angle = Angle(angle)
            except: return NotImplemented
        if angle.angle % (2 * math.pi) == 0:
            return Point(self.x,self.y)

        new_x = ((self.x-x) * angle.cos) - ((self.y-y) * angle.sin) + x
        new_y = ((self.x-x) * angle.sin) + ((self.y-y) * angle.cos) + y
        return Point(new_x,new_y)

    def round(self, num_digits=None):
        '''Round x and y to number of decimal points'''
        return Point( round(self.x, num_digits), round(self.y, num_digits))


class Angle:
    '''Define a trigonometric angle [of a vector] '''
    def __init__(self, arg):
        if isinstance(arg, numbers.Real):
        # We precompute sin and cos for rotations
            self.angle = arg
            self.cos = math.cos(self.angle)
            self.sin = math.sin(self.angle)
        elif isinstance(arg, Point):
        # Point angle is the trigonometric angle of the vector [origin, Point]
            pt = arg
            try:
                self.cos = pt.x/pt.length()
                self.sin = pt.y/pt.length()
            except ZeroDivisionError:
                self.cos = 1
                self.sin = 0

            self.angle = math.acos(self.cos)
            if self.sin < 0:
                self.angle = -self.angle
        else:
            raise TypeError("Angle is defined by a number or a Point")

    def __neg__(self):
        return Angle(Point(self.cos, -self.sin))
    def __add__(self, other):
        if not isinstance(other, Angle):
            try: other = Angle(other)
            except: return NotImplemented
        return Angle(self.angle+other.angle)

class Segment:
    '''A segment is an object defined by 2 points'''
    def __init__(self, start, end):
        self.start = start
        self.end = end

    def __str__(self):
        return 'Segment from ' + str(self.start) + ' to ' + str(self.end)

    def segments(self, __=0):
        ''' Segments is simply the segment start -> end'''
        return [self.start, self.end]

    def length(self):
        '''Segment length, Pythagoras theorem'''
        s = self.end - self.start
        return math.sqrt(s.x ** 2 + s.y ** 2)

    def pdistance(self, p):
        '''Perpendicular distance between this Segment and a given Point p'''
        if not isinstance(p, Point):
            return NotImplemented

        if self.start == self.end:
        # Distance from a Point to another Point is length of a segment
            return Segment(self.start, p).length()

        s = self.end - self.start
        if s.x == 0:
        # Vertical Segment => pdistance is the difference of abscissa
            return abs(self.start.x - p.x)
        # That's 2-D perpendicular distance formula (ref: Wikipedia)
        slope = s.y/s.x
        # intercept: Crossing with ordinate y-axis
        intercept = self.start.y - (slope * self.start.x)
        return abs(slope * p.x - p.y + intercept) / math.sqrt(slope ** 2 + 1)


    def bbox(self):
        '''Return bounding box as ( Point(min), Point(max )'''
        xmin = min(self.start.x, self.end.x)
        xmax = max(self.start.x, self.end.x)
        ymin = min(self.start.y, self.end.y)
        ymax = max(self.start.y, self.end.y)

        return (Point(xmin,ymin),Point(xmax,ymax))

    def transform(self, matrix):
        '''Transform start and end point by provided matrix'''
        self.start = matrix * self.start
        self.end = matrix * self.end

class Bezier:
    '''Bezier curve class
       A Bezier curve is defined by its control points
       Its dimension is equal to the number of control points
       Note that SVG only support dimension 3 and 4 Bezier curve, respectively
       Quadratic and Cubic Bezier curve'''
    def __init__(self, pts):
        self.pts = list(pts)
        self.dimension = len(pts)

    def __str__(self):
        return 'Bezier' + str(self.dimension) + \
                ' : ' + ", ".join([str(x) for x in self.pts])

    def control_point(self, n):
        '''Return Point at index n'''
        if n >= self.dimension:
            raise LookupError('Index is larger than Bezier curve dimension')
        return self.pts[n]

    def r_length(self):
        '''Rough Bezier length: length of control point segments'''
        pts = list(self.pts)
        l = 0.0
        p1 = pts.pop()
        while pts:
            p2 = pts.pop()
            l += Segment(p1, p2).length()
            p1 = p2
        return l

    def bbox(self):
        '''This returns the rough bounding box '''
        return self.r_bbox()

    def r_bbox(self):
        '''Rough bounding box: return the bounding box (P1,P2) of the Bezier
        _control_ points'''
        xmin = min([p.x for p in self.pts])
        xmax = max([p.x for p in self.pts])
        ymin = min([p.y for p in self.pts])
        ymax = max([p.y for p in self.pts])

        return (Point(xmin,ymin), Point(xmax,ymax))

    def segments(self, precision=0):
        '''Return a poly-line approximation ("segments") of the Bezier curve
           precision is the minimum significant length of a segment'''
        segments = []
        # n is the number of Bezier points to draw according to precision
        if precision != 0:
            n = int(self.r_length() / precision) + 1
        else:
            n = 1000
        #if n < 10: n = 10
        if n > 1000 : n = 1000

        for t in range(0, n+1):
            segments.append(self._bezierN(float(t)/n))
        return segments

    @staticmethod
    def _bezier1(p0, p1, t):
        '''Bezier curve, one dimension
        Compute the Point corresponding to a linear Bezier curve between
        p0 and p1 at "time" t '''
        pt = p0 + t * (p1 - p0)
        return pt

    def _bezierN(self, t):
        '''Bezier curve, Nth dimension
        Compute the point of the Nth dimension Bezier curve at "time" t'''
        # We reduce the N Bezier control points by computing the linear Bezier
        # point of each control point segment, creating N-1 control points
        # until we reach one single point
        res = list(self.pts)
        # We store the resulting Bezier points in res[], recursively
        for n in range(self.dimension, 1, -1):
            # For each control point of nth dimension,
            # compute linear Bezier point a t
            for i in range(0,n-1):
                res[i] = Bezier._bezier1(res[i], res[i+1], t)
        return res[0]

    def transform(self, matrix):
        '''Transform every point by the provided matrix'''
        self.pts = [matrix * x for x in self.pts]

class MoveTo:
    '''MoveTo class
    This will create a move without creating a segment
    to the destination point.
    '''
    def __init__(self, dest):
        self.dest = dest

    def bbox(self):
        '''This returns a single point bounding box. ( Point(destination), Point(destination) )'''
        return (self.dest, self.dest)

    def transform(self, matrix):
        '''Transform the destination point by provided matrix'''
        self.dest = matrix * self.dest


def simplify_segment(segment, epsilon):
    '''Ramer-Douglas-Peucker algorithm'''
    if len(segment) < 3 or epsilon <= 0:
        return segment[:]

    l = Segment(segment[0], segment[-1]) # Longest segment

    # Find the furthest point from the segment
    index, maxDist = max([(i, l.pdistance(p)) for i,p in enumerate(segment)],
            key=operator.itemgetter(1))

    if maxDist > epsilon:
        # Recursively call with segment split in 2 on its furthest point
        r1 = simplify_segment(segment[:index+1], epsilon)
        r2 = simplify_segment(segment[index:], epsilon)
        # Remove redundant 'middle' Point
        return r1[:-1] + r2
    return [segment[0], segment[-1]]
