Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

데이터 구조의 볼록 껍질 예제

<시간/>

여기에서 볼록 껍질에 대한 한 가지 예를 볼 수 있습니다. 점 집합이 있다고 가정합니다. 주어진 모든 점을 덮을 만큼 적은 양의 점을 사용하여 다각형을 만들어야 합니다. 이 섹션에서는 볼록 껍질을 얻기 위한 Jarvis March 알고리즘을 볼 것입니다.

Jarvis March 알고리즘은 주어진 데이터 포인트 세트에서 볼록 껍질의 코너 포인트를 감지하는 데 사용됩니다.

데이터 세트의 가장 왼쪽 지점에서 시작하여 시계 반대 방향 회전으로 볼록 껍질의 지점을 유지합니다. 현재 지점에서 현재 지점에서 해당 지점의 방향을 확인하여 다음 지점을 선택할 수 있습니다. 각도가 가장 클 때 점이 선택됩니다. 모든 포인트를 완료한 후 다음 포인트가 시작 포인트가 되면 알고리즘을 중지합니다.

입력 − 점 세트:{(-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)}

출력 − 볼록 껍질의 경계점은 다음과 같습니다. −

(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)

알고리즘

findConvexHull(points, n)
Input: The points, number of points.
Output: Corner points of convex hull.
Begin
   start := points[0]
   for each point i, do
      if points[i].x < start.x, then // get the left most point
         start := points[i]
   done
   current := start
   add start point to the result set.
   define colPts set to store collinear points
   while true, do //start an infinite loop
      next := points[i]
      for all points i except 0th point, do
         if points[i] = current, then
            skip the next part, go for next iteration
         val := cross product of current, next, points[i]
         if val > 0, then
            next := points[i]
            clear the colPts array
         else if cal = 0, then
            if next is closer to current than points[i], then
               add next in the colPts
               next := points[i]
            else
               add points[i] in the colPts
      done
      add all items in the colPts into the result
      if next = start, then
         break the loop
      insert next into the result
      current := next
   done
   return result
End

예시

#include<iostream>
#include<set>
#include<vector>
using namespace std;
struct point{ //define points for 2d plane
   int x, y;
   bool operator==(point p2){
      if(x == p2.x && y == p2.y)
         return 1;
      return 0;
   }
   bool operator<(const point &p2)const{ //dummy compare function used to sort in set
      return true;
   }
};
int crossProduct(point a, point b, point c){ //finds the place of c from ab vector
   int y1 = a.y - b.y;
   int y2 = a.y - c.y;
   int x1 = a.x - b.x;
   int x2 = a.x - c.x;
   return y2*x1 - y1*x2; //if result < 0, c in the left, > 0, c in the right, = 0, a,b,c are collinear
}
int distance(point a, point b, point c){
   int y1 = a.y - b.y;
   int y2 = a.y - c.y;
   int x1 = a.x - b.x;
   int x2 = a.x - c.x;
   int item1 = (y1*y1 + x1*x1);
   int item2 = (y2*y2 + x2*x2);
   if(item1 == item2)
      return 0; //when b and c are in same distance from a
   else if(item1 < item2)
      return -1; //when b is closer to a
   return 1; //when c is closer to a
}
set<point> findConvexHull(point points[], int n){
   point start = points[0];
   for(int i = 1; i<n; i++){ //find the left most point for starting
      if(points[i].x < start.x)
         start = points[i];
   }
   point current = start;
   set<point> result; //set is used to avoid entry of duplicate points
   result.insert(start);
   vector<point> *collinearPoints = new vector<point>;
   while(true){
      point nextTarget = points[0];
      for(int i = 1; i<n; i++){
         if(points[i] == current) //when selected point is current point, ignore rest part
            continue;
         int val = crossProduct(current, nextTarget, points[i]);
         if(val > 0){ //when ith point is on the left side
            nextTarget = points[i];
            collinearPoints = new vector<point>; //reset collinear points
         }else if(val == 0){ //if three points are collinear
            if(distance(current, nextTarget, points[i]) < 0){ //add closer one to collinear list
               collinearPoints->push_back(nextTarget);
               nextTarget = points[i];
            }else{
               collinearPoints->push_back(points[i]); //when ith point is closer or same as nextTarget
            }
         }
      }
      vector<point>::iterator it;
      for(it = collinearPoints->begin(); it != collinearPoints->end(); it++){
         result.insert(*it); //add allpoints in collinear points to result set
      }
      if(nextTarget == start) //when next point is start it means, the area covered
         break;
      result.insert(nextTarget);
      current = nextTarget;
   }
   return result;
}
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;
      set<point> result;
      result = findConvexHull(points, n);
      cout << "Boundary points of convex hull are: "<<endl;
      set<point>::iterator it;
      for(it = result.begin(); it!=result.end(); it++)
         cout << "(" << it->x << ", " <<it->y <<") ";
}

출력

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