NGUYÊN LÝ & THUẬT TOÁN

TopoFix

11 thuật toán kiểm tra & sửa lỗi topology cho dữ liệu GIS

Lộc Vũ Trung tổng hợp từ đam mê

Kiến trúc tổng quan

Hệ thống sử dụng kiến trúc đa luồng với 2 worker chạy trên QThread riêng biệt:

CheckWorker: Duyệt features, phát hiện lỗi, emit progress(int, str) và finished(dict)

FixWorker: Nhận layer + danh sách fix, xử lý tuần tự, emit finished(path)

Layer gốc → [CheckWorker - QThread] → results{key: [geometries]}

↓

[FixWorker - QThread] → Output file

11 Thuật toán Chi tiết

1. Duplicates — Trùng lặp hình học

So sánh WKT của mỗi geometry. Hai features có cùng WKT = trùng lặp.

Phát hiện

seen_wkt = {}

for feature in layer:

wkt = feature.geometry().asWkt()

if wkt in seen_wkt: mark_duplicate(feature)

Sửa lỗi

Sử dụng native:deleteduplicategeometries — tự động xóa feature trùng.

2. Gaps — Khoảng hở giữa polygon

Dissolve toàn bộ → 1 polygon gộp. Mỗi interior ring = 1 gap tiềm năng.

Phát hiện

1. Dissolve toàn bộ layer → 1 polygon gộp

2. Duyệt interior rings (holes)

3. Chuyển ring → polygon, kiểm tra area > gap_tolerance

Sửa lỗi

1. Dissolve → tìm gaps

2. SpatialIndex tìm polygon lân cận

3. Merge gap vào polygon có chung cạnh dài nhất

Tham số

3. Overlaps — Chồng đè

SpatialIndex tìm nhanh cặp giao nhau → GEOS kiểm tra chính xác.

Phát hiện

1. Tạo QgsSpatialIndex

2. Mỗi cặp: idx.intersects(bbox)

3. g1.overlaps(g2) → tính intersection

Sửa lỗi

1. Tính intersection mỗi cặp

2. g1.difference(intersection) — cắt phần giao

3. Ghi output → deleteduplicategeometries

3b. Must Not Overlap — Cắt thông minh

Khác Overlaps: cắt khỏi feature có diện tích NHỎ HƠN.

Phát hiện

Giống Overlaps, chỉ xử lý khi intersection.area() > mno_min_area

Sửa lỗi

So sánh area1 vs area2 → difference() trên polygon nhỏ hơn

Tham số

4. Invalid Geometries — Hình học không hợp lệ

GEOS validation: self-intersection, ring ngoài, duplicate nodes...

Phát hiện

if not g.isGeosValid(): mark_invalid(feature)

Sửa lỗi

native:fixgeometries chạy 2 LẦN:

1. Structure method — sửa cấu trúc

2. Linework method — sửa theo đường nối node

5. Multipart — Đối tượng đa phần

Phát hiện geometry có nhiều hơn 1 part.

Phát hiện

if g.isMultipart() and numGeometries() > 1: mark

Sửa lỗi

native:multiparttosingleparts — tách mỗi part thành feature riêng.

⚠ Bước ĐẦU TIÊN trong pipeline vì thay đổi số features.

6. Sliver Polygons — Vùng hình kim

Compactness Ratio P/√A — polygon dài hẹp có ratio cao bất thường.

Phát hiện

Ratio = P / √A

Hình tròn: 3.54 | Hình vuông: 4.0 | Sliver 1×100m: 20.2

if ratio > sliver_ratio AND area < sliver_max_area: mark

Sửa lỗi

Lọc bỏ — chỉ giữ features KHÔNG phải sliver.

Tham số

7. Redundant Vertices — Điểm nút dư thừa

Đếm vertex, vượt ngưỡng → simplify.

Phát hiện

if count_vertices(geometry) > redundant_max_verts: mark

Sửa lỗi

native:simplifygeometries (Douglas-Peucker)

Tham số

8. Unclosed Rings — Vòng không khép kín

Kiểm tra mỗi ring có điểm đầu = điểm cuối.

Phát hiện

for ring in all_rings(geometry):

if first_vertex != last_vertex: mark

Sửa lỗi

Xử lý cùng native:fixgeometries trong bước Invalid fix.

9. Missing Nodes — Thiếu nút trên cạnh chung

Thuật toán PHỨC TẠP NHẤT — hoàn toàn custom.

Polygon A có node P trên cạnh B, nhưng B KHÔNG có node tại P → lỗi topology.

_point_on_segment()

t = ((px-ax)*(bx-ax) + (py-ay)*(by-ay)) / ((bx-ax)² + (by-ay)²)

F = A + t × AB | P ∈ AB ⟺ 0 < t < 1 AND |PF| < tolerance

_find_missing_nodes() + _rebuild_geometry()

Duyệt mọi cặp → point_on_segment trên mọi cạnh → chèn node → rebuild polygon

10. Tiny Polygons — Gộp vùng nhỏ

Diện tích < ngưỡng → iterative merge vào polygon lân cận.

Phát hiện

if geometry.area() < tiny_min_area: mark

Sửa lỗi

Iterative merge (max 20 vòng):

Chọn polygon chung cạnh dài nhất → combine()

Bằng nhau → chọn diện tích lớn hơn

Tham số

Tổng hợp Tham số

⚠ Lưu ý: Tham số diện tích nhập bằng ha, nhân 10000 khi so sánh với geometry.area() (m²).