Thi đấu

Tính Diện Tích Đa Giác: Công Thức Dây Giày (Shoelace) và Định Lý Pick

Tính diện tích đa giác bằng công thức dây giày Shoelace và đếm số điểm nguyên bằng định lý Pick là bộ đôi thuật toán kinh điển trong hình học rời rạc giúp giải quyết bài toán đa giác lưới trong thời gian tuyến tính O(N).

Tính Diện Tích Đa Giác: Công Thức Dây Giày (Shoelace) và Định Lý Pick

Trong các kỳ thi lập trình thi đấu như ICPC, HSG Quốc gia hay kỳ thi tuyển sinh Chuyên Tin, các bài toán xoay quanh đa giác trên mặt phẳng tọa độ thường đặt ra hai yêu cầu cốt lõi:

  1. Tính diện tích của một đa giác bất kỳ (có thể lồi hoặc lõm) khi biết tọa độ các đỉnh theo thứ tự.
  2. Đếm số điểm có tọa độ nguyên nằm nghiêm ngặt bên trong hoặc nằm trên cạnh của một đa giác lưới (Lattice Polygon).

Nếu tiếp cận theo lối chia nhỏ đa giác thành các tam giác rời rạc bằng cách dựng đường chéo (triangulation), thuật toán sẽ rất phức tạp và dễ gặp lỗi ở đa giác lõm hình ziczac hoặc ngôi sao. Thật may mắn, hai công cụ toán học tuyệt mỹ là Công thức dây giày Gauss (Shoelace Formula) và Định lý Pick (Pick's Theorem) cho phép giải quyết trọn vẹn cả hai vấn đề trên chỉ trong thời gian tuyến tính \(O(N)\) mà không hề sinh ra sai số số thực!

Shoelace và định lý Pick trên đa giác lưới A B C D E B = 14 điểm trên biên I = 2 điểm bên trong 1. Công thức dây giày 2S = |−4 + 15 − 2 + 10 − 3| = 16 2. Điểm nguyên trên biên B = Σ gcd(|Δx|, |Δy|) = 4 + 3 + 2 + 2 + 3 = 14 3. Định lý Pick: S = I + B/2 − 1 I = (2S − B + 2) / 2 = (16 − 14 + 2) / 2 = 2 Diện tích S = 8, chỉ dùng số nguyên
Shoelace và định lý Pick A B C D E B = 14 trên biên I = 2 bên trong 2S = |Σ (xᵢyᵢ₊₁ − xᵢ₊₁yᵢ)| = 16 B = Σ gcd(|Δx|, |Δy|) = 14 I = (2S − B + 2) / 2 = 2
Đa giác lưới của mục ví dụ chạy tay: 14 điểm nguyên trên biên (cam), 2 điểm bên trong (xanh lá), 2S = 16.

Công thức dây giày Shoelace tính diện tích đa giác

Công thức dây giày (còn gọi là công thức đo đạc viên Gauss - Surveyor's Formula) áp dụng cho bất kỳ đa giác đơn (simple polygon) nào, nghĩa là đa giác có các cạnh không tự cắt nhau.

1. Ý tưởng toán học dựa trên tích có hướng

Giả sử đa giác có \(N\) đỉnh được liệt kê theo thứ tự liên tiếp dọc theo chu vi: \(P_1(x_1, y_1), P_2(x_2, y_2), \dots, P_N(x_N, y_N)\). Quy ước \(P_{N+1} = P_1\) để khép kín chu trình.

Chọn gốc tọa độ \(O(0, 0)\). Diện tích có hướng của tam giác tạo bởi gốc tọa độ và cạnh \(P_i P_{i+1}\) chính là một nửa tích có hướng 2D:

\[S_{\triangle O P_i P_{i+1}} = \frac{1}{2} (\vec{OP_i} \times \vec{OP_{i+1}}) = \frac{1}{2} (x_i y_{i+1} - x_{i+1} y_i)\]

Khi ta cộng dồn diện tích có hướng của tất cả \(N\) tam giác này lại:

  • Các phần diện tích nằm bên ngoài đa giác sẽ tự động triệt tiêu lẫn nhau do mang dấu ngược nhau.
  • Phần diện tích thực tế bên trong đa giác sẽ được giữ lại nguyên vẹn!

2. Dạng phát biểu công thức dây giày

Tổng diện tích \(S\) của đa giác là:

\[S = \frac{1}{2} \left| \sum_{i=1}^N (x_i y_{i+1} - x_{i+1} y_i) \right|\]

Hoặc nhân đôi hai vế để làm việc hoàn toàn trên số nguyên:

\[2S = \left| \sum_{i=1}^N (x_i y_{i+1} - x_{i+1} y_i) \right|\]

Vì sao gọi là "công thức dây giày"? Nếu bạn viết hai cột tọa độ:

  x1       y1
     \   /
  x2       y2
     \   /
  x3       y3
     ...
  xN       yN
     \   /
  x1       y1

Đường chéo hướng xuống sang phải mang dấu cộng (\(+x_i y_{i+1}\)), đường chéo hướng lên sang phải mang dấu trừ (\(-x_{i+1} y_i\)). Hình ảnh các nét chéo đan vào nhau tựa như cách thắt dây giày thể thao.

Ưu điểm vượt trội: Nếu tất cả tọa độ đỉnh là số nguyên, thì \(2S\) luôn luôn là một số nguyên chính xác tuyệt đối. Bạn không cần dùng kiểu số thực double hay lo lắng về sai số làm tròn khi so sánh diện tích.

Đếm điểm nguyên trên cạnh đa giác bằng ước chung lớn nhất

Một bài toán con thường gặp: Trên đoạn thẳng nối hai điểm nguyên \(A(x_1, y_1)\) và \(B(x_2, y_2)\), có bao nhiêu điểm có tọa độ nguyên?

Đặt \(\Delta x = |x_2 - x_1|\) và \(\Delta y = |y_2 - y_1|\). Số đoạn thẳng nhỏ có độ dài bằng nhau mà đoạn \(AB\) bị chia ra bởi các điểm nguyên trên lưới chính là:

\[g = \gcd(\Delta x, \Delta y)\]

Do đó:

  • Số điểm nguyên trên đoạn thẳng \(AB\) (tính cả 2 mút \(A\) và \(B\)) là: \(g + 1\).
  • Nếu ta duyệt lần lượt qua mọi cạnh của đa giác theo chu trình khép kín, mỗi đỉnh sẽ là điểm cuối của cạnh trước và điểm đầu của cạnh sau. Để không bị đếm trùng, với mỗi cạnh \(i\) ta chỉ đếm số điểm nguyên không tính mút đầu:

\[B_i = \gcd(|x_{i+1} - x_i|, |y_{i+1} - y_i|)\]

Tổng số điểm nguyên nằm trên toàn bộ chu vi biên của đa giác \(B\) (Boundary points) là:

\[B = \sum_{i=1}^N \gcd(|x_{i+1} - x_i|, |y_{i+1} - y_i|)\]

Hàm std::gcd trong C++17 hoặc math.gcd trong Python tính toán giá trị này trong thời gian \(O(\log(\min(\Delta x, \Delta y)))\) theo thuật toán Euclid.

Định lý Pick cho đa giác lưới

Định lý Pick (được nhà toán học người Áo Georg Alexander Pick công bố năm 1899) là một định lý hình học rời rạc có vẻ đẹp đáng kinh ngạc. Nó thiết lập một mối quan hệ đại số hoàn hảo giữa diện tích hình học \(S\) của một đa giác lưới đơn với số điểm nguyên nằm trong và trên biên của nó:

\[S = I + \frac{B}{2} - 1\]

Trong đó:

  • \(S\): Diện tích của đa giác (tính theo đơn vị ô vuông lưới).
  • \(I\): Số điểm nguyên nằm nghiêm ngặt bên trong đa giác (Interior lattice points).
  • \(B\): Số điểm nguyên nằm trên đường biên của đa giác (Boundary lattice points).

Tính số điểm nguyên bên trong \(I\)

Từ định lý Pick, ta dễ dàng suy ra công thức tính số điểm nguyên nghiêm ngặt bên trong:

\[2S = 2I + B - 2 \iff 2I = 2S - B + 2 \iff I = \frac{2S - B + 2}{2}\]

Vì \(2S\) và \(B\) đều là các số nguyên và \((2S - B + 2)\) luôn chia hết cho 2, ta tính được \(I\) bằng phép chia nguyên đơn giản trong \(O(1)\) ngay sau khi có \(2S\) từ Shoelace và \(B\) từ các phép GCD!

Học cùng giảng viên

Chủ đề này nằm trong Buổi 14 - Geometry cơ bản + Convex Hull của Tài năng lập trình. Xem đề cương

Ví dụ chạy tay từng bước trên đa giác cụ thể

Xét đa giác lưới 5 đỉnh \(A(1, 1), B(5, 1), C(5, 4), D(3, 2), E(1, 4)\): Các đỉnh được liệt kê ngược chiều kim đồng hồ.

Cạnh Điểm đầu \((x_i, y_i)\) Điểm cuối \((x_{i+1}, y_{i+1})\) \(x_i y_{i+1} - x_{i+1} y_i\) \(\Delta x, \Delta y\) \(\gcd(\Delta x, \Delta y)\)
\(AB\) \((1, 1)\) \((5, 1)\) \(1 \times 1 - 5 \times 1 = -4\) \(4, 0\) \(4\)
\(BC\) \((5, 1)\) \((5, 4)\) \(5 \times 4 - 5 \times 1 = 15\) \(0, 3\) \(3\)
\(CD\) \((5, 4)\) \((3, 2)\) \(5 \times 2 - 3 \times 4 = -2\) \(2, 2\) \(2\)
\(DE\) \((3, 2)\) \((1, 4)\) \(3 \times 4 - 1 \times 2 = 10\) \(2, 2\) \(2\)
\(EA\) \((1, 4)\) \((1, 1)\) \(1 \times 1 - 1 \times 4 = -3\) \(0, 3\) \(3\)
Tổng Tổng đại số = 16 \(B = 14\)
  • Giá trị \(2S = |16| = 16 \implies S = 8.0\).
  • Số điểm nguyên trên biên \(B = 4 + 3 + 2 + 2 + 3 = 14\).
  • Áp dụng định lý Pick để tìm \(I\): \[I = \frac{2S - B + 2}{2} = \frac{16 - 14 + 2}{2} = \frac{4}{2} = 2\] Kết quả: Đa giác có diện tích là \(8\), có \(14\) điểm nguyên trên biên và chính xác \(2\) điểm nguyên nằm bên trong (đó là các điểm \((2, 2)\) và \((4, 2)\); hai điểm \((2, 3)\) và \((4, 3)\) nằm trên cạnh \(DE\) và \(CD\) nên thuộc biên).

Cài đặt chuẩn C++17 và Python 3

Thuật toán tính diện tích dây giày kết hợp định lý Pick và giải thuật Euclid tìm ước chung lớn nhất:

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>

using namespace std;

// Cấu trúc Điểm tọa độ nguyên 64-bit
struct Point {
    long long x, y;
};

// Tính ước chung lớn nhất Euclid
long long gcd_ll(long long a, long long b) {
    a = llabs(a);
    b = llabs(b);
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
    }

    long long double_area = 0;
    long long boundary = 0;

    for (int i = 0; i < n; i++) {
        int next_i = (i + 1) % n;
        // Công thức dây giày (Shoelace): x_i * y_{i+1} - x_{i+1} * y_i
        double_area += p[i].x * p[next_i].y - p[next_i].x * p[i].y;

        // Số điểm nguyên trên đoạn thẳng nối p[i] và p[next_i]
        long long dx = p[next_i].x - p[i].x;
        long long dy = p[next_i].y - p[i].y;
        boundary += gcd_ll(dx, dy);
    }

    double_area = llabs(double_area);

    // Định lý Pick: S = I + B/2 - 1 <=> 2S = 2I + B - 2 <=> I = (2S - B + 2) / 2
    long long interior = (double_area - boundary + 2) / 2;

    cout << double_area << " " << interior << " " << boundary << "\n";

    return 0;
}

Đánh giá độ phức tạp và ứng dụng thi đấu

  • Thời gian (Time Complexity): Thuật toán duyệt qua \(N\) cạnh của đa giác. Tại mỗi cạnh, phép nhân tọa độ tốn \(O(1)\), phép tính \(\gcd(\Delta x, \Delta y)\) tốn \(O(\log(\min(\Delta x, \Delta y)))\). Với tọa độ trong khoảng \([-10^9, 10^9]\), hiệu tọa độ lên tới \(2 \cdot 10^9\) và mỗi phép GCD tốn không quá 44 phép chia modulo (trường hợp xấu nhất là hai số Fibonacci liên tiếp \(1836311903\) và \(1134903170\)). Tổng thời gian là: \[O(N \log(\mathrm{coord\_max}))\] Với \(N = 10^5\), chương trình chỉ mất khoảng 0.04 giây, nhanh hơn hàng chục lần so với thuật toán tam giác hóa đa giác.
  • Không gian (Space Complexity): Chỉ cần lưu danh sách \(N\) đỉnh: \(O(N)\).
  • Ứng dụng:
    • Tính diện tích vùng phủ trong các bài toán quy hoạch bản đồ.
    • Đếm số cây trồng trong vườn hình đa giác lưới.
    • Kết hợp với thuật toán tìm bao lồi (Convex Hull) để giải bài toán diện tích bao lồi nhỏ nhất.

Luyện ngay trên Big-O Coding

Hãy bắt tay vào cài đặt và nộp thử lời giải của bạn trên hệ thống chấm tự động Big-O Coding để rèn luyện kỹ năng hình học tính toán:

Định lý Pick có áp dụng được cho đa giác có lỗ rỗng (hố) bên trong không?

Có, định lý Pick có phiên bản mở rộng cho đa giác có \(h\) lỗ rỗng: \[S = I + \frac{B}{2} + h - 1\] Trong đó \(B\) là tổng số điểm nguyên trên cả biên ngoài và biên của tất cả các lỗ rỗng bên trong. Với đa giác đơn thông thường không có lỗ rỗng, \(h = 0\), ta thu được công thức Pick quen thuộc.

Công thức dây giày có hoạt động đúng nếu các đỉnh được liệt kê cùng chiều kim đồng hồ không?

Hoàn toàn đúng! Khi các đỉnh được liệt kê cùng chiều kim đồng hồ (Clockwise), tổng đại số tích có hướng sẽ mang dấu âm: \(-2S\). Tuy nhiên, nhờ việc lấy giá trị tuyệt đối \(| \sum \dots |\) ở bước cuối cùng, diện tích thu được luôn là số dương chính xác.

Nếu đa giác tự cắt (self-intersecting) thì công thức Shoelace có đúng không?

Không. Nếu đa giác tự cắt, công thức Shoelace sẽ tính hiệu đại số giữa các vòng lặp định hướng ngược nhau, không phản ánh diện tích thực. Để giải đa giác tự cắt, bạn cần phân rã đa giác tại các giao điểm thành tập hợp các đa giác đơn độc lập.

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483