首页 > 代码库 > 二维凸包 Graham 算法
二维凸包 Graham 算法
三点以下的情况就不写了
Python:
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
Cpp:
#include <iostream> #include <cmath> #include <deque> #include <algorithm> using namespace std; class Point { public: Point( double x, double y ) { this->x = x; this->y = y; } Point( const Point& other ) { this->x = other.x; this->y = other.y; } bool operator < ( const Point& other ) const { if( this->y < other.y ) return true; else if( this->y == other.y ) { if( this->x < other.x ) return true; else return false; } else return false; } bool operator == ( const Point& other ) const { return ( this->x == other.x ) && ( this->y == other.y ); } friend ostream& operator << ( ostream& os, const Point& p ) { os << "( X: " << p.x << ", " << "Y: " << p.y << " )" << endl; return os; } double x; double y; }; Point start_point( 1 << 30, 1 << 30 ); deque< Point > points; deque< Point > result; double dist( const Point& p1, const Point& p2 ) { return sqrt( ( p1.x - p2.x ) * ( p1.x - p2.x ) + ( p1.y - p2.y ) * ( p1.y - p2.y ) ); } double crossMultiply( const Point& p1, const Point& p2, const Point& p3 ) { return ( ( p2.x - p1.x ) * ( p3.y - p1.y ) - ( p2.y - p1.y ) * ( p3.x - p1.x ) ); } bool cmp( const Point& p1, const Point& p2 ) { double m = crossMultiply( start_point, p1, p2 ); if( m < 0 ) return false; else if( m == 0 && ( dist( start_point, p1 ) < dist( start_point, p2 ) ) ) return false; else return true; } void graham() { for( int i = 0; i < points.size(); ++i ) if( points[i] < start_point ) start_point = points[i]; for( deque< Point >::iterator iter = points.begin(); iter != points.end(); ++iter ) { if( *iter == start_point ) { points.erase( iter ); break; } } sort( points.begin(), points.end(), cmp ); result.push_back( start_point ); result.push_back( points.front() ); points.pop_front(); result.push_back( points.front() ); points.pop_front(); for( int i = 0; i < points.size(); ++i ) { while( crossMultiply( result[result.size() - 2], result[result.size() - 1], points[i] ) <= 0 ) result.pop_back(); result.push_back( points[i] ); } } int main() { points.push_back( Point( 30, 30 ) ); points.push_back( Point( 50, 60 ) ); points.push_back( Point( 60, 20 ) ); points.push_back( Point( 70, 45 ) ); points.push_back( Point( 86, 39 ) ); points.push_back( Point( 112, 60 ) ); points.push_back( Point( 200, 113 ) ); points.push_back( Point( 250, 50 ) ); points.push_back( Point( 300, 200 ) ); points.push_back( Point( 130, 240 ) ); points.push_back( Point( 76, 150 ) ); points.push_back( Point( 47, 76 ) ); points.push_back( Point( 36, 40 ) ); points.push_back( Point( 33, 35 ) ); graham(); for( int i = 0; i < result.size(); ++i ){ cout << result[i]; } return 0; }
Free Pascal:
program Graham; type TPoint = record x : extended; y : extended; end; var points : array[1..10000] of TPoint; result : array[1..10000] of TPoint; top : Integer; points_num : Integer; i : Integer; procedure Swap( var a, b : TPoint ); inline; var temp : TPoint; begin temp := a; a := b; b := temp; end; procedure Init; inline; var i : Integer; begin readln( points_num ); for i := 1 to points_num do begin with points[i] do begin readln( x, y ); end end; for i := 1 to points_num do begin if ( points[i].y < points[1].y ) or ( points[i].y = points[1].y ) and ( points[i].x < points[1].x ) then begin Swap( points[1], points[i] ); end end; end; function CrossMultiply( p1, p2, p3 : TPoint ) : extended; inline; begin exit( ( p1.x - p3.x ) * ( p2.y - p3.y ) - ( p2.x - p3.x ) * ( p1.y - p3.y ) ); end; function Distance( p1, p2 : TPoint ) : extended; inline; begin exit( sqrt( ( p1.x - p2.x ) * ( p1.x - p2.x ) + ( p1.y - p2.y ) * ( p1.y - p2.y ) ) ); end; procedure Sort( x, y : longint ); inline; var xx, yy : longint; mid, temp : TPoint; begin xx := x; yy := y; mid := points[ ( xx + yy ) shr 1]; repeat while ( CrossMultiply( points[xx], mid, points[1] ) > 0 ) or ( CrossMultiply( points[xx], mid, points[1] ) = 0 ) and ( Distance( points[xx], points[1] ) < Distance( mid, points[1] ) ) do begin Inc( xx ); end; while ( CrossMultiply( points[yy], mid, points[1] ) < 0 ) or ( CrossMultiply( points[yy], mid, points[1] ) = 0 ) and ( Distance( points[yy], points[1] ) > Distance( mid, points[1] ) ) do begin Dec( yy ); end; if xx <= yy then begin Swap( points[xx], points[yy] ); Inc( xx ); Dec( yy ); end; until xx > yy; if yy > x then Sort( x, yy ); if xx < y then Sort( xx, y ); end; procedure Push( i : longint ); inline; begin inc( top ); result[top] := points[i]; end; procedure Graham; inline; var i : Integer; begin Sort( 2, points_num ); top := 0; Push( 1 ); Push( 2 ); for i := 3 to points_num do begin while ( top > 1 ) and ( CrossMultiply( points[i], result[top], result[top - 1] ) >= 0 ) do begin dec( top ); end; push( i ); end; end; begin Init; Graham; for i := 1 to top do begin writeln( result[i].x, result[i].y ); end; readln; end.
还差 Scheme, Ada,SML 版本的没写。。。。我是不是有强迫症。。。。
不对,还有 JS 动漫版的~
二维凸包 Graham 算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。