グラハムスキャンアルゴリズム

凸包は、指定されたすべてのデータポイントをカバーできる最小の閉じた領域です。

グラハムのスキャンアルゴリズムは、凸包のコーナーポイントを見つけます。このアルゴリズムでは、最初に最低点が選択されます。その点が凸包の始点です。残りのn-1個の頂点は、始点から反時計回りの方向に基づいて並べ替えられます。 2つ以上の点が同じ角度を形成している場合は、開始点から最も遠い点を除いて、同じ角度のすべての点を削除します。

残りのポイントから、それらをスタックにプッシュします。そして、スタックのトップポイント、2番目のトップポイント、および新しく選択されたポイントポイント[i]の方向が反時計回りでない場合は、スタックからアイテムを1つずつ削除し、チェックした後、ポイント[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:
Boundary points of convex hull are:
(-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<iostream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;

struct point {    //define points for 2d plane
   int x, y;
};

point p0;    //used to another two points

point secondTop(stack<point>&stk) {
   point tempPoint = stk.top(); stk.pop();
   point res = stk.top();    //get the second top element
   stk.push(tempPoint);    //push previous top again
   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;    //anti-clockwise direction
      return 1;    //clockwise direction
}

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;  
}

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

   for(int i = 1; i<n; i++) {
      int y = points[i].y;
      //find bottom most or left most point
      if((y < minY) || (minY == y) && points[i].x < points[min].x) {
         minY = points[i].y;
         min = i;  
      }
   }

   swap(points[0], points[min]);    //swap min point to 0th location
   p0 = points[0];
   qsort(&points[1], n-1, sizeof(point), comp);    //sort points from 1 place to end
   
   int arrSize = 1;    //used to locate items in modified array
   for(int i = 1; i<n; i++) {

      //when the angle of ith and (i+1)th elements are same, remove points
      while(i < n-1 && direction(p0, points[i], points[i+1]) == 0)
         i++;
      points[arrSize] = points[i];
      arrSize++;
   }

   if(arrSize < 3)
      return convexHullPoints;    //there must be at least 3 points, return empty list.
         
      //create a stack and add first three points in the stack
      stack<point> stk;
      stk.push(points[0]); stk.push(points[1]); stk.push(points[2]);
   
      for(int i = 3; i<arrSize; i++) {    //for remaining vertices
         while(direction(secondTop(stk), stk.top(), points[i]) != 2)
            stk.pop();    //when top, second top and ith point are not making left turn, remove point
         stk.push(points[i]);
      }

      while(!stk.empty()) {
         convexHullPoints.push_back(stk.top());    //add points from stack
         stk.pop();
      }
}

int main() {
   point 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}};
   int n = 18;
   vector<point> result;
   result = findConvexHull(points, n);
   cout << "Boundary points of convex hull are: "<<endl;
   vector<point>::iterator it;

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

出力

Boundary points of convex hull are:
(-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)