C++で点集合から単純な閉じた経路（閉路）を求めるアルゴリズム

平面上に与えられた点の集合があり、そのすべての点をちょうど一度ずつ通る「単純な閉じた経路（単純閉路）」を見つけたいとします。下の図のような点が与えられた場合、これらの点を適切な順序で結ぶことで閉じたパスを構成できます。

アルゴリズムの考え方

この問題は、凸包を求める際に用いられる「偏角ソート」の考え方を応用することで解くことができます。具体的な手順は以下の通りです。

• 最も左下にある点（y座標が最小、同一の場合はx座標も最小）を基準点 P として選びます。

• 残りの n − 1 個の点を、P を中心とした反時計回りの偏角（極角）に基づいてソートします。2つの点の偏角が等しい場合は、P からの距離が近い方を先に配置します。

• ソート後の点のリストを先頭から順にたどり、その順序で経路を作ります。最後に基準点 P へ戻ることで、経路が閉じた環になります。

この手法により、自己交差しない単純閉路が必ず得られます。計算量はソートが支配的となるため、O(n log n) となります。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
class Point {
   public:
   int x, y;
};
Point p0;
int euclid_dist(Point p1, Point p2) {
   return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
int orientation(Point p1, Point p2, Point p3) {
   int val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
   if (val == 0) return 0; // 同一直線上
   return (val > 0)? 1: 2; // 時計回りまたは反時計回り
}
int compare(const void *vp1, const void *vp2) {
   Point *p1 = (Point *)vp1;
   Point *p2 = (Point *)vp2;
   int o = orientation(p0, *p1, *p2);
   if (o == 0)
   return (euclid_dist(p0, *p2) >= euclid_dist(p0, *p1))? -1 : 1;
   return (o == 2)? -1: 1;
}
void findClosedPath(Point points[], int n) {
   int y_min = points[0].y, min = 0;
   for (int i = 1; i < n; i++) {
      int y = points[i].y;
      if ((y < y_min) || (y_min == y && points[i].x < points[min].x))
      y_min = points[i].y, min = i;
   }
   swap(points[0], points[min]);
   p0 = points[0];
   qsort(&points[1], n-1, sizeof(Point), compare); // 偏角でソート
   for (int i=0; i<n; i++)
   cout << "(" << points[i].x << ", "<< points[i].y <<"), ";
}
int main() {
   Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},{0, 0}, {1, 2}, {3, 1}, {3, 3}};
   int n = sizeof(points)/sizeof(points[0]);
   findClosedPath(points, n);
}

実行結果

(0, 0), (3, 1), (1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (0, 3),

コードのポイント解説

1. 基準点の選択

findClosedPath 関数では、まず線形探索によって y 座標が最小の点を探し、同値が存在する場合は x 座標がより小さい方を選んで配列の先頭に移動しています。この点が偏角計算の原点となります。

2. 方向判定関数 orientation

外積の値を利用して、3点が同一直線上にあるか、時計回りか、反時計回りかを判定します。これは凸包アルゴリズムでも共通して使われる基本的なテクニックです。

3. 比較関数 compare

qsort 用の比較関数では、基準点 p0 から見た2点の偏角関係を orientation で判定し、同一直線上にある場合はユークリッド距離の二乗（euclid_dist）で距離の近い方を優先します。距離の二乗を使うことで、平方根の計算を避けて高速化しています。