볼록 다각형의 민코프스키 합¶
정의¶
평면 위의 점들로 이루어진 두 집합 $A$와 $B$를 생각해 봅시다. 민코프스키 합 $A + B$는 $\{a + b| a \in A, b \in B\}$로 정의됩니다. 여기서는 $A$와 $B$가 각각 내부를 포함한 볼록 다각형 $P$와 $Q$로 이루어진 경우를 다룹니다. 이 글 전체에서 다각형을 그 정점들의 순서 있는 수열과 동일시하므로, $|P|$나 $P_i$ 같은 표기가 의미를 가집니다. 볼록 다각형 $P$와 $Q$의 합은 정점이 최대 $|P| + |Q|$개인 볼록 다각형이 됩니다.
알고리즘¶
여기서는 다각형의 정점 번호가 순환한다고 간주합니다. 즉, $P_{|P|} = P_0,\ Q_{|Q|} = Q_0$이며 나머지도 마찬가지입니다.
합의 크기는 원래 다각형들의 크기에 대해 선형이므로, 선형 시간 알고리즘을 찾는 것을 목표로 해야 합니다. 두 다각형 모두 반시계 방향으로 정렬되어 있다고 가정합시다. 편각 순으로 정렬된 간선 수열 $\{\overrightarrow{P_iP_{i+1}}\}$과 $\{\overrightarrow{Q_jQ_{j+1}}\}$을 생각해 봅시다. $P + Q$의 간선 수열은 이 두 수열을 편각 순서를 유지하며 병합하고, 연속된 같은 방향의 벡터들을 그 합으로 대체하여 얻을 수 있다고 주장합니다. 이 아이디어를 그대로 사용하면 선형 시간 알고리즘을 얻을 수 있지만, 변의 수열로부터 $P + Q$의 정점을 복원하려면 벡터 덧셈을 반복해야 하므로 부동소수점 좌표를 다루는 경우 원치 않는 정밀도 문제가 생길 수 있습니다. 따라서 이 아이디어를 약간 변형한 방법을 설명하겠습니다.
먼저 각 다각형의 첫 번째 정점이 가장 작은 y좌표를 갖도록 정점의 순서를 재배열해야 합니다(그러한 정점이 여러 개라면 x좌표가 가장 작은 것을 고릅니다). 그러면 두 다각형의 변이 편각 순으로 정렬되므로, 따로 정렬할 필요가 없습니다. 이제 두 포인터 $i$($P$의 정점을 가리킴)와 $j$($Q$의 정점을 가리킴)를 만들고, 둘 다 처음에 0으로 설정합니다. $i < |P|$ 또는 $j < |Q|$인 동안 다음 단계를 반복합니다.
-
$P_i + Q_j$를 $P + Q$에 추가합니다.
-
$\overrightarrow{P_iP_{i + 1}}$과 $\overrightarrow{Q_jQ_{j+1}}$의 편각을 비교합니다.
-
더 작은 각에 해당하는 포인터를 증가시킵니다(각이 같으면 둘 다 증가시킵니다).
시각화¶
무슨 일이 일어나는지 이해하는 데 도움이 될 만한 좋은 시각화 자료가 있습니다.
두 다각형 사이의 거리¶
민코프스키 합의 가장 흔한 응용 중 하나는 두 볼록 다각형 사이의 거리를 계산하는 것(또는 단순히 두 다각형이 교차하는지 확인하는 것)입니다. 두 볼록 다각형 $P$와 $Q$ 사이의 거리는 $\min\limits_{a \in P, b \in Q} ||a - b||$로 정의됩니다. 두 다각형이 교차하면 이 거리는 $0$입니다. 그렇지 않으면 최소 거리는 두 정점 사이 또는 정점과 간선 사이에서 얻어지므로, 모든 쌍을 단순하게 확인하면 $O(|P||Q|)$ 시간이 걸립니다. 하지만 민코프스키 합을 영리하게 사용하면 복잡도를 $O(|P| + |Q|)$로 줄일 수 있습니다.
$Q$를 점 $(0, 0)$에 대해 대칭 이동하여 다각형 $-Q$를 얻으면, 문제는 $P + (-Q)$의 점과 $(0, 0)$ 사이의 최소 거리를 구하는 문제로 귀결됩니다. 다음 아이디어를 이용하면 이 거리를 선형 시간에 구할 수 있습니다. $(0, 0)$이 다각형의 내부 또는 경계 위에 있으면 거리는 $0$이고, 그렇지 않으면 거리는 $(0, 0)$과 다각형의 어떤 정점 또는 간선 사이에서 얻어집니다. 민코프스키 합은 선형 시간에 계산할 수 있으므로, 두 볼록 다각형 사이의 거리를 구하는 선형 시간 알고리즘을 얻습니다.
구현¶
다음은 정수 좌표 점으로 이루어진 다각형에 대한 민코프스키 합의 구현입니다. 이 경우 편각을 계산해 직접 비교하는 대신 두 벡터의 외적 부호를 보면 되므로, 모든 계산을 정수로 수행할 수 있습니다.
struct pt{
long long x, y;
pt operator + (const pt & p) const {
return pt{x + p.x, y + p.y};
}
pt operator - (const pt & p) const {
return pt{x - p.x, y - p.y};
}
long long cross(const pt & p) const {
return x * p.y - y * p.x;
}
};
void reorder_polygon(vector<pt> & P){
size_t pos = 0;
for(size_t i = 1; i < P.size(); i++){
if(P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
pos = i;
}
rotate(P.begin(), P.begin() + pos, P.end());
}
vector<pt> minkowski(vector<pt> P, vector<pt> Q){
// the first vertex must be the lowest
reorder_polygon(P);
reorder_polygon(Q);
// we must ensure cyclic indexing
P.push_back(P[0]);
P.push_back(P[1]);
Q.push_back(Q[0]);
Q.push_back(Q[1]);
// main part
vector<pt> result;
size_t i = 0, j = 0;
while(i < P.size() - 2 || j < Q.size() - 2){
result.push_back(P[i] + Q[j]);
auto cross = (P[i + 1] - P[i]).cross(Q[j + 1] - Q[j]);
if(cross >= 0 && i < P.size() - 2)
++i;
if(cross <= 0 && j < Q.size() - 2)
++j;
}
return result;
}