유클리드 최단 경로(Euclidean Shortest Path)와 가시성 그래프(Visibility Graph)

유클리드 최단 경로

평면 상에 출발점과 도착점이 주어지면 그 사이를 잇는 최단 경로는 당연히 직선입니다. 하지만 만약 그 사이에 장애물이 존재한다면 돌아가야 하니 최단 경로를 계산하기가 아주 복잡해집니다. 이런 최단 경로 문제를 특별히 유클리드 최단 경로(Euclidean shortest path) 문제라고 합니다. 경로 최적화라는 이름으로 로봇 공학 등지에서 많이 연구되는 주제죠.

간단히 모든 장애물이 다각형이고, 다각형의 경계(꼭짓점과 변)을 지나는 건 가능하지만 내부는 지날 수 없는 경우를 살펴봅시다(장애물이 다각형이 아니더라도  경계에서 충분히 많은 점을 골라 다각형으로 근사할 수 있으므로 이 경우만 생각해도 충분합니다). 예를 하나 들자면 아래와 같은 문제입니다.

이때 출발점(파란색)과 도착점(빨간색) 사이 최단 경로는

장애물이 다각형인 경우에 유클리드 최단 경로는 다음 두 정리를 만족합니다.

정리 1) 유클리드 최단 경로는 다각형의 경계가 아닌 곳에서 방향이 바뀌지 않는다.

증명) 유클리드 최단 경로가 다각형의 경계가 아닌 곳에서 방향을 바꾼다고 해봅시다. 그러면 아래 그림과 같이 항상 더 짧은 경로를 찾을 수 있게 되므로, 모순입니다. ■

정리 2) 유클리드 최단 경로는 다각형의 꼭짓점이 아닌 변 위의 점에서 방향이 바뀌지 않는다.

증명) 정리 1과 똑같이 귀류법으로 증명합니다. 꼭짓점이 아닌 곳에서 방향이 바뀌는 경우는 변을 따라 진행하다 중간에 변에서 벗어나거나(또는 그 반대) 다각형 외부에서 변 위의 한 점을 찍고 다시 외부로 나가는 경우가 있는데, 어느 쪽이든 경로가 다각형 내부로는 들어갈 수 없기 때문에 항상 더 짧은 경로가 존재하게 됩니다(사실 그려보면 너무 자명합니다). ■

정리 1과 2에 의해, 유클리드 최단 경로는 항상 다각형의 꼭짓점에서만 방향을 바꿀 수 있습니다.

가시성 그래프

이제 풀이 과정은 자명합니다. 꼭짓점과 꼭짓점 사이에서는 직선이어야 하니, 두 꼭짓점 사이에 선분을 그었을 때 어떤 다각형의 내부를 지나지 않는 꼭짓점 쌍마다 이어줍시다. 다시 말해, 한쪽 꼭짓점에 서면 반대쪽이 장애물에 가리지 않고 잘 보이면 이어준다는 거죠. 이렇게 하면 아래와 같은 그래프가 나오고, 꼭짓점 사이의 가시성(visibility)에 따라 변을 연결했다고 해서 가시성 그래프(visibility graph)라고 부릅니다. 가시성 그래프를 만들고 나서는, 그냥 다익스트라로 최단거리를 구해주면 끝입니다!

가시성 그래프를 만드는 건 정의를 그대로 써서 할 수 있습니다. 모든 꼭짓점의 쌍에 대해 둘을 연결하는 선분이 어떤 다각형의 내부를 지나는지 확인합니다. 그렇다면 선분과 다각형의 충돌 판정은 어떻게 할까요? 이게 더럽습니다….

먼저 꼭짓점 $u$와 $v$를 선택했다고 합시다. 이 때 선분 $\overline{uv}$가 어떤 다각형 내부를 지나는 경우는 세 가지 중 적어도 하나입니다.

  1. $u$ 또는 $v$가 다각형 내부에 있을 때
  2. 다각형의 한 변과 $\overline{uv}$가 교차할 때
  3. $\overline{uv}$가 어떤 다각형의 대각선이면서 그 다각형의 내부를 지날 때

