"""
This file is part of the 'Elements' Project
Elements is a 2D Physics API for Python (supporting Box2D2)

Copyright (C) 2008, The Elements Team, <elements@linuxuser.at>

Home:  http://elements.linuxuser.at
IRC:   #elements on irc.freenode.org

Code:  http://www.assembla.com/wiki/show/elements
       svn co http://svn2.assembla.com/svn/elements

License:  GPLv3 | See LICENSE for the full text
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 3 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, see <http://www.gnu.org/licenses/>.
"""
from functools import partial

from math import fabs
from math import sqrt
from math import atan2
from math import degrees
from math import acos

from .locals import *


def calc_center(points):
    """ Calculate the center of a polygon

        Return: The center (x,y)
    """
    tot_x, tot_y = 0, 0
    for p in points:
        tot_x += p[0]
        tot_y += p[1]
    n = len(points)
    return (tot_x / n, tot_y / n)


def poly_center_vertices(pointlist):
    """ Rearranges vectors around the center

        Return: pointlist ([(x, y), ...])
    """
    poly_points_center = []
    cx, cy = calc_center(pointlist)

    for p in pointlist:
        x = p[0] - cx
        y = cy - p[1]
        poly_points_center.append((x, y))

    return poly_points_center


def is_line(vertices, tolerance=25.0):
    """ Check if passed vertices are a line. Done by comparing
        the angles of all vectors and check tolerance.

        Parameters:
          vertices ... a list of vertices (x, y)
          tolerance .. how many degrees should be allowed max to be a line

        Returns: True if line, False if no line
    """
    if len(vertices) <= 2:
        return True

    # Step 1: Points -> Vectors
    p_old = vertices[0]
    alphas = []

    for p in vertices[1:]:
        x1, y1 = p_old
        x2, y2 = p
        p_old = p

        # Create Vector
        vx, vy = (x2 - x1, y2 - y1)

        # Check Length
        l = sqrt((vx * vx) + (vy * vy))
        if l == 0.0:
            continue

        # Normalize vector
        vx /= l
        vy /= l

        # Append angle
        if fabs(vx) < 0.2:
            alpha = 90.0
        else:
            alpha = degrees(atan2(vy, vx))

        alphas.append(fabs(alpha))

    # Sort angles
    alphas.sort()

    # Get maximum difference
    alpha_diff = fabs(alphas[-1] - alphas[0])
    print "alpha difference:", alpha_diff

    if alpha_diff < tolerance:
        return True
    else:
        return False


def reduce_poly_by_angle(vertices, tolerance=10.0, minlen=20):
    """ This function reduces a poly by the angles of the vectors
        (detect lines).
        If the angle difference from one vector to the last > tolerance:
        use last point.
        If the angle is quite the same, it's on the line.

        Parameters:
          vertices ... a list of vertices (x, y)
          tolerance .. how many degrees should be allowed max

        Returns: (1) New Pointlist, (2) Soft reduced pointlist (reduce_poly())
    """
    v_last = vertices[-1]
    vertices = vxx = reduce_poly(vertices, minlen)

    p_new = []
    p_new.append(vertices[0])

    dir = None
    is_convex = True

    for i in xrange(len(vertices) - 1):
        if i == 0:
            p_old = vertices[i]
            continue

        x1, y1 = p_old
        x2, y2 = vertices[i]
        x3, y3 = vertices[i + 1]
        p_old = vertices[i]

        # Create Vectors
        v1x = (x2 - x1) * 1.0
        v1y = (y2 - y1) * 1.0

        v2x = (x3 - x2) * 1.0
        v2y = (y3 - y2) * 1.0

        # Calculate angle
        a = ((v1x * v2x) + (v1y * v2y))
        b = sqrt((v1x * v1x) + (v1y * v1y))
        c = sqrt((v2x * v2x) + (v2y * v2y))

        # No Division by 0 :)
        if (b * c) == 0.0:
            continue

        # Get the current degrees
        # We have a bug here sometimes...
        try:
            angle = degrees(acos(a / (b * c)))
        except:
            # cos=1.0
            print "cos=", a / (b * c)
            continue

        # Check if inside tolerance
        if fabs(angle) > tolerance:
            p_new.append(vertices[i])
            # print "x", 180-angle, is_left(vertices[i-1],
            # vertices[i], vertices[i+1])

            # Check if convex:
            if dir is None:
                dir = is_left(vertices[i - 1], vertices[i], vertices[i + 1])
            else:
                if dir != is_left(vertices[i - 1], vertices[i],
                                  vertices[i + 1]):
                    is_convex = False

    # We also want to append the last point :)
    p_new.append(v_last)

    # Returns: (1) New Pointlist, (2) Soft reduced pointlist (reduce_poly())
    return p_new, is_convex

    """ OLD FUNCTION: """
    # Wipe all points too close to each other
    vxx = vertices = reduce_poly(vertices, minlen)

    # Create Output List
    p_new = []
    p_new.append(vertices[0])

    # Set the starting vertice
    p_old = vertices[0]
    alpha_old = None

    # For each vector, compare the angle difference to the last one
    for i in range(1, len(vertices)):
        x1, y1 = p_old
        x2, y2 = vertices[i]
        p_old = (x2, y2)

        # Make Vector
        vx, vy = (x2 - x1, y2 - y1)

        # Vector length
        l = sqrt((vx * vx) + (vy * vy))

        # normalize
        vx /= l
        vy /= l

        # Get Angle
        if fabs(vx) < 0.2:
            alpha = 90
        else:
            alpha = degrees(atan2(vy, vx))

        if alpha_old is None:
            alpha_old = alpha
            continue

        # Get difference to previous angle
        alpha_diff = fabs(alpha - alpha_old)
        alpha_old = alpha

        # If the new vector differs from the old one, we add the old point
        # to the output list, as the line changed it's way :)
        if alpha_diff > tolerance:
            # print ">",alpha_diff, "\t", vx, vy, l
            p_new.append(vertices[i - 1])

    # We also want to append the last point :)
    p_new.append(vertices[-1])

    # Returns: (1) New Pointlist, (2) Soft reduced pointlist (reduce_poly())
    return p_new, vxx


