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"]