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:
- 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ự.
- Đế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!
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
doublehay 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!
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;
}
import sys
import math
def main():
input_data = sys.stdin.read().split()
if not input_data:
return
n = int(input_data[0])
points = []
idx = 1
for _ in range(n):
x = int(input_data[idx])
y = int(input_data[idx + 1])
idx += 2
points.append((x, y))
double_area = 0
boundary = 0
for i in range(n):
x1, y1 = points[i]
x2, y2 = points[(i + 1) % n]
# Công thức Shoelace
double_area += x1 * y2 - x2 * y1
# Số điểm nguyên trên cạnh
boundary += math.gcd(abs(x2 - x1), abs(y2 - y1))
double_area = abs(double_area)
# Định lý Pick
interior = (double_area - boundary + 2) // 2
sys.stdout.write(f"{double_area} {interior} {boundary}\n")
if __name__ == '__main__':
main()
Đá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
- CP-Algorithms - Finding area of simple polygon in O(N) - Diện tích có dấu của đa giác đơn tính bằng tổng các hình thang dưới từng cạnh, tương đương công thức dây giày.
- CP-Algorithms - Pick's Theorem - Liên hệ diện tích đa giác lưới với số điểm nguyên trên biên và bên trong.
- VNOI Wiki - Hình học tính toán phần 3: Đa giác - Công thức Shoelace, đếm điểm nguyên trên cạnh bằng gcd và định lý Pick, viết bằng tiếng Việt.
- USACO Guide - Geometry Primitives - Các phép toán hình học cơ bản, có công thức Shoelace và định lý Pick, cho phân hạng Platinum.
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.


