Cắt đa giác (Sutherland-Hodgman) và giao đa giác lồi
Thuật toán Sutherland-Hodgman cắt một đa giác (kể cả lõm) bởi nửa mặt phẳng hoặc đa giác lồi, dùng để tính diện tích giao hai đa giác lồi và diện tích phần đa giác nằm trong một vùng lồi.
Cắt đa giác (polygon clipping) là phép lấy phần của một đa giác nằm bên trong một vùng cho trước. Thuật toán Sutherland-Hodgman làm việc này khi vùng cắt là một nửa mặt phẳng hoặc một đa giác lồi: lần lượt cắt đa giác bởi từng nửa mặt phẳng tạo bởi các cạnh của vùng cắt. Mỗi lần cắt chỉ là một vòng lặp qua đỉnh hiện tại, nên cài đặt rất ngắn và ít lỗi.
Ứng dụng điển hình: tính diện tích giao của hai đa giác lồi (hai hình chữ nhật xoay, tam giác và hình vuông, ...), cắt một đa giác (kể cả không lồi) bởi một số ít đường thẳng rồi đo diện tích phần còn lại, hoặc dựng tường minh giao của vài nửa mặt phẳng trong một khung chữ nhật. Giới hạn điển hình: tổng số đỉnh nhân số lần cắt khoảng đến .
Ý tưởng / Trực giác
Cắt bởi một nửa mặt phẳng. Gọi là nửa mặt phẳng bên trái đường thẳng có hướng , tức các điểm có . Duyệt các cạnh của đa giác theo thứ tự:
- nếu thì giữ ;
- nếu và nằm ở hai phía của đường thẳng thì thêm giao điểm của cạnh với đường thẳng.
Đa giác kết quả gồm các đoạn biên cũ nằm trong , nối với nhau bằng các đoạn trên đường thẳng. Giao điểm tính theo tỉ lệ khoảng cách có dấu: với và trái dấu, giao điểm là .
Cắt bởi đa giác lồi. Một đa giác lồi (ngược chiều kim đồng hồ) đúng bằng giao của các nửa mặt phẳng bên trái mỗi cạnh của nó. Vì , ta cắt lần lượt bởi từng cạnh. Nếu vùng cắt không lồi thì không viết được nó dưới dạng giao các nửa mặt phẳng, và thuật toán cho kết quả sai.
Đa giác bị cắt không cần lồi. Khi lõm, có thể gồm nhiều mảnh rời nhau. Sutherland-Hodgman vẫn trả về một dãy đỉnh, trong đó các mảnh được nối bằng những "cầu" có độ dày chạy đi rồi chạy về trên đường thẳng cắt. Đa giác đó suy biến, nhưng diện tích có dấu (công thức shoelace) của nó vẫn đúng bằng tổng diện tích các mảnh: mỗi cầu được đi qua hai lần theo hai chiều ngược nhau nên đóng góp triệt tiêu. Vì vậy nếu chỉ cần diện tích thì không phải tách mảnh.
Diện tích có dấu. Với đa giác :
dương khi các đỉnh đi ngược chiều kim đồng hồ. Chuẩn hóa cả hai đa giác về chiều ngược kim đồng hồ trước khi cắt, để "bên trái cạnh" đúng là "bên trong vùng cắt".
Ví dụ chạy tay
Cắt hình vuông bởi tam giác (cả hai ngược chiều kim đồng hồ).
5 |
| ++
4 |.....##.
|....####
3 |....####
|...#####+
2 |...#####+
|..######++
1 |........
|........
+----------
0 1 2 3 4 5
# : thuộc P ∩ C (kết quả) . : chỉ thuộc P + : chỉ thuộc C
(mỗi ký tự là một ô 0.5 x 0.5)
| Cạnh của | Giá trị cross tại các đỉnh hiện tại | Đa giác sau khi cắt | Diện tích |
|---|---|---|---|
| , , , | |||
| , , , | |||
| , , , , |
Ở bước 2, cạnh đi từ trong () ra ngoài (), giao điểm ở tỉ lệ , tức ; cạnh đi từ ngoài vào trong, giao điểm . Kiểm chứng: tam giác có diện tích ; phần nằm trên là tam giác nhỏ diện tích , phần nằm bên phải là tam giác diện tích ; còn lại .
Đa giác lõm. Cắt chữ U (diện tích ), chỉ giữ phần . Kết quả là một dãy đỉnh duy nhất : hai "cánh" của chữ U nối với nhau bằng đoạn và đoạn quay về nằm trên đường thẳng . Diện tích có dấu bằng , đúng bằng hai hình vuông đơn vị.
Cài đặt
Dữ liệu: đa giác ( đỉnh nguyên, có thể lõm, theo chiều bất kỳ) và đa giác lồi ( đỉnh). In diện tích .
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
struct Pt {
ld x, y;
};
Pt operator-(Pt a, Pt b) { return {a.x - b.x, a.y - b.y}; }
Pt operator+(Pt a, Pt b) { return {a.x + b.x, a.y + b.y}; }
Pt operator*(Pt a, ld t) { return {a.x * t, a.y * t}; }
ld cross(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }
ld cross(Pt o, Pt a, Pt b) { return cross(a - o, b - o); } // > 0 nếu o, a, b ngược chiều kim đồng hồ
// Diện tích có dấu (dương nếu các đỉnh ngược chiều kim đồng hồ)
ld signedArea(const vector<Pt>& p) {
ld s = 0;
for (size_t i = 0, k = p.size(); i < k; i++) s += cross(p[i], p[(i + 1) % k]);
return s / 2;
}
// Giữ phần đa giác nằm bên trái (hoặc trên) đường thẳng có hướng a -> b
vector<Pt> clipHalfPlane(const vector<Pt>& poly, Pt a, Pt b) {
vector<Pt> out;
size_t k = poly.size();
for (size_t i = 0; i < k; i++) {
Pt cur = poly[i], nxt = poly[(i + 1) % k];
ld ca = cross(a, b, cur), cb = cross(a, b, nxt);
if (ca >= 0) out.push_back(cur); // đỉnh hiện tại nằm trong: giữ
if ((ca > 0 && cb < 0) || (ca < 0 && cb > 0)) // cạnh cắt ngang đường thẳng
out.push_back(cur + (nxt - cur) * (ca / (ca - cb))); // thêm giao điểm
}
return out;
}
// Giao của đa giác bất kỳ (subject) với đa giác LỒI (clip), cả hai ngược chiều kim đồng hồ
vector<Pt> clipConvex(vector<Pt> subject, const vector<Pt>& clip) {
size_t m = clip.size();
for (size_t j = 0; j < m && !subject.empty(); j++) subject = clipHalfPlane(subject, clip[j], clip[(j + 1) % m]);
return subject;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n;
vector<Pt> P(n);
for (auto& p : P) cin >> p.x >> p.y;
cin >> m;
vector<Pt> C(m);
for (auto& p : C) cin >> p.x >> p.y;
if (signedArea(P) < 0) reverse(P.begin(), P.end()); // chuẩn hóa ngược chiều kim đồng hồ
if (signedArea(C) < 0) reverse(C.begin(), C.end());
vector<Pt> R = clipConvex(P, C);
cout << fixed << setprecision(6) << (double)signedArea(R) << '\n';
}
import sys
def cross(o, a, b): # > 0 nếu o, a, b ngược chiều kim đồng hồ
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
def signed_area(p): # dương nếu các đỉnh ngược chiều kim đồng hồ
k = len(p)
return sum(p[i][0] * p[(i + 1) % k][1] - p[i][1] * p[(i + 1) % k][0] for i in range(k)) / 2
def clip_half_plane(poly, a, b):
"""Giữ phần đa giác nằm bên trái (hoặc trên) đường thẳng có hướng a -> b."""
out = []
k = len(poly)
for i in range(k):
cur, nxt = poly[i], poly[(i + 1) % k]
ca, cb = cross(a, b, cur), cross(a, b, nxt)
if ca >= 0: # đỉnh hiện tại nằm trong: giữ
out.append(cur)
if (ca > 0 and cb < 0) or (ca < 0 and cb > 0): # cạnh cắt ngang đường thẳng
t = ca / (ca - cb)
out.append((cur[0] + (nxt[0] - cur[0]) * t, cur[1] + (nxt[1] - cur[1]) * t))
return out
def clip_convex(subject, clip):
"""Giao của đa giác bất kỳ với đa giác LỒI, cả hai ngược chiều kim đồng hồ."""
m = len(clip)
for j in range(m):
if not subject:
break
subject = clip_half_plane(subject, clip[j], clip[(j + 1) % m])
return subject
def main():
data = sys.stdin.read().split()
pos = 0
n = int(data[pos])
pos += 1
P = [(float(data[pos + 2 * i]), float(data[pos + 2 * i + 1])) for i in range(n)]
pos += 2 * n
m = int(data[pos])
pos += 1
C = [(float(data[pos + 2 * i]), float(data[pos + 2 * i + 1])) for i in range(m)]
if signed_area(P) < 0: # chuẩn hóa ngược chiều kim đồng hồ
P.reverse()
if signed_area(C) < 0:
C.reverse()
print("%.6f" % signed_area(clip_convex(P, C)))
main()
Điều kiện giữ đỉnh là ca >= 0 (giữ cả đỉnh nằm đúng trên đường thẳng), còn điều kiện thêm giao điểm là hai dấu ngặt trái nhau. Nhờ vậy một đỉnh nằm trên đường thẳng không bị thêm hai lần, và không có phép chia cho .
Độ phức tạp
| Thao tác | Thời gian | Kết quả |
|---|---|---|
| Cắt đa giác đỉnh bởi một nửa mặt phẳng | không quá đỉnh ( nếu đa giác lồi) | |
| Giao đa giác lồi đỉnh với đa giác lồi đỉnh | đa giác lồi đỉnh | |
| Đa giác đỉnh bất kỳ cắt bởi đa giác lồi ít cạnh (ví dụ 4) |
Vì sao? Mỗi lần cắt duyệt mỗi cạnh của đa giác hiện tại một lần và thêm tối đa hai điểm cho mỗi cạnh. Nếu đa giác đang lồi, đường thẳng cắt biên của nó tại tối đa hai điểm, nên số đỉnh chỉ tăng tối đa mỗi lần và luôn . Với đa giác lõm, mỗi lần cắt có thể tăng số đỉnh nhiều hơn, nên kỹ thuật này hợp khi vùng cắt có ít cạnh.
⚠️ Lỗi thường gặp
- Sai chiều của đa giác cắt: nếu đi theo chiều kim đồng hồ thì "bên trái cạnh" là bên ngoài, kết quả rỗng hoặc sai. Luôn kiểm tra dấu diện tích và đảo ngược khi cần.
- Dùng vùng cắt không lồi: Sutherland-Hodgman chỉ đúng khi vùng cắt lồi. Giao hai đa giác lõm cần thuật toán khác (Weiler-Atherton, hoặc tách vùng cắt thành các tam giác lồi rồi cộng diện tích).
- Sinh điểm trùng tại đỉnh nằm trên đường thẳng: điều kiện
(ca >= 0) != (cb >= 0)thêm lại chính đỉnh cóca == 0như một "giao điểm" khicb < 0. Diện tích không đổi nhưng đa giác có cạnh độ dài , gây lỗi khi bước sau cần hướng của cạnh (ví dụ tính pháp tuyến, chia cạnh). Dùng điều kiện trái dấu ngặt như trong code. - Tách mảnh khi chỉ cần diện tích: đa giác kết quả có cầu độ dày là bình thường; đừng cố "sửa" nó hay lấy giá trị tuyệt đối của từng phần. Lấy diện tích có dấu của cả dãy đỉnh.
- Sai số tích lũy: mỗi lần cắt sinh giao điểm số thực, và các lần cắt sau lại dùng các điểm này. Dùng
long doubletrong C++ khi tọa độ lớn hoặc số lần cắt nhiều; so sánh dấucrossvới (không cần epsilon khi chỉ tính diện tích, vì sai dấu tại điểm sát đường thẳng chỉ làm lệch diện tích một lượng rất nhỏ). - Quên dừng khi rỗng: khi đa giác đã rỗng, các lần cắt sau vẫn trả rỗng; nhưng nếu code lấy
poly[0]hay chia chopoly.size()thì sẽ lỗi. Kiểm tra rỗng trước.
Biến thể / Mở rộng
- Giao nhiều nửa mặt phẳng: với nửa mặt phẳng lớn, cắt lần lượt tốn ; thuật toán giao nửa mặt phẳng sắp theo góc với deque chạy . Khi nhỏ (vài trăm), cắt một khung chữ nhật lớn bằng Sutherland-Hodgman là cách cài nhanh nhất.
- Giao đa giác với hình tròn: cộng có dấu, trên mỗi cạnh , diện tích giao giữa tam giác (tâm, , ) với hình tròn. Kết hợp với cắt nửa mặt phẳng để xử lý vùng ghép từ đa giác lồi và chỏm tròn.
- Kiểm tra điểm, bao lồi: các bước tiền xử lý thường gặp là dựng bao lồi để có vùng cắt lồi, và kiểm tra điểm trong đa giác. Xem thêm các kỹ thuật nền tảng ở Hình học.
Bài tập luyện
- Hình chữ nhật quay (rectpzl): (Very Hard) Diện tích giao của một hình chữ nhật và bản xoay của nó quanh tâm: cắt hình chữ nhật này bởi bốn cạnh của hình chữ nhật kia rồi tính shoelace (cẩn thận sai số khi kích thước tới ).
- Bão đang đến (icpc24rega): (Expert) Diện tích phần đa giác lõm nằm trong bao lồi của hai hình tròn: tách vùng thành một tứ giác lồi và hai chỏm tròn, cắt đa giác bằng Sutherland-Hodgman và dùng diện tích có dấu của kết quả suy biến.
Bình luận