Wiki › Thuật toán › Hình học tính toán › Cắt đa giác (Sutherland-Hodgman) và giao đa giác lồi

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.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 12 phút 3 lượt xem

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 O(k) qua k đỉ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 106 đến 107.

Ý tưởng / Trực giác

Cắt bởi một nửa mặt phẳng. Gọi H là nửa mặt phẳng bên trái đường thẳng có hướng a→b, tức các điểm p có cross(b−a,p−a)≥0. Duyệt các cạnh (cur,nxt) của đa giác theo thứ tự:

  • nếu cur∈H thì giữ cur;
  • nếu cur và nxt 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 H, 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 ca=cross(b−a,cur−a) và cb=cross(b−a,nxt−a) trái dấu, giao điểm là cur+(nxt−cur)·caca−cb.

Cắt bởi đa giác lồi. Một đa giác lồi C (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ì P∩(H1∩H2)=(P∩H1)∩H2, 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 P lõm, P∩H 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 0 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 p0,…,pk−1:

S=12∑i=0k−1cross(pi,pi+1),

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 P=(0,0),(4,0),(4,4),(0,4) bởi tam giác C=(1,1),(5,1),(3,5) (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 C Giá trị cross tại các đỉnh hiện tại Đa giác sau khi cắt Diện tích
(1,1)→(5,1) (0,0):−4, (4,0):−4, (4,4):12, (0,4):12 (4,1),(4,4),(0,4),(0,1) 12
(5,1)→(3,5) (4,1):4, (4,4):−2, (0,4):14, (0,1):20 (4,1),(4,3),(3.5,4),(0,4),(0,1) 11.75
(3,5)→(1,1) (4,1):12, (4,3):8, (3.5,4):4, (0,4):−10, (0,1):−4 (4,1),(4,3),(3.5,4),(2.5,4),(1,1) 6.5

Ở bước 2, cạnh (4,1)→(4,4) đi từ trong (4>0) ra ngoài (−2<0), giao điểm ở tỉ lệ 44−(−2)=23, tức (4,3); cạnh (4,4)→(0,4) đi từ ngoài vào trong, giao điểm (3.5,4). Kiểm chứng: tam giác C có diện tích 8; phần nằm trên y=4 là tam giác nhỏ diện tích 0.5, phần nằm bên phải x=4 là tam giác diện tích 1; còn lại 8−0.5−1=6.5.

Đa giác lõm. Cắt chữ U (0,0),(3,0),(3,3),(2,3),(2,1),(1,1),(1,3),(0,3) (diện tích 7), chỉ giữ phần y≥2. Kết quả là một dãy đỉnh duy nhất (3,2),(3,3),(2,3),(2,2),(1,2),(1,3),(0,3),(0,2): hai "cánh" của chữ U nối với nhau bằng đoạn (2,2)→(1,2) và đoạn quay về (0,2)→(3,2) nằm trên đường thẳng y=2. Diện tích có dấu bằng 2, đúng bằng hai hình vuông đơn vị.

Cài đặt

Dữ liệu: đa giác P (n đỉnh nguyên, có thể lõm, theo chiều bất kỳ) và đa giác lồi C (m đỉnh). In diện tích P∩C.

C++
#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';
}
Python
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 ca−cb=0.

Độ phức tạp

Thao tác Thời gian Kết quả
Cắt đa giác k đỉnh bởi một nửa mặt phẳng O(k) không quá 2k đỉnh (≤k+1 nếu đa giác lồi)
Giao đa giác lồi n đỉnh với đa giác lồi m đỉnh O(n·m) đa giác lồi ≤n+m đỉnh
Đa giác n đỉnh bất kỳ cắt bởi đa giác lồi ít cạnh (ví dụ 4) O(n)

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 1 mỗi lần và luôn ≤n+m. 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 C đ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 == 0 như một "giao điểm" khi cb < 0. Diện tích không đổi nhưng đa giác có cạnh độ dài 0, 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 0 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 double trong C++ khi tọa độ lớn hoặc số lần cắt nhiều; so sánh dấu cross với 0 (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 cho poly.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 nửa mặt phẳng lớn, cắt lần lượt tốn O(N2); thuật toán giao nửa mặt phẳng sắp theo góc với deque chạy O(NlogN). Khi N 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 AB, diện tích giao giữa tam giác (tâm, A, B) 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 106).
  • 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.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0