Source code for pymunk.util

# ----------------------------------------------------------------------------
# pymunk
# Copyright (c) 2007-2011 Victor Blomqvist
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
# ----------------------------------------------------------------------------

"""This submodule contains utility functions, mainly to help with polygon 
creation.

"""
from __future__ import division
__version__ = "$Id: util.py 439 2012-08-30 22:14:05Z vb@viblo.se $"
__docformat__ = "reStructuredText"

from math import sqrt
from .vec2d import Vec2d

X, Y = 0, 1 

try:
    from functools import partial
except ImportError:
    # Python 2.4 support
    def partial(func, *args, **keywords):
        def newfunc(*fargs, **fkeywords):
            newkeywords = keywords.copy()
            newkeywords.update(fkeywords)
            return func(*(args + fargs), **newkeywords)

        newfunc.func = func
        newfunc.args = args
        newfunc.keywords = keywords
        return newfunc

[docs]def is_clockwise(points): """ Check if the points given forms a clockwise polygon :return: True if the points forms a clockwise polygon """ a = 0 i, j = 0, 0 for i in range(len(points)): j = i + 1 if j == len(points): j = 0 a += points[i][X]*points[j][Y] - points[i][Y]*points[j][X] return a <= 0 #or is it the other way around?
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 """ # cast the answer to an int so it can be used directly from sort() # cast is not a good idea.. use something else #return int((p1.x - p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y)) sorting = (p1[X] - p0[X])*(p2[Y]-p0[Y]) - (p2[X]-p0[X])*(p1[Y]-p0[Y]) if sorting > 0: return 1 elif sorting < 0: return -1 else: return 0
[docs]def is_convex(points): """Test if a polygon (list of (x,y)) is convex or not :return: True if the polygon is convex, False otherwise """ assert len(points) > 2, "need at least 3 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[X] - p0[X], p1[Y] - p0[Y] # p1-p0 b = p2[X] - p1[X], p2[Y] - p1[Y] # p2-p1 if sign(a[X]) != sign(b[X]): xc +=1 if sign(a[Y]) != sign(b[Y]): yc +=1 p0, p1 = p1, p2 return xc <= 2 and yc <= 2
def sign(x): """Sign function. :return -1 if x < 0, else return 1 """ if x < 0: return -1 else: return 1
[docs]def reduce_poly(points, tolerance=0.5): """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) """ assert len(points) > 0, "reduce_poly can not simplify an empty points list" curr_p = points[0] reduced_ps = [points[0]] for p in points[1:]: distance = (curr_p[X] - p[X])**2 + (curr_p[Y] - p[Y])**2 if distance > tolerance: curr_p = p reduced_ps.append(p) return reduced_ps
[docs]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) """ assert len(points) > 2, "need at least 3 points to form a convex hull" ### Find lowest rightmost point p0 = points[0] for p in points[1:]: if p[Y] < p0[Y]: p0 = p elif p[Y] == p0[Y] and p[X] > p0[X]: 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
[docs]def calc_center(points): """Calculate the center of a polygon :return: The center (x,y) """ #ref: http://en.wikipedia.org/wiki/Polygon assert len(points) > 0, "need at least 1 points to calculate the center" area = calc_area(points) p1 = points[0] cx = cy = 0 for p2 in points[1:] + [points[0]]: tmp = (p1[X]*p2[Y] - p2[X]*p1[Y]) cx += (p1[X] + p2[X]) * tmp cy += (p1[Y] + p2[Y]) * tmp p1 = p2 c = 1 / (6. * area) * cx, 1 / (6. * area) * cy return c
[docs]def poly_vectors_around_center(pointlist, points_as_Vec2d=True): """Rearranges vectors around the center If points_as_Vec2d, then return points are also Vec2d, else pos :return: pointlist ([Vec2d/pos, ...]) """ poly_points_center = [] cx, cy = calc_center(pointlist) if points_as_Vec2d: for p in pointlist: x = p[X] - cx y = p[Y] - cy poly_points_center.append(Vec2d((x, y))) else: for p in pointlist: x = p[X] - cx y = cy - p[Y] poly_points_center.append((x, y)) return poly_points_center
[docs]def calc_area(points): """Calculate the area of a polygon :return: Area of polygon """ #ref: http://en.wikipedia.org/wiki/Polygon if len(points) < 3: return 0 p1 = points[0] a = 0 for p2 in points[1:] + [points[0]]: a += p1[X] * p2[Y] - p2[X] * p1[Y] p1 = p2 a = 0.5 * a return a
[docs]def calc_perimeter(points): """Calculate the perimeter of a polygon :return: Perimeter of polygon """ if len(points) < 2: return 0 p1 = points[0] c = 0 for p2 in points[1:] + [points[0]]: c += sqrt((p2[X] - p1[X])**2 + (p2[Y] - p1[Y])**2) p1 = p2 return c ### "hidden" functions
def _is_corner(a, b, c): # returns if point b is an outer corner return not(is_clockwise([a, b, c])) def _point_in_triangle(p, a, b, c): # measure area of whole triangle whole = abs(calc_area([a, b, c])) # measure areas of inner triangles formed by p parta = abs(calc_area([a, b, p])) partb = abs(calc_area([b, c, p])) partc = abs(calc_area([c, a, p])) # allow for potential rounding error in area calcs # (not that i've encountered one yet, but just in case...) thresh = 0.0000001 # return if the sum of the inner areas = the whole area return ((parta+partb+partc) < (whole+thresh)) def _get_ear(poly): count = len(poly) # not even a poly if count < 3: return [], [] # only a triangle anyway if count == 3: return poly, [] # start checking points for i in range(count): ia = (i-1) % count ib = i ic = (i+1) % count a = poly[ia] b = poly[ib] c = poly[ic] # is point b an outer corner? if _is_corner(a,b,c): # are there any other points inside triangle abc? valid = True for j in range(count): if not(j in (ia,ib,ic)): p = poly[j] if _point_in_triangle(p,a,b,c): valid = False # if no such point found, abc must be an "ear" if valid: remaining = [] for j in range(count): if j != ib: remaining.append(poly[j]) # return the ear, and what's left of the polygon after the ear is clipped return [a,b,c], remaining # no ear was found, so something is wrong with the given poly (not anticlockwise? self-intersects?) return [], [] def _attempt_reduction(hulla, hullb): inter = [vec for vec in hulla if vec in hullb] if len(inter) == 2: starta = hulla.index(inter[1]) tempa = hulla[starta:]+hulla[:starta] tempa = tempa[1:] startb = hullb.index(inter[0]) tempb = hullb[startb:]+hullb[:startb] tempb = tempb[1:] reduced = tempa+tempb if is_convex(reduced): return reduced # reduction failed, return None return None def _reduce_hulls(hulls): count = len(hulls) # 1 or less hulls passed if count < 2: return hulls, False # check all hulls in the list against each other for ia in range(count-1): for ib in range(ia+1, count): # see if hulls can be reduced to one reduction = _attempt_reduction(hulls[ia], hulls[ib]) if reduction != None: # they can so return a new list of hulls and a True newhulls = [reduction] for j in range(count): if not(j in (ia,ib)): newhulls.append(hulls[j]) return newhulls, True # nothing was reduced, send the original hull list back with a False return hulls, False ### major functions
[docs]def triangulate(poly): """Triangulates poly and returns a list of triangles :Parameters: poly list of points that form an anticlockwise polygon (self-intersecting polygons won't work, results are undefined) """ triangles = [] remaining = poly[:] # while the poly still needs clipping while len(remaining) > 2: # rotate the list: # this stops the starting point from getting stale which sometimes # a "fan" of polys, which often leads to poor convexisation remaining = remaining[1:]+remaining[:1] # clip the ear, store it ear, remaining = _get_ear(remaining) if ear != []: triangles.append(ear) # return stored triangles return triangles
[docs]def convexise(triangles): """Reduces a list of triangles (such as returned by triangulate()) to a non-optimum list of convex polygons :Parameters: triangles list of anticlockwise triangles (a list of three points) to reduce """ # fun fact: convexise probably isn't a real word hulls = triangles[:] reduced = True # keep trying to reduce until it won't reduce any more while reduced: hulls, reduced = _reduce_hulls(hulls) # return reduced hull list return hulls
__all__ = ["is_clockwise", "reduce_poly", "convex_hull", "calc_area", "calc_center", "poly_vectors_around_center", "is_convex", "calc_perimeter", "triangulate", "convexise"]

Table Of Contents