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

TopoFix

18 thuật toán kiểm tra & sửa lỗi topology cho dữ liệu GIS
🔷 Polygon (11)  |  📏 Line (4)  |  📍 Point (3)

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²).

📏 Thuật toán kiểm tra ĐƯỜNG (Line Topology)

L1. Dangles — Đầu mút treo

Endpoint của đường KHÔNG kết nối với bất kỳ đường nào khác → đầu mút treo (dangle).

Nguyên lý khoa học

Trong lý thuyết đồ thị, dangle = node có bậc 1 (degree=1). Với mạng lưới giao thông hoặc thủy văn, dangle thường là lỗi số hóa.

Phát hiện

1. Thu thập tất cả endpoints (đầu + cuối) mỗi đường

2. Endpoint không trùng với endpoint nào khác trong tolerance → dangle

Sửa lỗi

Cần xem xét thủ công — dangle có thể là lỗi hoặc điểm cuối hợp lệ (ngõ cụt).

L2. Self-Intersection — Tự cắt chính nó

Đường giao cắt chính nó tại 1+ điểm → vi phạm OGC Simple Feature.

Nguyên lý khoa học

OGC Simple Feature yêu cầu mỗi LineString là "simple" — không tự giao cắt (ngoại trừ tại endpoints cho ring). GEOS library thực hiện kiểm tra qua isValid().

Phát hiện

if not geometry.isGeosValid(): → validateGeometry() trả về vị trí lỗi

Sửa lỗi

native:fixgeometries — tách đường tại điểm giao cắt.

L3. Duplicate Lines — Đường trùng nhau

Hai features có geometry hoàn toàn giống nhau → trùng lặp.

Nguyên lý khoa học

So sánh WKT (Well-Known Text) với precision 6 chữ số thập phân. Đây là phương pháp tương tự thuật toán Duplicates cho Polygon.

Phát hiện

Hash WKT mỗi geometry → phát hiện trùng

Sửa lỗi

Xóa features trùng, giữ bản gốc (first occurrence).

L4. Overlapping Lines — Đường chồng nhau

Hai đường có đoạn trùng (LineString intersection) → lỗi topology.

Nguyên lý khoa học

Sử dụng DE-9IM (Dimensionally Extended 9-Intersection Model): hai đường overlap khi intersection có dimension = 1 (line), không phải dimension = 0 (point — giao nhau bình thường).

Phát hiện

1. QgsSpatialIndex tìm cặp candidates

2. intersection(g_a, g_b) → kiểm tra type = LineGeometry

Sửa lỗi

Cần xem xét thủ công — xóa hoặc tách đoạn trùng.

📍 Thuật toán kiểm tra ĐIỂM (Point Topology)

P1. Duplicate Points — Điểm trùng nhau

Hai+ features điểm có tọa độ trùng nhau (trong tolerance) → trùng lặp.

Nguyên lý khoa học

So sánh khoảng cách Euclidean: d = √((x₁-x₂)² + (y₁-y₂)²)
Nếu d < tolerance → trùng lặp. Complexity: O(n²) nhưng với QgsSpatialIndex giảm xuống O(n·log n).

Phát hiện

if |x_a - x_b| < tol AND |y_a - y_b| < tol: duplicate

Sửa lỗi

Xóa features trùng, giữ bản gốc.

P2. Invalid Coordinates — Tọa độ không hợp lệ

Điểm có tọa độ NaN, Infinity, hoặc ngoài phạm vi hợp lý.

Nguyên lý khoa học

IEEE 754 floating-point: NaN (Not a Number) xuất hiện khi phép tính không xác định.
Kiểm tra: x ≠ x (NaN test) hoặc |x| > 10¹⁰ (outlier test).

Phát hiện

if pt.x() != pt.x() (NaN) OR |pt.x()| > 1e10 (outlier): invalid

Sửa lỗi

Xóa features có tọa độ không hợp lệ.

P3. Isolated Points — Điểm cô lập

Điểm nằm quá xa mọi điểm khác → có thể là lỗi nhập liệu.

Nguyên lý khoa học

Nearest Neighbor Analysis: Tìm k=1 nearest neighbor bằng QgsSpatialIndex (R-tree).
Nếu khoảng cách > ngưỡng → điểm cô lập.
Liên quan: Clark-Evans Index R = d̄_obs / d̄_exp đánh giá phân bố ngẫu nhiên.

Phát hiện

1. SpatialIndex.nearestNeighbor(point, k=2) → lấy neighbor gần nhất (trừ chính nó)

2. if distance > isolated_dist: mark isolated

Sửa lỗi

Cần xem xét thủ công — điểm cô lập có thể hợp lệ.

Tổng hợp: 18 Thuật toán