"""
This file is part of the 'Elements' Project
Elements is a 2D Physics API for Python (supporting Box2D2)
Copyright (C) 2008, The Elements Team,
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 .
"""
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 *
from elements import box2d
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 = []
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 == 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 == 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