C++でのAngularSweepアルゴリズム

特定の半径の円で囲むことができるポイントの最大数を見つけるためのアルゴリズム。これは、半径rの円と特定の2次元点のセットについて、円で囲まれている（円の端ではなく円の内側にある）点の最大数を見つける必要があることを意味します。

なぜなら、これが最も効果的な方法は角度スイープアルゴリズムです。

アルゴリズム

• ⁿ があります C ₂ 問題で与えられた点については、これらの各点の間の距離を見つける必要があります。

• 任意の点を取り、その点を中心に回転したときに円内にある点の最大数を取得します P 。

• 問題の最終的な戻り値として囲むことができる最大ポイント数を返します。

例

#include <bits/stdc++.h>
using namespace std;
#define MAX_POINTS 500
typedef complex<double> Point;
Point arr[MAX_POINTS];
double dis[MAX_POINTS][MAX_POINTS];
int getPointsInside(int i, double r, int n) {
   vector <pair<double, bool> > angles;
   for (int j = 0; j < n; j++) {
      if (i != j && dis[i][j] <= 2*r) {
         double B = acos(dis[i][j]/(2*r));
         double A = arg(arr[j]-arr[i]);
         double alpha = A-B;
         double beta = A+B;
         angles.push_back(make_pair(alpha, true));
         angles.push_back(make_pair(beta, false));
      }
   }
   sort(angles.begin(), angles.end());
   int count = 1, res = 1;
   vector <pair<double, bool>>::iterator it;
   for (it=angles.begin(); it!=angles.end(); ++it) {
      if ((*it).second)
         count++;
      else
         count--;
      if (count > res)
         res = count;
   }
   return res;
}
int maxPoints(Point arr[], int n, int r) {
   for (int i = 0; i < n-1; i++)
      for (int j=i+1; j < n; j++)
         dis[i][j] = dis[j][i] = abs(arr[i]-arr[j]);
      int ans = 0;
      for (int i = 0; i < n; i++)
         ans = max(ans, getPointsInside(i, r, n));
      return ans;
}
int main() {
   Point arr[] = {Point(6.47634, 7.69628), Point(5.16828, 4.79915), Point(6.69533, 6.20378)};
   int r = 1;
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "The maximum number of points are: " << maxPoints(arr, n, r);
   return 0;
}

出力

The maximum number of points are: 2