首页 > 代码库 > 凸包 Graham 算法
凸包 Graham 算法
import math class Point( object ): def __init__( self, x, y ): self.x = x self.y = y def __cmp__( self, other ): if self.y < other.y: return -1 elif self.y == other.y: if self.x < other.x: return -1 elif self.x == other.x: return 0 else: return 1 else: return 1 def __repr__( self ): return "(X: {x}, Y:{y})".format( x = self.x, y = self.y ) @staticmethod def distance( p1, p2 ): return math.sqrt( ( p1.x - p2.x ) * ( p1.x - p2.x ) + ( p1.y - p2.y ) * ( p1.y - p2.y ) ) @staticmethod def crossMultiply( p1, p2, p3 ): return ( p2.x - p1.x ) * ( p3.y - p1.y ) - ( p2.y - p1.y ) * ( p3.x - p1.x ) points = [] results = [] def graham(): def find_start_point(): res = Point( float( 'inf' ), float( 'inf' ) ) for p in points: if res > p: res = p return res def _cmp( p1, p2 ): m = Point.crossMultiply( start_point, p1, p2 ) if m < 0: return 1 elif m == 0 and Point.distance( start_point, p1 ) < Point.distance( start_point, p2 ): return 1 else: return -1 global points, results start_point = find_start_point() points.remove( start_point ) points = sorted( points, _cmp ) results.extend( [start_point, points.pop( 0 ), points.pop( 0 )] ) for p in points: while ( Point.crossMultiply( results[-2], results[-1], p ) ) <= 0: results.pop() results.append( p ) return results if __name__ == "__main__": points.extend( [ Point( 30, 30 ), Point( 50, 60 ), Point( 60, 20 ), Point( 70, 45 ), Point( 86, 39 ), Point( 112, 60 ), Point( 200, 113 ), Point( 250, 50 ), Point( 300, 200 ), Point( 130, 240 ), Point( 76, 150 ), Point( 47, 76 ), Point( 36, 40 ), Point( 33, 35 ) ] ) res = graham() print res
凸包 Graham 算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。