<s> """<STR_LIT>""" <EOL> __copyright__ = "<STR_LIT>" <EOL> import numpy <EOL> def _isLeft ( a , b , c ) : <EOL> """<STR_LIT>""" <EOL> return ( ( b [ <NUM_LIT:0> ] - a [ <NUM_LIT:0> ] ) * ( c [ <NUM_LIT:1> ] - a [ <NUM_LIT:1> ] ) - ( b [ <NUM_LIT:1> ] - a [ <NUM_LIT:1> ] ) * ( c [ <NUM_LIT:0> ] - a [ <NUM_LIT:0> ] ) ) > <NUM_LIT:0> <EOL> def _isRightTurn ( ( p , q , r ) ) : <EOL> sum1 = q [ <NUM_LIT:0> ] * r [ <NUM_LIT:1> ] + p [ <NUM_LIT:0> ] * q [ <NUM_LIT:1> ] + r [ <NUM_LIT:0> ] * p [ <NUM_LIT:1> ] <EOL> sum2 = q [ <NUM_LIT:0> ] * p [ <NUM_LIT:1> ] + r [ <NUM_LIT:0> ] * q [ <NUM_LIT:1> ] + p [ <NUM_LIT:0> ] * r [ <NUM_LIT:1> ] <EOL> if sum1 - sum2 < <NUM_LIT:0> : <EOL> return <NUM_LIT:1> <EOL> else : <EOL> return <NUM_LIT:0> <EOL> def convexHull ( pointList ) : <EOL> """<STR_LIT>""" <EOL> unique = { } <EOL> for p in pointList : <EOL> unique [ p [ <NUM_LIT:0> ] , p [ <NUM_LIT:1> ] ] = <NUM_LIT:1> <EOL> points = unique . keys ( ) <EOL> points . sort ( ) <EOL> if len ( points ) < <NUM_LIT:1> : <EOL> return numpy . zeros ( ( <NUM_LIT:0> , <NUM_LIT:2> ) , numpy . float32 ) <EOL> if len ( points ) < <NUM_LIT:2> : <EOL> return numpy . array ( points , numpy . float32 ) <EOL> upper = [ points [ <NUM_LIT:0> ] , points [ <NUM_LIT:1> ] ] <EOL> for p in points [ <NUM_LIT:2> : ] : <EOL> upper . append ( p ) <EOL> while len ( upper ) > <NUM_LIT:2> and not _isRightTurn ( upper [ - <NUM_LIT:3> : ] ) : <EOL> del upper [ - <NUM_LIT:2> ] <EOL> points = points [ : : - <NUM_LIT:1> ] <EOL> lower = [ points [ <NUM_LIT:0> ] , points [ <NUM_LIT:1> ] ] <EOL> for p in points [ <NUM_LIT:2> : ] : <EOL> lower . append ( p ) <EOL> while len ( lower ) > <NUM_LIT:2> and not _isRightTurn ( lower [ - <NUM_LIT:3> : ] ) : <EOL> del lower [ - <NUM_LIT:2> ] <EOL> del lower [ <NUM_LIT:0> ] <EOL> del lower [ - <NUM_LIT:1> ] <EOL> return numpy . array ( upper + lower , numpy . float32 ) <EOL> def minkowskiHull ( a , b ) : <EOL> """<STR_LIT>""" <EOL> points = numpy . zeros ( ( len ( a ) * len ( b ) , <NUM_LIT:2> ) ) <EOL> for n in xrange ( <NUM_LIT:0> , len ( a ) ) : <EOL> for m in xrange ( <NUM_LIT:0> , len ( b ) ) : <EOL> points [ n * len ( b ) + m ] = a [ n ] + b [ m ] <EOL> return convexHull ( points . copy ( ) ) <EOL> def _projectPoly ( poly , normal ) : <EOL> """<STR_LIT>""" <EOL> pMin = numpy . dot ( normal , poly [ <NUM_LIT:0> ] ) <EOL> pMax = pMin <EOL> for n in xrange ( <NUM_LIT:1> , len ( poly ) ) : <EOL> p = numpy . dot ( normal , poly [ n ] ) <EOL> pMin = min ( pMin , p ) <EOL> pMax = max ( pMax , p ) <EOL> return pMin , pMax <EOL> def polygonCollision ( polyA , polyB ) : <EOL> """<STR_LIT>""" <EOL> for n in xrange ( <NUM_LIT:0> , len ( polyA ) ) : <EOL> p0 = polyA [ n - <NUM_LIT:1> ] <EOL> p1 = polyA [ n ] <EOL> normal = ( p1 - p0 ) [ : : - <NUM_LIT:1> ] <EOL> normal [ <NUM_LIT:1> ] = - normal [ <NUM_LIT:1> ] <EOL> normal /= numpy . linalg . norm ( normal ) <EOL> aMin , aMax = _projectPoly ( polyA , normal ) <EOL> bMin , bMax = _projectPoly ( polyB , normal ) <EOL> if aMin > bMax : <EOL> return False <EOL> if bMin > aMax : <EOL> return False <EOL> for n in xrange ( <NUM_LIT:0> , len ( polyB ) ) : <EOL> p0 = polyB [ n - <NUM_LIT:1> ] <EOL> p1 = polyB [ n ] <EOL> normal = ( p1 - p0 ) [ : : - <NUM_LIT:1> ] <EOL> normal [ <NUM_LIT:1> ] = - normal [ <NUM_LIT:1> ] <EOL> normal /= numpy . linalg . norm ( normal ) <EOL> aMin , aMax = _projectPoly ( polyA , normal ) <EOL> bMin , bMax = _projectPoly ( polyB , normal ) <EOL> if aMin > bMax : <EOL> return False <EOL> if bMin > aMax : <EOL> return False <EOL> return True <EOL> def polygonCollisionPushVector ( polyA , polyB ) : <EOL> """<STR_LIT>""" <EOL> retSize = <NUM_LIT> <EOL> ret = False <EOL> for n in xrange ( <NUM_LIT:0> , len ( polyA ) ) : <EOL> p0 = polyA [ n - <NUM_LIT:1> ] <EOL> p1 = polyA [ n ] <EOL> normal = ( p1 - p0 ) [ : : - <NUM_LIT:1> ] <EOL> normal [ <NUM_LIT:1> ] = - normal [ <NUM_LIT:1> ] <EOL> normal /= numpy . linalg . norm ( normal ) <EOL> aMin , aMax = _projectPoly ( polyA , normal ) <EOL> bMin , bMax = _projectPoly ( polyB , normal ) <EOL> if aMin > bMax : <EOL> return False <EOL> if bMin > aMax : <EOL> return False <EOL> size = min ( aMax , bMax ) - max ( aMin , bMin ) <EOL> if size < retSize : <EOL> ret = normal * ( size + <NUM_LIT:0.1> ) <EOL> retSize = size <EOL> for n in xrange ( <NUM_LIT:0> , len ( polyB ) ) : <EOL> p0 = polyB [ n - <NUM_LIT:1> ] <EOL> p1 = polyB [ n ] <EOL> normal = ( p1 - p0 ) [ : : - <NUM_LIT:1> ] <EOL> normal [ <NUM_LIT:1> ] = - normal [ <NUM_LIT:1> ] <EOL> normal /= numpy . linalg . norm ( normal ) <EOL> aMin , aMax = _projectPoly ( polyA , normal ) <EOL> bMin , bMax = _projectPoly ( polyB , normal ) <EOL> if aMin > bMax : <EOL> return False <EOL> if bMin > aMax : <EOL> return False <EOL> size = min ( aMax , bMax ) - max ( aMin , bMin ) <EOL> if size < retSize : <EOL> ret = normal * - ( size + <NUM_LIT:0.1> ) <EOL> retSize = size <EOL> return ret <EOL> def fullInside ( polyA , polyB ) : <EOL> """<STR_LIT>""" <EOL> for n in xrange ( <NUM_LIT:0> , len ( polyA ) ) : <EOL> p0 = polyA [ n - <NUM_LIT:1> ] <EOL> p1 = polyA [ n ] <EOL> normal = ( p1 - p0 ) [ : : - <NUM_LIT:1> ] <EOL> normal [ <NUM_LIT:1> ] = - normal [ <NUM_LIT:1> ] <EOL> normal /= numpy . linalg . norm ( normal ) <EOL> aMin , aMax = _projectPoly ( polyA , normal ) <EOL> bMin , bMax = _projectPoly ( polyB , normal ) <EOL> if aMax > bMax : <EOL> return False <EOL> if aMin < bMin : <EOL> return False <EOL> for n in xrange ( <NUM_LIT:0> , len ( polyB ) ) : <EOL> p0 = polyB [ n - <NUM_LIT:1> ] <EOL> p1 = polyB [ n ] <EOL> normal = ( p1 - p0 ) [ : : - <NUM_LIT:1> ] <EOL> normal [ <NUM_LIT:1> ] = - normal [ <NUM_LIT:1> ] <EOL> normal /= numpy . linalg . norm ( normal ) <EOL> aMin , aMax = _projectPoly ( polyA , normal ) <EOL> bMin , bMax = _projectPoly ( polyB , normal ) <EOL> if aMax > bMax : <EOL> return False <EOL> if aMin < bMin : <EOL> return False <EOL> return True <EOL> def lineLineIntersection ( p0 , p1 , p2 , p3 ) : <EOL> """<STR_LIT>""" <EOL> A1 = p1 [ <NUM_LIT:1> ] - p0 [ <NUM_LIT:1> ] <EOL> B1 = p0 [ <NUM_LIT:0> ] - p1 [ <NUM_LIT:0> ] <EOL> C1 = A1 * p0 [ <NUM_LIT:0> ] + B1 * p0 [ <NUM_LIT:1> ] <EOL> A2 = p3 [ <NUM_LIT:1> ] - p2 [ <NUM_LIT:1> ] <EOL> B2 = p2 [ <NUM_LIT:0> ] - p3 [ <NUM_LIT:0> ] <EOL> C2 = A2 * p2 [ <NUM_LIT:0> ] + B2 * p2 [ <NUM_LIT:1> ] <EOL> det = A1 * B2 - A2 * B1 <EOL> if det == <NUM_LIT:0> : <EOL> return p0 <EOL> return [ ( B2 * C1 - B1 * C2 ) / det , ( A1 * C2 - A2 * C1 ) / det ] <EOL> def clipConvex ( poly0 , poly1 ) : <EOL> """<STR_LIT>""" <EOL> res = poly0 <EOL> for p1idx in xrange ( <NUM_LIT:0> , len ( poly1 ) ) : <EOL> src = res <EOL> res = [ ] <EOL> p0 = poly1 [ p1idx - <NUM_LIT:1> ] <EOL> p1 = poly1 [ p1idx ] <EOL> for n in xrange ( <NUM_LIT:0> , len ( src ) ) : <EOL> p = src [ n ] <EOL> if not _isLeft ( p0 , p1 , p ) : <EOL> if _isLeft ( p0 , p1 , src [ n - <NUM_LIT:1> ] ) : <EOL> res . append ( lineLineIntersection ( p0 , p1 , src [ n - <NUM_LIT:1> ] , p ) ) <EOL> res . append ( p ) <EOL> elif not _isLeft ( p0 , p1 , src [ n - <NUM_LIT:1> ] ) : <EOL> res . append ( lineLineIntersection ( p0 , p1 , src [ n - <NUM_LIT:1> ] , p ) ) <EOL> return numpy . array ( res , numpy . float32 ) </s>
