dazzlingvit đã viết:...
Vậy có cách cải tiến nào để vừa tăng tốc, vừa tính chính xác không?
...
Tích phân là phương pháp tính diện tích tổng quát nhất, áp dụng được cho mọi đa giác và mọi miền có giới hạn nói chung.
Tuy nhiên, nếu chỉ giới hạn trong các đa giác lồi và lõm (không tính đa giác phức hay đa giác tự cắt) thì có thể dùng "mẹo fill" thế này:
- Vẽ đa giác lên mặt phẳng toạ độ (có quy ước kích thước điểm ảnh tương ứng với độ dài d nào đó);
- Giả sử Xmin, Xmax là cực tiểu và cực đại trong tập các toạ độ X (i) các đỉnh. Xác định (bằng tính toán chứ không vẽ) các giao điểm của đường thẳng đứng x = (Xmin + Xmax)/2 với các cạnh của đa giác và sắp xếp các giao điểm theo chiều tăng hoặc giảm dần. Khi đó một điểm bất kỳ nằm giữa 2 giao điểm đầu tiên (nếu trùng nhau thì giữa 2 giao điểm tiếp theo,...) sẽ chắc chắn nằm bên trong đa giác;
- Fill đa giác từ điểm đó với màu khác màu cạnh đa giác;
- Lưu hình ảnh thành file *.BMP;
- Đọc file ảnh để tính tổng số điểm ảnh có màu fill (N1) và số điểm ảnh có màu cạnh (N2);
- Diện tích đa giác xấp xỉ d*d*(N1 + N2/2).
Nếu dùng "mẹo" này thì độ chính xác phụ thuộc vào quy ước kích thước 1 pixel, càng nhỏ thì độ chính xác càng tăng, nhưng file BMP sẽ rất lớn, lơi hại gần giống như khi lấy tích phân - dx càng nhỏ thì làm càng lâu.
