Web   ·   Wiki   ·   Activities   ·   Blog   ·   Lists   ·   Chat   ·   Meeting   ·   Bugs   ·   Git   ·   Translate   ·   Archive   ·   People   ·   Donate
 summaryrefslogtreecommitdiffstats log msg author committer range
path: root/elements/tools_poly.py
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiff
Diffstat (limited to 'elements/tools_poly.py')
-rw-r--r--elements/tools_poly.py266
1 files changed, 143 insertions, 123 deletions
 diff --git a/elements/tools_poly.py b/elements/tools_poly.pyindex 5ca3986..a2bb425 100644--- a/elements/tools_poly.py+++ b/elements/tools_poly.py@@ -8,7 +8,7 @@ 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 + 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@@ -22,7 +22,7 @@ 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 . +along with this program. If not, see . """ from functools import partial @@ -33,167 +33,177 @@ 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+ 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)- + 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)- + 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: + 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)- + # Create Vector+ vx, vy = (x2 - x1, y2 - y1)+ # Check Length- l = sqrt((vx*vx) + (vy*vy))- if l == 0.0: continue+ 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))+ 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- + """ 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 = [] p_new.append(vertices[0])- - dir = None ++ dir = None is_convex = True- - for i in xrange(len(vertices)-1):++ 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]+ 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))+ b = sqrt((v1x * v1x) + (v1y * v1y))+ c = sqrt((v2x * v2x) + (v2y * v2y))++ # No Division by 0 :)+ if (b * c) == 0.0:+ continue - # 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)))+ angle = degrees(acos(a / (b * c))) except: # cos=1.0- print "cos=", a/(b*c)+ 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])- + 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])+ 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]):+ 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: """ + """ 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@@ -205,110 +215,121 @@ def reduce_poly_by_angle(vertices, tolerance=10.0, minlen=20): p_old = (x2, y2) # Make Vector- vx, vy = (x2-x1, y2-y1)- + vx, vy = (x2 - x1, y2 - y1)+ # Vector length- l = sqrt((vx*vx) + (vy*vy))- + 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))+ else:+ alpha = degrees(atan2(vy, vx)) - if alpha_old == None:+ if alpha_old is None: alpha_old = alpha continue- + # Get difference to previous angle- alpha_diff = fabs(alpha - alpha_old) + 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])+ 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 +++# 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 - """ + 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] ++ 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 - + 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))+ 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@@ -319,21 +340,21 @@ def convex_hull(points): 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.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) + l = is_left(pt2, pt1, p) if l > 0: hull.append(p) else:@@ -343,5 +364,4 @@ def convex_hull(points): pt2 = hull[-2] l = is_left(pt2, pt1, p) hull.append(p)- return hull - + return hull