プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

ジャービスマーチアルゴリズム


ジャービスマーチアルゴリズムは、特定のデータポイントのセットから凸包のコーナーポイントを検出するために使用されます。

データセットの左端のポイントから開始して、反時計回りの回転によって凸包内のポイントを保持します。現在のポイントから、現在のポイントからのそれらのポイントの方向を確認することにより、次のポイントを選択できます。角度が最大の場合、ポイントが選択されます。すべてのポイントを完了した後、次のポイントが開始ポイントになったら、アルゴリズムを停止します。

入力と出力

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) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)

アルゴリズム

findConvexHull(points, n)

入力: ポイント、ポイント数。

出力: 凸包のコーナーポイント。

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)

  1. フロイドウォーシャルアルゴリズム

    Floyd-Warshallアルゴリズムを使用して、特定の重み付きグラフからすべてのペアの最短経路問題を見つけます。このアルゴリズムの結果として、グラフ内の任意のノードから他のすべてのノードまでの最小距離を表す行列が生成されます。 最初、出力行列はグラフの指定されたコスト行列と同じです。その後、出力行列はすべての頂点kを中間頂点として更新されます。 このアルゴリズムの時間計算量はO(V ^ 3)です。ここで、Vはグラフ内の頂点の数です。 入力と出力 Input: The cost matrix of the graph. 0 3 6 ∞ ∞ ∞ &

  2. C++のコンピュータグラフィックスにおけるポイントクリッピングアルゴリズム

    コンピュータグラフィックスは、コンピュータ画面に画像やグラフィックスを描画することを扱います。ここでは、画面を2次元座標系として扱います。この座標系は左上(0,0)から始まり、右下で終わります。 表示平面 コンピュータグラフィックスでグラフィックスを描画するために定義された領域です。または画面の表示領域。 クリッピングとは、表示面の外側にあるポイントまたはグラフィックを削除することです。 クリッピングを理解するために例を見てみましょう。 ここで、ポイントCとDは、青色でマークされた表示平面の外側にあるため、クリップされます。 コンピュータグラフィックスのポイントをクリップするた