1번은 다각형끼리 겹치거나 출발점 또는 도착점이 다각형 내부에 존재할 수 있을 때만 확인하면 됩니다. 가장 중요한 것은 2번입니다. 변($\overline{ab}$라고 합시다)과 $\overline{uv}$의 교점이 $u$나 $v$면 겹치는 게 아니기 때문입니다. 그걸 겹친 걸로 판정해버리면 $\overline{uv}$가 어떤 다각형의 변이고 그와 인접한 변이 $\overline{ab}$인 경우 등이 문제가 되죠. 이 사실을 가장 기본적인 조건으로 깔면 $\overline{uv}$와 $\overline{ab}$의 위치 관계를 아래와 같이 나눌 수 있습니다.

겹침에 해당하는 경우를 살펴봅시다. 왼쪽은 당연히 겹치는 거고, 오른쪽이 문젠데 교점이 $a$나 $b$인 경우는 겹치는 걸로 처리해줘야 합니다. 그렇지 않으면 아래와 같은 경우를 안 겹치는 걸로 판정해버리거든요.

그런데 이러면 아래 경우에서 $\overline{uv}$가 다각형과 교차한다고 판정해버립니다만, 어차피 $uv$ 사이에 변이 안 만들어져도 $ua$ 사이와 $av$ 사이에 변이 만들어질 테니 별 문제는 없습니다. 오히려 중복되는 변을 제거할 수 있죠. 하나 덧붙이자면 안 겹침의 가장 오른쪽 둘 같은 경우도 교차로 판정해서 중복되는 변을 지울 수 있는데, 판정이 하나 더 들어가서 귀찮으니 넘어갑시다.

그 다음으로 $\overline{uv}$가 어떤 다각형의 대각선이면서 그 다각형의 내부를 지날 때를 판정해야 합니다. 이건 그냥 $u$와 $v$의 중점이 다각형 내부에 존재하는지 보면 됩니다. $\overline{uv}$가 다각형의 내부를 지나지 않는데 중점이 다각형 내부에 존재할리 없겠죠.

$\overline{uv}$ 사이에 변이 존재하는지 계산하는 데 걸리는 시간 복잡도를 계산해보면

  1. 점이 다각형 내부에 있는지 판정하는 건 다각형의 꼭짓점 개수를 $v$라 했을 때 $O(v)$입니다. 이걸 모든 다각형에 대해 다 해줘야 하니 모든 다각형의 꼭짓점 개수 총합을 $n$이라 하면 $O(n)$이 걸리겠네요.
  2. $\overline{uv}$와 모든 다각형의 변을 한 번씩 비교해봐야 하므로 역시 $O(n)$입니다(다각형의 변 개수=꼭짓점 개수).
  3. 1번과 똑같이 $O(n)$입니다.

그리고 $u$와 $v$의 쌍이 $n(n-1)/2$가지이므로 총 시간 복잡도는 $O(n^3)$이 됩니다.

이걸 정렬과 이진 트리를 써서 $O(n^2\log n)$으로 줄일 수 있는데 복잡하거니와 보통 이런 문제에선 $n$이 크지 않으므로 여기선 생략하겠습니다.

구현

  1. $u$와 $v$가 다각형에 포함되는지 검사하는 함수를 구현해야 합니다. 이때 다각형의 꼭짓점이나 변 위에 있는 경우는 포함 안 된 걸로 꼭 처리해야 합니다!
  2. 변이 $\overline{uv}$랑 교차하는 지 여부는 ccw로 해결하면 됩니다.
  3. $\overline{uv}$의 중점이 다각형에 포함되는지 검사하는 건 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:: 좀

https://www.acmicpc.net/problem/2125

연습문제입니다.

BOJ 5449:: Farmer John

https://www.acmicpc.net/problem/5449

장애물이 다각형 대신 선분으로, 훨씬 간단합니다.