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ố

Tham số | Mặc định | Mô tả
--- | --- | ---
gap_tolerance | 0.001 ha | Diện tích tối thiểu để xem là gap

## 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ố

Tham số | Mặc định | Mô tả
--- | --- | ---
mno_min_area | 0.001 m² | Ngưỡng diện tích giao

## 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ố

Tham số | Mặc định | Mô tả
--- | --- | ---
sliver_max_area | 1.0 ha | Vùng lớn hơn không thể là sliver
sliver_ratio | 20.0 | Ngưỡng P/√A

## 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ố

Tham số | Mặc định | Mô tả
--- | --- | ---
redundant_max_verts | 500 | Số đỉnh tối đa
simplify_tol | (tùy chọn) | Dung sai simplify

## 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

Tham số | Mặc định | Mô tả
--- | --- | ---
missing_node_tol | 0.001 | Snap tolerance (đơn vị bản đồ). VN-2000: 0.001m
Dữ liệu độ (WGS84) | 1e-8 → 1e-6 | EPSG:4326
Dữ liệu mét (VN-2000) | 0.001 → 0.01 | Hệ tọa độ VN-2000

## 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ố

Tham số | Mặc định | Mô tả
--- | --- | ---
tiny_min_area | (user input) | Ngưỡng diện tích (ha)

# Tổng hợp Tham số

Tham số | Key | Mặc định | Đơn vị | UI Widget
--- | --- | --- | --- | ---
Ngưỡng Gap | gap_tolerance | 0.001 | ha | QDoubleSpinBox
Sliver max area | sliver_max_area | 1.0 | ha | QDoubleSpinBox
Sliver ratio | sliver_ratio | 20.0 | — | QDoubleSpinBox
Max vertices | redundant_max_verts | 500 | count | QSpinBox
Simplify tol | simplify_tol | (var) | map units | QDoubleSpinBox
MNO min area | mno_min_area | 0.001 | m² | QDoubleSpinBox
Missing node tol | missing_node_tol | 0.001 | map units | QDoubleSpinBox
Tiny min area | tiny_min_area | (var) | ha | QDoubleSpinBox

⚠ 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)

Cơ sở lý thuyết: Lý thuyết đồ thị (Graph Theory) — mạng lưới đường được mô hình hóa dưới dạng đồ thị G = (V, E) với V là các nút giao và E là các đoạn đường. Tiêu chuẩn OGC Simple Feature Access (ISO 19125-1) định nghĩa các quan hệ không gian cho geometry dạng đường.

## 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)

Cơ sở lý thuyết: Spatial Statistics và Nearest Neighbor Analysis. Phân tích mẫu điểm (Point Pattern Analysis) dựa trên khoảng cách Euclidean và các chỉ số thống kê không gian.

## 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.

Tham số | Mặc định | Mô tả
--- | --- | ---
dup_point_tol | 0.001 | Khoảng cách trùng (đơn vị bản đồ)

## 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ệ.

Tham số | Mặc định | Mô tả
--- | --- | ---
isolated_dist | 1000.0 | Khoảng cách tối đa (đơn vị bản đồ)

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

Loại | Số lượng | Thuật toán
--- | --- | ---
🔷 Polygon | 11 | Multipart, Invalid, Unclosed, Duplicates, Overlaps, Must Not Overlap, Gaps, Redundant, Slivers, Missing Nodes, Tiny Polygon
📏 Line | 4 | Dangles, Self-Intersection, Duplicate Lines, Overlapping Lines
📍 Point | 3 | Duplicate Points, Invalid Coordinates, Isolated Points