# The following functions is_left, reduce_poly and convex_hull are
# from the pymunk project (http://code.google.com/p/pymunk/)
def is_left(p0, p1, p2):
    """Test if p2 is left, on or right of the (infinite) line (p0,p1).

    :return: > 0 for p2 left of the line through p0 and p1
        = 0 for p2 on the line
        < 0 for p2 right of the line
    """
    sorting = (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * \
              (p1[1] - p0[1])
    if sorting > 0:
        return 1
    elif sorting < 0:
        return -1
    else:
        return 0


def is_convex(points):
    """Test if a polygon (list of (x,y)) is strictly convex or not.

    :return: True if the polygon is convex, False otherwise
    """
    #assert len(points) > 2, "not enough points to form a polygon"

    p0 = points[0]
    p1 = points[1]
    p2 = points[2]

    xc, yc = 0, 0
    is_same_winding = is_left(p0, p1, p2)
    for p2 in points[2:] + [p0] + [p1]:
        if is_same_winding != is_left(p0, p1, p2):
            return False
        a = p1[0] - p0[0], p1[1] - p0[1]  # p1-p0
        b = p2[0] - p1[0], p2[1] - p1[1]  # p2-p1
        if sign(a[0]) != sign(b[0]):
            xc += 1
        if sign(a[1]) != sign(b[1]):
            yc += 1
        p0, p1 = p1, p2

    return xc <= 2 and yc <= 2


def sign(x):
    if x < 0:
        return -1
    else:
        return 1


def reduce_poly(points, tolerance=50):
    """Remove close points to simplify a polyline
    tolerance is the min distance between two points squared.

    :return: The reduced polygon as a list of (x,y)
    """
    curr_p = points[0]
    reduced_ps = [points[0]]

    for p in points[1:]:
        x1, y1 = curr_p
        x2, y2 = p
        dx = fabs(x2 - x1)
        dy = fabs(y2 - y1)
        l = sqrt((dx * dx) + (dy * dy))
        if l > tolerance:
            curr_p = p
            reduced_ps.append(p)

    return reduced_ps


def convex_hull(points):
    """Create a convex hull from a list of points.
    This function uses the Graham Scan Algorithm.

    :return: Convex hull as a list of (x,y)
    """
    # Find lowest rightmost point
    p0 = points[0]
    for p in points[1:]:
        if p[1] < p0[1]:
            p0 = p
        elif p[1] == p0[1] and p[0] > p0[0]:
            p0 = p
    points.remove(p0)

    # Sort the points angularly about p0 as center
    f = partial(is_left, p0)
    points.sort(cmp=f)
    points.reverse()
    points.insert(0, p0)

    # Find the hull points
    hull = [p0, points[1]]

    for p in points[2:]:

        pt1 = hull[-1]
        pt2 = hull[-2]
        l = is_left(pt2, pt1, p)
        if l > 0:
            hull.append(p)
        else:
            while l <= 0 and len(hull) > 2:
                hull.pop()
                pt1 = hull[-1]
                pt2 = hull[-2]
                l = is_left(pt2, pt1, p)
            hull.append(p)
    return hull
