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ố

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