diff options
| -rw-r--r-- | helpers.py | 122 | ||||
| -rw-r--r-- | tools.py | 7 |
2 files changed, 127 insertions, 2 deletions
@@ -20,3 +20,125 @@ def constructTriangleFromLine(p1,p2): p3 = (p1[0] + halfHeightVector[0], p1[1] - halfHeightVector[1]) p4 = (p1[0] - halfHeightVector[0], p1[1] + halfHeightVector[1]) return [p2,p3,p4] + +# returns the area of a polygon +def polyArea(vertices): + n = len(vertices) + A = 0 + p=n-1 + q=0 + while q<n: + A+=vertices[p][0]*vertices[q][1] - vertices[q][0]*vertices[p][1] + p=q + q += 1 + return A/2.0 + +#Some polygon magic, thanks to John W. Ratcliff on www.flipcode.com + +# returns true if pt is in triangle +def insideTriangle(pt,triangle): + + ax = triangle[2][0] - triangle[1][0] + ay = triangle[2][1] - triangle[1][1] + bx = triangle[0][0] - triangle[2][0] + by = triangle[0][1] - triangle[2][1] + cx = triangle[1][0] - triangle[0][0] + cy = triangle[1][1] - triangle[0][1] + apx= pt[0] - triangle[0][0] + apy= pt[1] - triangle[0][1] + bpx= pt[0] - triangle[1][0] + bpy= pt[1] - triangle[1][1] + cpx= pt[0] - triangle[2][0] + cpy= pt[1] - triangle[2][1] + + aCROSSbp = ax*bpy - ay*bpx + cCROSSap = cx*apy - cy*apx + bCROSScp = bx*cpy - by*cpx + return aCROSSbp >= 0.0 and bCROSScp >= 0.0 and cCROSSap >= 0.0 + +def polySnip(vertices,u,v,w,n): + EPSILON = 0.0000000001 + + Ax = vertices[u][0] + Ay = vertices[u][1] + + Bx = vertices[v][0] + By = vertices[v][1] + + Cx = vertices[w][0] + Cy = vertices[w][1] + + if EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))): return False + + for p in range(0,n): + if p == u or p == v or p == w: continue + Px = vertices[p][0]; + Py = vertices[p][1]; + if insideTriangle((Px,Py),((Ax,Ay),(Bx,By),(Cx,Cy))): return False; + + return True; + + +# decomposes a polygon into its triangles +def decomposePoly(vertices): + vertices = list(vertices) + n = len(vertices) + result = [] + if(n < 3): return [] # not a poly! + + # force a counter-clockwise polygon + if 0 >= polyArea(vertices): + vertices.reverse() + + # remove nv-2 vertices, creating 1 triangle every time + nv = n + count = 2*nv # error detection + m=0 + v=nv-1 + while nv>2: + count -= 1 + if 0>= count: + return [] # Error -- probably bad polygon + + # three consecutive vertices + u = v + if nv<=u: u = 0 # previous + v = u+1 + if nv<=v: v = 0 # new v + w = v+1 + if nv<=w: w = 0 # next + + if(polySnip(vertices,u,v,w,nv)): + + # record this triangle + result.append((vertices[u],vertices[v],vertices[w])) + + m+=1 + # remove v from remaining polygon + vertices.pop(v) + nv -= 1 + # reset error detection + count = 2*nv + return result + + + + + + + + + + + + + + + + + + + + + +
\ No newline at end of file @@ -161,8 +161,11 @@ class PolygonTool(Tool): if not self.vertices: self.vertices=[event.pos] elif distance(event.pos,self.vertices[0]) < 15: - self.vertices.append(self.vertices[0]) #connect the polygon - self.game.world.add.complexPoly(self.vertices, dynamic=True, density=1.0, restitution=0.16, friction=0.5) + #self.vertices.append(self.vertices[0]) #connect the polygon + gons = decomposePoly(self.vertices) + for g in gons: + self.game.world.add.convexPoly(g, dynamic=True, density=1.0, restitution=0.16, friction=0.5) + #self.game.world.add.complexPoly(self.vertices, dynamic=True, density=1.0, restitution=0.16, friction=0.5) self.vertices = None else: self.vertices.append(event.pos) |