유클리드 최단 경로
평면 상에 출발점과 도착점이 주어지면 그 사이를 잇는 최단 경로는 당연히 직선입니다. 하지만 만약 그 사이에 장애물이 존재한다면 돌아가야 하니 최단 경로를 계산하기가 아주 복잡해집니다. 이런 최단 경로 문제를 특별히 유클리드 최단 경로(Euclidean shortest path) 문제라고 합니다. 경로 최적화라는 이름으로 로봇 공학 등지에서 많이 연구되는 주제죠.
간단히 모든 장애물이 다각형이고, 다각형의 경계(꼭짓점과 변)에 닿아서 이동하는 건 가능하지만 내부를 지날 수는 없는 문제를 생각해봅시다. 장애물이 다각형이 아니더라도 경계에서 충분히 많은 점을 골라 다각형으로 근사할 수 있으니 문제 없습니다. 아래 그림은 한 예시입니다.
이때 출발점(파란색)과 도착점(빨간색) 사이 최단 경로는 다음과 같습니다.
장애물이 다각형인 경우에 유클리드 최단 경로는 다음 정리를 만족합니다.
유클리드 최단 경로는 다각형의 꼭짓점에서만 방향을 바꿀 수 있다.
만약 다각형의 꼭짓점 또는 변 위가 아닌 곳에서 방향을 바꾼다면, 항상 더 짧은 경로를 찾을 수 있으므로 모순입니다.
마찬가지로 꼭짓점이 아닌 변 위에서 방향을 바꾸는 것 또한 불가능합니다.
가시성 그래프
이제 풀이 과정은 자명합니다. 꼭짓점과 꼭짓점 사이에서는 직선이어야 하니, 두 꼭짓점 사이에 선분을 그었을 때 어떤 다각형의 내부를 지나지 않는 꼭짓점 쌍마다 이어줍시다. 다시 말해, 한쪽 꼭짓점에 서면 반대쪽이 장애물에 가리지 않고 잘 보이면 이어준다는 거죠. 이렇게 하면 아래와 같은 그래프가 나오고, 꼭짓점 사이의 가시성(visibility)에 따라 변을 연결했다고 해서 가시성 그래프(visibility graph)라고 부릅니다. 가시성 그래프를 만들고 나서는, 그냥 다익스트라로 최단거리를 구해주면 끝입니다.
가시성 그래프를 만드는 건 정의를 그대로 써서 할 수 있습니다. 모든 꼭짓점의 쌍에 대해 둘을 연결하는 선분이 어떤 다각형의 내부를 지나는지 확인합니다. 그렇다면 선분과 다각형의 충돌 판정은 어떻게 할까요? 먼저 꼭짓점 $u$와 $v$를 선택했다고 합시다. 이때 선분 $\overline{uv}$가 어떤 다각형 내부를 지나는 경우는 세 가지 중 적어도 하나입니다.
- $u$ 또는 $v$가 다각형 내부에 있을 때
- 다각형의 한 변과 $\overline{uv}$가 교차할 때
- $\overline{uv}$가 어떤 다각형의 대각선이면서 그 다각형의 내부를 지날 때
1번은 다각형끼리 겹치거나 출발점 또는 도착점이 다각형 내부에 있을 때만 가능한 경우인데 이를 확인하는 건 쉽습니다. 가장 중요한 것은 2번입니다. 다각형의 변 $\overline{ab}$와 선분 $\overline{uv}$ 사이 위치 관계는 다음과 같이 나눌 수 있습니다.
겹침에 해당하는 경우를 살펴봅시다. 왼쪽은 당연히 겹치는 거고, 오른쪽이 문젠데 둘의 교점이 $a$나 $b$인 경우는 겹치는 걸로 처리해줘야 합니다. 아니면 아래 경우를 안 겹치는 걸로 판정해버립니다.
그런데 이러면 아래 경우에서 $\overline{uv}$가 다각형 내부를 지난다고 판정해버립니다만, 어차피 $uv$ 사이에 변이 안 만들어져도 $ua$ 사이와 $av$ 사이에 변이 만들어질 테니 별 문제는 없습니다. 오히려 중복되는 변을 제거할 수 있죠. 하나 덧붙이자면 안 겹침의 가장 오른쪽 둘 같은 경우도 교차로 판정해서 중복되는 변을 지울 수 있는데, 판정이 하나 더 들어가서 귀찮으니 넘어갑시다.
그 다음으로 $\overline{uv}$가 어떤 다각형의 대각선이면서 그 다각형의 내부를 지날 때를 판정해야 합니다. 이건 그냥 $u$와 $v$의 중점이 다각형 내부에 존재하는지 보면 됩니다. $\overline{uv}$가 다각형의 내부를 지나지 않는데 중점이 다각형 내부에 존재할리 없겠죠. 물론 $\overline{uv}$가 다각형 내부를 지나면서 중점은 다각형 외부에 있을 수는 있지만 이렇게 되려면 반드시 다각형의 다른 변과 교차해야 합니다.
모든 다각형의 꼭짓점과 변의 개수를 $n$개라 하면 $\overline{uv}$가 다각형 내부를 지나는지 판정하는 데 $O(n)$의 시간이 걸립니다. 그리고 $u$와 $v$의 쌍이 총 $O(n^2)$가지이므로 전체 시간 복잡도는 $O(n^3)$입니다. 물론 이게 최선은 아니고, 정렬과 이진 트리를 사용하여 $O(n^2\log n)$에 푸는 알고리즘도 있습니다.
구현
- $u$와 $v$가 다각형에 포함되는지 검사해야 합니다. 이때 다각형의 꼭짓점이나 변 위에 있는 경우는 포함 안 되는 걸로 처리합니다.
- 변이 $\overline{uv}$와 교차하는지 여부는 CCW로 해결할 수 있습니다.
- 중점이 다각형의 내부에 있는지 판정하는 것은 1번과 동일합니다.
using namespace std;
using ll = long long;
struct Point {
ll x, y;
Point() {}
Point(ll _x, ll _y) : x(_x), y(_y) {}
double len(void) {return sqrt(this->x * this->x + this->y * this->y);}
};
bool operator==(Point lhs, Point rhs) {return lhs.x == rhs.x && lhs.y == rhs.y;}
Point operator+(Point lhs, Point rhs) {return Point(lhs.x + rhs.x, lhs.y + rhs.y);}
Point operator-(Point lhs, Point rhs) {return Point(lhs.x - rhs.x, lhs.y - rhs.y);}
Point operator*(ll a, Point p) {return Point(a * p.x, a * p.y);}
ll operator*(Point lhs, Point rhs) {return lhs.x * rhs.x + lhs.y * rhs.y;}
ll operator^(Point lhs, Point rhs) {return lhs.x * rhs.y - lhs.y * rhs.x;}
using Polygon = vector<Point>;
const double INF = 1e18;
inline ll ccw(Point a, Point b, Point c) {
return (b-a)^(c-b);
}
// u, v, a가 같은 직선 위에 있으면서 a가 u와 v 사이에 있는가?
inline bool is_collinear_order(Point u, Point v, Point a) {
return ccw(u, v, a) == 0 && (a-u)*(v-u) > 0 && (a-u)*(v-u) < (v-u)*(v-u);
}
// u와 v의 중점이 p 내부에 있는가?
bool is_midpoint_in_polygon(Point u, Point v, Polygon &p) {
int cross = 0;
for (int i = 0; i < (int)p.size(); i++) {
int j = (i + 1) % p.size();
// 중점이 p의 꼭짓점과 겹칠 경우
if (u + v == 2*p[i])
return false;
// 중점이 p의 변과 겹칠 경우
if (is_collinear_order(2*p[i], 2*p[j], u + v))
return false;
if ((2*p[i].y > u.y + v.y) != (2*p[j].y > u.y + v.y)) {
ll a = (u.y + v.y - 2*p[i].y) * (p[j].x - p[i].x);
ll b = (u.x + v.x - 2*p[i].x) * (p[j].y - p[i].y);
if ((p[j].y > p[i].y && a > b) || (p[j].y < p[i].y && a < b))
cross++;
}
}
return cross % 2 > 0;
}
// 선분 uv와 선분 ab가 겹치는가? (단, 겹치는 점이 u 또는 v인 경우는 제외)
inline bool is_intersect(Point u, Point v, Point a, Point b) {
return ccw(u, v, a) * ccw(u, v, b) <= 0 && ccw(a, b, u) * ccw(a, b, v) < 0;
}
// u와 v가 서로 볼 수 있는가?
bool is_visible(Point u, Point v, vector<Polygon> &polygons) {
for (Polygon &p : polygons)
if (is_midpoint_in_polygon(u, u, p) || is_midpoint_in_polygon(v, v, p))
return false;
if (u == v)
return true;
for (Polygon &p : polygons) {
for (int i = 0; i < (int)p.size(); i++)
if (is_intersect(u, v, p[i], p[(i+1) % p.size()]))
return false;
if (is_midpoint_in_polygon(u, v, p))
return false;
}
return true;
}
double euclidean_shortest_path(Point s, Point t, vector<Polygon> &polygons) {
int v = 0;
vector<Point> points;
for (Polygon &p: polygons) {
v += p.size();
points.insert(points.end(), p.begin(), p.end());
}
points.push_back(s);
points.push_back(t);
vector<vector<pair<double, int>>> adj(v+2, vector<pair<double, int>>());
for (int i = 0; i <= v; i++)
for (int j = i+1; j <= v+1; j++)
if (is_visible(points[i], points[j], polygons)) {
double d = (points[i] - points[j]).len();
adj[i].push_back(make_pair(d, j));
adj[j].push_back(make_pair(d, i));
}
vector<double> dist(v+2, INF);
vector<bool> visited(v+2, false);
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
dist[v] = 0;
pq.push(make_pair(0, v));
vector<int> prev(v+2, -1);
while (!pq.empty()) {
int cur = pq.top().second;
pq.pop();
if (visited[cur])
continue;
visited[cur] = true;
for (auto &p : adj[cur]) {
double d = p.first;
int nxt = p.second;
if (dist[nxt] > dist[cur] + d) {
dist[nxt] = dist[cur] + d;
pq.push(make_pair(dist[nxt], nxt));
prev[nxt] = cur;
}
}
}
return dist[v+1];
}
응용
BOJ 2125:: 좀
연습문제입니다.
BOJ 5449:: Farmer John
장애물이 다각형 대신 선분으로, 훨씬 간단합니다.