格雷厄姆扫描算法

2023-06-21 06:45:03 278

凸包是可以覆盖所有给定数据点的最小封闭区域。

Graham的Scan算法会找到凸包的角点。在该算法中，首先选择最低点。该点是凸包的起点。剩余的n-1个顶点从起点开始按逆时针方向排序。如果两个或多个点形成相同的角度，则删除除距起点最远的点之外的所有相同角度的点。

从剩余的点开始，将它们压入堆栈。并逐个从堆栈中取出项目，当堆栈顶点、第二个顶点和新选择的点points[i]的方向不是逆时针时，检查后，将points[i]插入堆栈。

输入和输出

Input:
Set of points: {(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), (4,-6), (8,-7),(0,0), (3,-2),(6,-10),(0,-6),(-9,-5),(-8,-2),(-8,0),(-10,3),(-2,2),(-10,4)}
Output:
凸包的边界点是：
(-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

算法

findConvexHull(points, n)

输入-点集，点数。

输出-凸包的边界点。

Begin
   minY := points[0].y
   min := 0

   for i := 1 to n-1 do
      y := points[i].y
      if y < minY or minY = y and points[i].x < points[min].x, then
         minY := points[i].y
         min := i
   done

   swap points[0] and points[min]
   p0 := points[0]
   sort points from points[1] to end
   arrSize := 1

   for i := 1 to n, do
      when i < n-1 and (p0, points[i], points[i+1]) are collinear, do
         i := i + 1
      done
      points[arrSize] := points[i]
      arrSize := arrSize + 1
   done

   if arrSize < 3, then
      return cHullPoints
   push points[0] into stack
   push points[1] into stack
   push points[2] into stack

   for i := 3 to arrSize, do
      while top of stack, item below the top and points[i] is not in
         anticlockwise rotation, do
         delete top element from stack
      done
      push points[i] into stack
   done

   while stack is not empty, do
      item stack top element into cHullPoints
      pop from stack
   done
End

示例

#include
#include
#include
#include
using namespace std;

struct point {    //定义二维平面的点
   int x, y;
};

point p0;    //习惯了另外两点

point secondTop(stack&stk) {
   point tempPoint = stk.top(); stk.pop();
   point res = stk.top();    //获取第二个顶部元素
   stk.push(tempPoint);    //再次推上一个顶部
   return res;
}

int squaredDist(point p1, point p2) {
   return ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

int direction(point a, point b, point c) {
   int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
   if (val == 0)
      return 0;     //colinear
   else if(val < 0)
      return 2;    //逆时针方向
      return 1;    //顺时针方向
}

int comp(const void *point1, const void*point2) {
   point *p1 = (point*)point1;
   point *p2 = (point*)point2;
   int dir = direction(p0, *p1, *p2);

   if(dir == 0)
      return (squaredDist(p0, *p2) >= squaredDist(p0, *p1))?-1 : 1;
   return (dir==2)? -1 : 1;  
}

vectorfindConvexHull(point points[], int n) {
   vector convexHullPoints;
   int minY = points[0].y, min = 0;

   for(int i = 1; i stk;
      stk.push(points[0]); stk.push(points[1]); stk.push(points[2]);
   
      for(int i = 3; i result;
   result = findConvexHull(points, n);
   cout << "凸包的边界点是： "<::iterator it;

   for(it = result.begin(); it!=result.end(); it++)
      cout << "(" << it->x << ", " <y <<") ";
}

输出结果

凸包的边界点是：
(-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

格雷厄姆扫描算法

输入和输出

算法

示例

热门推荐

随机推荐