BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC MỎ-ĐỊA CHẤT
________________________________
PHẠM THẾ HUYNH
NGHIÊN CỨU CÔNG NGHỆ THÀNH LẬP
VÀ ỨNG DỤNG BẢN ĐỒ SỐ ĐỊA CHÍNH
TRONG ĐIỀU KIỆN VIỆT NAM

Ngành : Kỹ thuật Trắc địa - Bản đồ
Mã số : 62.52.05.03
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT


Luận án sẽ được bảo vệ trước Hội đồng đánh giá luận án cấp Trường, họp
tại trường Đại học Mỏ - Địa chất vào hồi giờ, ngày tháng năm
2015.

Có thể tìm hiểu luận án tại:
- Thư viện Quốc gia - Hà Nội
- Thư viện trường Đại học Mỏ - Địa chất

1
MỞ ĐẦU
1. Tính cấp thiết của đề tài
Hiện nay, việc thành lập bản đồ số nói chung và bản đồ số địa chính nói riêng đang
được triển khai rộng rãi trên cả nước. Tuy nhiên, do chưa có hệ thống phần mềm xử lý,
biên tập một cách hoàn chỉnh, thống nhất; hệ thống văn bản kỹ thuật cho công tác thành
lập bản đồ địa chính thay đổi thường xuyên nên việc thành lập bản đồ số địa chính còn
gặp nhiều khó khăn. Để thành lập được một bản đồ địa chính số phải thực hiện qua
nhiều công đoạn bằng nhiều phần mềm khác nhau, mỗi đơn vị sản xuất thực hiện theo
một quy trình riêng. Các sản phẩm bản đồ chủ yếu sử dụng phần mềm đồ họa nước
ngoài và các mô đun phần mềm Việt Nam chạy trên các nền đồ họa đó. Trong giai đoạn
hiện nay, khi luật bản quyền được thắt chặt thì việc sử dụng các phần mềm nước ngoài
sẽ đẩy giá thành sản phẩm cao làm cho không phải đơn vị sản xuất nào cũng có thể thực
hiện được. Bên cạnh đó, với dữ liệu không được chuẩn hóa đồng đều thì khai thác ứng
dụng bản đồ số địa chính còn hạn chế. Chính vì vậy, việc nghiên cứu hoàn thiện công
nghệ thành lập và ứng dụng bản đồ số địa chính trong điều kiện Việt Nam là một yêu
cầu cấp thiết, có ý nghĩa lý luận và thực tiễn cao.
2. Mục đích nghiên cứu của luận án

7. Ý nghĩa khoa học và thực tiễn của luận án
- Ý nghĩa khoa học: Xây dựng cơ sở lý thuyết sử dụng mô hình dữ liệu phù hợp vừa
linh hoạt trong việc thành lập và khai thác dữ liệu bản đồ số địa chính vừa dễ dàng trong
việc cập nhật biến động đất đai.
- Ý nghĩa thực tiễn: Giải pháp hoàn thiện quy trình thành lập bản đồ địa chính đề
xuất trong luận án nhằm tăng năng suất lao động, chuyên môn hóa công tác nội - ngoại
nghiệp, có thể áp dụng ở tất cả các đơn vị thành lập bản đồ số địa chính.
8. Các luận điểm bảo vệ
- Giải pháp hoàn thiện quy trình công nghệ thành lập bản đồ địa chính đề xuất trong
luận án phù hợp với sự tiến bộ khoa học kỹ thuật ở Việt Nam hiện nay;
- Sử dụng cấu trúc dữ liệu DCEL là cơ sở để quản lý và khai thác dữ liệu bản đồ số
địa chính.
9. Các điểm mới của luận án
(1) Cách tiếp cận mới trong việc sử dụng thông tin trực quan khi đo đạc thành lập
bản đồ địa chính nhằm chuyên môn hóa công tác nội ngoại nghiệp.
(2) Đề xuất sử dụng cấu trúc dữ liệu DCEL và xây dựng thuật toán sử dụng trong
biên tập cũng như tạo ứng dụng bản đồ số địa chính trong điều kiện Việt Nam;
(3) Xác định giải pháp tối ưu hóa tốc độ tính toán cho các thuật toán trong xây dựng
chương trình.
10. Kết cấu của luận án
Luận án được chia thành các phần:
(1). Mở đầu: Giới thiệu tính cấp thiết, mục đích, ý nghĩa, đối tượng, phạm vi nghiên
cứu của luận án;
(2). Chương 1. Tổng quan: Giới thiệu tình hình nghiên cứu trong và ngoài nước về
những vấn đề liên quan đến nội dung luận án, các vấn đề còn tồn tại, cần nghiên cứu;
(3). Nội dung nghiên cứu được trình bày trong 3 chương 2, 3, 4:
Chương 2. Giải pháp hoàn thiện công nghệ thành lập và ứng dụng bản đồ số địa
chính trong điều kiện Việt Nam.
Chương 3. Sử dụng cấu trúc dữ liệu Dcel trong thành lập và ứng dụng bản đồ số địa
chính

nhân công kỹ thuật, ảnh hưởng lớn của điều kiện thời tiết, độ chính xác thấp, sản phẩm
bản đồ trên giấy khó lưu trữ, nhân bản Ưu điểm của công nghệ này là các thông tin tức
thời tại thực địa được chuyển vẽ và ghi chú ngay lên bản vẽ đồng thời kiểm chứng ngay
được sự chính xác về hình thửa, các mối quan hệ hình học của các đối tượng như thẳng
hàng, vuông góc Các thông tin này được gọi là thông tin trực quan.
Năm 1992, theo yêu cầu của TP Hà Nội về công tác quản lý đất đai cần có bản đồ địa
chính tỷ lệ 1/200 khu vực nội thành. Việc sử dụng phương pháp triển điểm truyền thống
không đảm bảo được độ chính xác thể hiện các đối tượng trên bản đồ. Khi đó, Sở Nhà
đất Hà Nội yêu cầu phải tính tọa độ chính xác từng điểm chi tiết rồi dùng hệ thống mắt
lưới chữ thập triển các điểm theo tọa độ lên bản đồ. Tuy nhiên, hiệu quả của phương
pháp này thấp do việc tính toán tọa độ và triển điểm mất nhiều thời gian (công nghệ
thông tin lúc đó chưa phát triển, các phần mềm đồ họa còn hạn chế, máy vi tính còn quá
xa xỉ đối với các đơn vị thành lập bản đồ). Lúc này, một số nhà khoa học đã nghiên cứu
xây dựng các chương trình tính tọa độ điểm chi tiết và triển điểm lên bản vẽ. Việc tính
toán và triển điểm khi đó đã trở nên dễ dàng hơn. Mặc dầu vậy, với đội ngũ các nhà
khoa học trong đó có các giảng viên khoa Trắc địa của trường Đại học Mỏ - Địa chất và
cán bộ đo vẽ chuyên nghiệp nhưng tốc độ thành lập bản đồ chậm và nhiều khu vực
không thể vẽ đúng được theo thực địa.
Nguyên nhân sau này được phát hiện ra là công nghệ đo vẽ bản đồ số khi đó vô tình vi
phạm một số nguyên tắc đo vẽ truyền thống đó là một số nguyên tắc theo phương pháp
truyền thống bị phá vỡ khi đo vẽ bản đồ số:
- Người vẽ phải tham gia trong tổ đo: do lúc này máy vi tình giá thành cao, người có
trình độ vẽ bản đồ số hiếm nên phải vẽ cho nhiều tổ đo;
- Quá trình vẽ phải được thực hiện ngay sau khi đo: bản vẽ bị tồn đọng nhiều ngày do
việc đo nhanh hơn việc vẽ;
- Điểm mia triển tuần tự từ trạm này sang trạm khác theo trình tự đo: các điểm mia
chuyển vẽ toàn bộ lên bản vẽ làm cho việc xác định các sai lệch không xác định được
khi có một trạm sai.
Đúc kết lại, đó chính là thông tin trực quan không được lưu trữ trong sổ đo dẫn đến
người vẽ bị mù thông tin. Đặc điểm của thông tin này là chỉ lưu trữ trong thời gian ngắn

được chuyển vẽ trên máy vi tính bằng các phần mềm chuyên dụng rồi sử dụng các bản
vẽ sơ họa hoặc ghi chú để thành lập bản đồ tổng thể. Quy trình đo vẽ như vậy không
chuyên môn hóa công việc nội nghiệp và ngoại nghiệp.
1.2.3.2. Biên tập bản đồ
Quá trình biên tập bản đồ địa chính gồm các bước:
- Tạo bản đồ tổng thể khu đo
- Tạo sơ đồ phân mảnh và tạo tờ bản đồ địa chính
- Biên tập tờ bản đồ địa chính
Với cách chia mảnh như hiện nay, nhiều yêu cầu của hệ thống tham chiếu thửa đất
khác không thỏa mãn và mối quan hệ liền kề giữa các thửa đất bị phá vỡ.
Bên cạnh đó, việc quản lý thửa đất theo các tờ bản đồ đòi hỏi quá trình đo đạc phải
hoàn thiện mới tiến hành phân chia được các mảnh bản đồ để biên tập riêng sau đó mới
xác định được số hiệu thửa đất để lập hồ sơ thửa đất. Đây là một bất cập lớn trong quá
trình thành lập hồ sơ và làm giảm hiệu quả công việc một cách rõ rệt, không tận dụng
được khả năng làm việc song song giữa xây dựng bản đồ và hồ sơ địa chính.
1.2.3.3. Quản lý dữ liệu phục vụ ứng dụng bản đồ số địa chính
Việc xây dựng cơ sở dữ liệu địa chính và đo đạc thành lập bản đồ địa chính hiện nay
đang sử dụng hai hệ thống riêng biệt nên khó quản lý và cập nhật. Mỗi hệ thống có
khuôn dạng dữ liệu khác nhau, chính vì vậy, phải chuyển đổi dữ liệu bản đồ từ khuôn
dạng này sang khuôn dạng khác. Việc chuyển đổi dữ liệu dẫn đến dữ liệu có thể không
5
được đầy đủ. Khi có một thay đổi nhỏ về thông tin một thửa đất sẽ phải tốn nhiều thời
gian để cập nhật dữ liệu đồng thời trên cả hai hệ thống và đòi hỏi những người có kỹ
thuật cao mới làm được điều này, trong khi đó việc biến động đất đai và cập nhật thông
tin đất đai là một việc diễn ra thường xuyên.
a. Quản lý dữ liệu
Cơ sở dữ liệu bản đồ địa chính lưu trong 2 dạng file:
- File đồ hoạ *.DGN của Microstation;
- File *.POL lưu trữ mối quan hệ Topo của các đối tượng vùng đồng thời lưu trữ cả
dữ liệu thuộc tính của chúng.

CHƯƠNG 2. GIẢI PHÁP HOÀN THIỆN CÔNG NGHỆ THÀNH LẬP VÀ ỨNG
DỤNG BẢN ĐỒ SỐ ĐỊA CHÍNH TRONG ĐIỀU KIỆN VIỆT NAM
2.1. Xác định giải pháp
Qua các đánh giá quy trình công nghệ thành lập và ứng dụng bản đồ số địa chính
trong phần tổng quan cho thấy ba vấn đề chính cần được quan tâm giải quyết đó là:
chuyển đổi hệ thống bản đồ địa chính số đã có theo hệ thống tọa độ mới mà vẫn lưu trữ
6
được thông tin thuộc tính thửa đất; chuyên môn hóa công tác nội - ngoại nghiệp; quản lý
cơ sở dữ liệu bản đồ địa chính sao cho vừa thuận lợi trong việc thành lập vừa dễ dàng
trong công tác cập nhật biến động đất đai cũng như ứng dụng bản đồ số địa chính.
2.2. Chuyển đổi bản đồ địa chính khi thay đổi hệ thống tọa độ
Hiện nay, hệ thống bản đồ số tỷ lệ trung bình và lớn đã và đang thành lập trong hệ tọa
độ VN2000, múi chiếu 3 độ và kinh tuyến trục địa phương. Tuy nhiên, nhiều địa phương
do chưa có kinh phí nên vẫn còn sử dụng hệ thống bản đồ số ở hệ tọa độ HN72, thậm chí
có địa phương vẫn còn sử dụng bản đồ giải thửa giấy 299 (bản đồ được đo vẽ theo chỉ
thị 299/TTg năm 1980 của Phủ Thủ tướng). Đến nay, theo thông tư 25/2014/TT-
BTNMT của Bộ tài nguyên và Môi trường đã thay đổi thông số đơn vị đo, tọa độ điểm
trung tâm làm việc.
Như vậy, có thể thấy rằng bản đồ địa chính đã được thành lập qua nhiều giai đoạn
khác nhau, với các hệ tọa độ khác nhau và được sử dụng để quản lý ở nhiều cấp đến
từng thửa đất.
Với sự phát triển của khoa học công nghệ, hội nhập quốc tế thì việc thay đổi hệ tọa độ
và quy định kỹ thuật là điều không thể tránh khỏi, trong khi đó, đối với người sử dụng
đất, những vấn đề về thay đổi hệ tọa độ hay quy định kỹ thuật thành lập không làm thay
đổi phần lớn những thông tin thuộc tính riêng của họ.
Vấn đề đặt ra là làm thế nào chuyển đổi hệ thống bản đồ cũ sang hệ thống tọa độ mới
mà thông tin thuộc tính các thửa đất phải cập nhật là ít nhất.
2.2.1. Giải pháp chuyển đổi từ bản đồ giấy sang bản đồ số
Để chuyển đổi từ bản đồ giấy sang bản đồ số dạng Vector trước hết chuyển bản đồ
giấy sang dạng Raster bằng thiết bị quét với độ phân giải cao, sử dụng các điểm khống

sang tọa độ khác cần được thực hiện một cách đồng thời đối với các đối tượng không
gian và cơ sở dữ liệu thuộc tính tương ứng để đảm bảo bản đồ địa chính sau chuyển đổi
vẫn có cơ sở dữ liệu thuộc tính tương thích.
Cập nhật dữ liệu từ các tệp dữ liệu thuộc tính của bản đồ địa chính trong hệ nguồn vào
các tờ bản đồ địa chính trong hệ đích bằng cách tham chiếu qua một chỉ số duy nhất của
thửa đất. Chỉ số này cần được lưu trữ cùng với cơ sở dữ liệu thuộc tính đồng thời thể
hiện dưới dạng một đối tượng đồ họa dạng Text nằm trong ranh giới thửa đất. Đối tượng
này được chuyển sang hệ mới đồng thời với quá trình chuyển đổi tọa độ của các đối
tượng không gian.
Bản đồ tổng thể theo đơn vị hành chính sau khi chuyển đổi hệ tọa độ, tiến hành biên
tập lại, tạo mô hình Topo, các thửa đất vẫn lưu trữ chỉ số duy nhất của thửa đất. Khi cần
cập nhật thông tin sẽ tham chiếu đến chỉ số này để lấy thông tin thuộc tính.
2.3. Giải pháp chuyên môn hóa công tác nội - ngoại nghiệp
2.3.1. Giải pháp đề xuất
- Phân lô thửa đất
Phân chia khu vực đo vẽ thành các lô thửa đất liền kề. Các lô thửa đất này được
phân chia theo nguyên tắc phân tách nhau bằng các đối tượng hình tuyến như giao
thông, thủy lợi phù hợp với đặc điểm khu đo. Tiến hành đánh số lô thống nhất từ đầu
đến cuối trong quá trình đo đạc và biên tập bản đồ. Chỉ số tham chiếu duy nhất đến thửa
đất sẽ là: MX.SL.ST, trong đó MX là mã xã, SL là số hiệu lô, ST là số hiệu thửa đất
trong lô. Việc đánh số thửa đất thực hiện tuần tự, không được trùng lặp trong lô sao cho
các thửa đất liền kề nhau có số hiệu thửa kề nhau để dễ tìm kiếm. Việc đánh số hiệu thửa
có thể được thực hiện ngay khi vẽ sơ họa các lô thửa đất. Từ đó, các thửa đất được định
danh duy nhất, dễ dàng trong thu thập thông tin thuộc tính, không xảy ra nhầm lẫn khi
một số thông tin trùng nhau.
- Tạo dữ liệu không gian và dữ liệu thuộc tính
- In các lô thửa đất
- Đo đạc ngoại nghiệp
- Xử lý số liệu nội nghiệp sơ bộ
- Kiểm tra đối soát

, y
i
); mỗi đối tượng
vùng được biểu diễn bằng một chuỗi những cặp toạ độ (x
j
, y
j
) với điểm đầu và điểm cuối
trùng nhau.
Đặc điểm: Cấu trúc Spaghetti không ghi nhận đặc trưng kề nhau của hai vùng kề
nhau, nghĩa là tại hai vùng kề nhau sẽ có hai cạnh chung kề nhau, cạnh chung của hai
vùng kề nhau là hai cạnh độc lập nhau.
Cấu trúc này đơn giản, dễ trình bày, biên tập vì vậy vẫn được sử dụng rộng rãi để
thành lập bản đồ, tuy nhiên khối lượng lưu trữ lớn, trùng lặp dữ liệu, không ghi nhận đặc
trưng kề nhau của các vùng nên khó áp dụng trong quản lý dữ liệu bản đồ số địa chính.
2.4.2. Mô hình dữ liệu Topo
Là một mô hình phức tạp, các đối tượng được quản lý không chỉ bởi toạ độ mà còn
bằng cả mối quan hệ không gian giữa các đối tượng.
2.4.2.1. Cấu trúc Winged-Edge Topology
Cấu trúc Winged-Edge Topology (còn gọi là cấu trúc cạnh có cánh) quản lý các cạnh
thửa đất với các mối liên kết cạnh trái trước, trái sau, phải trước, phải sau, mặt trái, mặt
phải. Các cạnh đều phải xác định hướng.
Đặc điểm của cấu trúc này lưu trữ các cạnh theo hướng do đó việc xác định hướng
của cạnh thửa cần đặc biệt quan tâm, từ đó mới xác định được các cạnh trái trước, trái
sau, phải trước, phải sau.
Ưu điểm: Khối lượng lưu trữ dữ liệu nhỏ do không dư thừa dữ liệu, mỗi cạnh liên kết
với bốn cạnh khác.
Nhược điểm: Cách lưu trữ tương đối phức tạp, phải tạo mô hình Topo trước thì mới
xây dựng được cấu trúc dữ liệu.
2.4.2.2. Cấu trúc dữ liệu Doubly Connected Edge List (DCEL)

việc quản lý mô hình Topo thửa đất, tuy nhiên cấu trúc dữ liệu DCEL quản lý các nửa
cạnh độc lập là cấu trúc đơn giản, dễ hiểu, nên dễ xử lý. Chính vì vậy, trong nghiên cứu
của luận án, chọn mô hình Topo với cấu trúc dữ liệu DCEL để nghiên cứu.

CHƯƠNG 3. SỬ DỤNG CẤU TRÚC DỮ LIỆU DCEL
TRONG THÀNH LẬP VÀ ỨNG DỤNG BẢN ĐỒ SỐ ĐỊA CHÍNH
Các phần mềm biên tập bản đồ địa chính ở Việt Nam hiện nay hầu hết chỉ tập
trung tạo mô hình Topo mà chưa chú trọng đến việc lưu trữ mối quan hệ Topo của các
vùng. Chính vì vậy, mỗi khi có sự biến động về thông tin không gian của vùng cần phải
xây dựng lại mô hình Topo. Quá trình này vừa tốn thời gian, vừa mất đi các thông tin
thuộc tính của các vùng đã có. Sau khi tạo lại Topo người sử dụng phải gắn thêm các dữ
liệu thuộc tính cho các vùng phát sinh và việc này thường khó kiểm soát bởi các vùng
biến động có thể ở nhiều nơi trên bản vẽ. Chính vì vậy, người sử dụng thông thường gán
lại toàn bộ cơ sở dữ liệu thuộc tính trên bản vẽ khi có bất kỳ một biến động nào về vùng
dù chỉ những thay đổi nhỏ. Đây là một trong những công việc tốn thời gian và dễ nhầm
lẫn, bỏ sót trong công tác nội nghiệp.
Để giải quyết vấn đề này, cần phải xây dựng một hệ thống biên tập chuyên dụng
với một mô hình cấu trúc dữ liệu Topo phù hợp đồng thời có các giải pháp để quản lý cơ
sở dữ liệu khi có biến động về vùng mà vẫn đảm bảo mối quan hệ Topo giữa các vùng.
Với cấu trúc dữ liệu lựa chọn là DCEL một số vấn đề quan trọng trong công tác thành
v
1

v
2
v
3
v
4
Hình 2.6. Mô hình cấu trúc

3

a
1

a
2
v
5

a
3
10
lập và ứng dụng bản đồ số như tạo mô hình Topo, biên tập thửa đất, chồng phủ các vùng
cần có những giải pháp, thuật toán cụ thể để thực hiện.
Trước hết cần nghiên cứu một số thuật toán cơ sở sẽ áp dụng trong việc sử dụng
cấu trúc DCEL thành lập và ứng dụng bản đồ số địa chính.
3.1. Một số thuật toán cơ sở
3.1.1. Sắp xếp và tìm kiếm
3.1.1.1. Sắp xếp nhanh
3.1.1.2. Tìm kiếm nhị phân
3.1.2. Xác định điểm nằm ở phía nào của đoạn thẳng
Đoạn thẳng được xem như một vectơ có chiều từ đầu mút thứ nhất đến đầu mút
thứ hai. Khi giải quyết bài toán này, chúng ta cần chú ý đến các trường hợp ba điểm
thẳng hàng. Hàm ccw có ba giá trị 1, -1 và 0, trong đó 1: điểm xét ở bên trái, -1 :điểm
xét ở bên phải. Khi ba điểm thẳng hàng, 1: đầu mút thứ hai nằm giữa, -1: đầu mút thứ
nhất nằm giữa, 0: điểm xét nằm trong đoạn thẳng. Hàm này được xây dựng trên cơ sở
xét dấu của tích có hướng hai vectơ, vectơ thứ nhất là bản thân đoạn thẳng, vectơ thứ hai
nối từ điểm thứ hai đến điểm xét.
3.1.3. Kiểm tra giao của hai đoạn thẳng

). Diện tích đại số của đa giác S
được tính theo công thức cơ bản:
11

 




n
1i
1i1ii
yyx
2
1
S
với y
n+1
= y
1
; y
0
= y
n

Diện tích đại số cho giá trị có dấu, nếu tính theo chiều kim đồng hồ sẽ có dấu
dương, tính ngược chiều kim đồng hồ có dấu âm.
3.1.7. Xác định góc hợp bởi phương thẳng đứng với đoạn thẳng
Một đoạn thẳng AB nối hai điểm A (x
A




+ π
Nếu α < 0 thì α = α + 2* π (Để đảm bảo α luôn không âm)
3.2. Thuật toán tạo mô hình Topo sử dụng cấu trúc DCEL
3.2.1. Nhập điểm, sắp xếp và lọc điểm trùng.
Sau khi nhập điểm là tọa độ các đầu mút của các đoạn, việc sắp xếp được thực
hiện theo thứ tự: đầu tiên theo X, sau đó theo Y đối với các điểm có X giống nhau.
Việc sắp xếp theo hoành độ X sử dụng thuật toán cơ sở QuickSort (theo thuật toán
3.1.1.1), còn khi sắp xếp theo Y vì số điểm trong mỗi đoạn cần sắp nhỏ hơn nhiều, nên
có thể sắp xếp theo các phương pháp khác hiệu quả hơn như sắp xếp chọn, sắp xếp
chèn Việc phát hiện và lọc điểm trùng được tiến hành song song với quá trình sắp xếp
theo Y, các điểm trùng sẽ bị loại bỏ và các điểm còn lại sẽ được dồn lên trên. Độ phức
tạp của bước này phụ thuộc vào việc sắp xếp, do sử dụng QuickSort nên về mặt trung
bình độ phức tạp sẽ là O(nlogn).
Kết quả thu được là một danh sách điểm đã được sắp xếp với số lượng điểm N
đ
3.2.2. Xác định các đoạn hở, các đoạn giao nhau
Một trường hợp thường xảy ra trong thực tế đo đạc ngoại nghiệp, khi một điểm
được đo hai lần, do sai số đo và tính toán, dẫn đến tọa độ thu được của điểm này các lần
đo có giá trị khác nhau.
Đối với trường hợp cần loại bớt một giá trị tọa độ, phải có chỉ tiêu điểm trùng.
Cách giải quyết trong trường hợp nối tắt cần xác định vị trí giao nhau của hai cạnh
(theo thuật toán 3.1.3), bổ sung một điểm mới và dùng điểm này để chia các cạnh nối tắt
thành hai cạnh mới.
3.2.3. Nhập cạnh, sắp xếp, lọc cạnh trùng

Sau khi thực hiện việc sắp xếp và lọc điểm trùng, các đầu mút của các đoạn có chỉ
số khác nhau sẽ phải trỏ tới các điểm khác nhau. Sau đó sử dụng hàm tìm kiếm nhị phân

.Prev là nửa cạnh trước, e
i
.Twin là nửa cạnh đảo của nửa
cạnh xét e
i
; e
i-1
là nửa cạnh bên trái; e
i+1
là nửa cạnh bên phải có cùng đỉnh gốc với e
i
đã
sắp xếp theo góc so với phương thẳng đứng (nếu cùng một đỉnh chỉ có hai hướng thì nửa
cạnh trái và nửa cạnh phải trùng nhau; nếu có ba hướng trở lên thì nửa cạnh trái của nửa
cạnh đầu là nửa cạnh cuối và nửa cạnh phải của nửa cạnh cuối là nửa cạnh đầu trong
danh sách sắp xếp theo đỉnh gốc). Gắn thông tin nửa cạnh trước và nửa cạnh sau của
cạnh e
i
theo công thức:
e
i
.Prev = e
i+1
.Twin; (e
i
.Twin).Next = e
i-1
(3.1)

Trên hình 3.3a nửa cạnh xét e

2
a. Đỉnh 2 hướng b. Đỉnh nhiều hơn 2 hướng
e
i

e
i+1

e
i-1

e
i

e
i+1

e
i-1

Hình 3.
3
. Xác đ
ị
nh thu
ộ
c tính DCEL

e
k

mới gặp phải các đường đa giác cụt, thì các điểm cần loại lại nằm ở giữa.
Kết quả của quá trình khoanh vùng là xác định được danh sách các vùng lưu trữ
bởi danh sách đỉnh vùng DV(). Xác định diện tích đại số của từng vùng theo danh sách
DV(), nếu diện tích đại số của vùng nhỏ hơn 0 ("vùng âm") thì đó là vùng bao ngoài của
nhiều vùng có diện tích đại số lớn hơn 0 ("vùng dương") liên thông hoặc là vùng nằm
trong một "vùng dương" khác ("vùng đảo"). Như vậy, đối với những "vùng âm", cần
phải thực hiện một phép kiểm tra xem vùng này có nằm trong một vùng nào trong số các
"vùng dương" hay không, nếu không sẽ là vùng ngoài biên, còn nếu có sẽ là "vùng đảo"
của vùng đó và gắn thông tin "vùng đảo" cho DCEL.
Kết quả của quá trình khoanh vùng là cấu trúc DCEL đầy đủ cho các vùng.
Sử dụng thuật toán cơ sở tìm điểm trong vùng để lấy được chỉ số thửa đất, từ đó
gắn kết với bảng thông tin thuộc tính cập nhật thông tin thuộc tính.
3.3. Biên tập thửa đất sử dụng cấu trúc DCEL
Sau khi xây dựng được cấu trúc DCEL của các thửa đất, mối quan hệ Topo giữa
các thửa đất đã được xác lập, tuy nhiên quá trình biên tập thửa đất không thể tránh được
các thao tác tách, gộp thửa nhất, thêm, bớt đỉnh thửa trong quá trình cập nhật biến động
đất đai. Vấn đề đặt ra là làm thế nào biên tập các thửa đất mà không làm phá vỡ cấu trúc
DCEL đã được xác lập, bảo toàn cấu trúc dữ liệu Topo.
3.3.1. Tách thửa đất
Ký hiệu các đỉnh là v kèm chỉ số, ví dụ như v
i
; các nửa cạnh có kí hiệu là e, ví dụ
như e
j
, các vùng kí hiệu là a, ví dụ như a
k
. Một thửa đất (sau đây gọi tắt là thửa) a
i
sẽ bao
gồm một danh sách các nửa cạnh có thuộc tính vùng (thửa) là a

i
và e
j
. Hình 3.4 mô tả các các cạnh (e
i
, e’
i
), (e
j
, e'
j
) và các vùng a
1
,
a
2
, a
3
trước khi vùng a
2
bị chia. Khi đó e
i
và e
j
có cùng thuộc tính vùng là a
2
còn các nửa
cạnh đảo e'
i
và e'

, e
j2
. Các nửa cạnh đảo
e'
i
, e'
j
cũng được xử lý tương tự, sẽ phát sinh các nửa cạnh e
k
, e’
k
và các vùng a
4
,
a
5.
(Hình 3.5). Các thuộc tính của e
i1
, e
i2
sẽ lấy theo thuộc của nửa cạnh e
i
; các thuộc tính
của e’
i1
, e’
i2
lấy theo thuộc tính của nửa cạnh đảo e’
i
; tương tự, các thuộc tính của e

- xuất phát từ nửa cạnh chia e
k
có điểm đầu là v
1
, điểm cuối là v
2
, xác định e
j2
có
gốc là điểm cuối v
2
rồi tìm nửa cạnh tiếp theo của e
j2
.
- tìm nửa cạnh tiếp theo cho đến khi nửa cạnh tiếp theo là e
i1
có điểm cuối là v
1

- cập nhật thuộc tính cho tất cả nửa cạnh trên vùng thành a
4

Tạo vùng a
5
:
-Làm tương tự như trên cho nửa cạnh đảo e'
k
b. Hai đầu mút của đường chia là đỉnh thửa
Nếu đầu mút của đường chia là đỉnh, các nửa cạnh mới và đỉnh mới được tạo ra
chỉ nằm trên đường chia e

j
e'
j
Hình
3.4.

Các c
ạ
nh th
ử
a đ
ấ
t trư
ớ
c khi chiaa
3

a
5

a
1

e
k

e'

e'
i2

e
i
v
1

v
2

15
Quá trình tạo các vùng a
4
, a
5
sẽ được tiến hành tương tự như mô tả ở mục a, với
vai trò của e
i
như e
i1
, e
j
như e
j2
; e
i+1
như e
i2
, e

. Thông tin DCEL của các nửa cạnh nét liền trên
hình vẽ cần được cập nhật lại.
3.3.3. Thêm bớt đỉnh
Trường hợp tổng quát khi cạnh (gồm hai nửa cạnh e
k
, e’
k
đảo nhau) được thay thế
bằng một đường đa tuyến có cùng chung điểm đầu và điểm cuối hoặc ngược lại. Ta nhận
thấy các cạnh của đường đa tuyến có thuộc tính giống với (e
k
, e’
k
), do đó chỉ cần sao
chép thuộc tính của cạnh (e
k
, e’
k
) cho từng cạnh của đa tuyến hoặc ngược lại và bổ sung
hoặc loại bỏ các điểm, các nửa cạnh cần thiết, cập nhật thêm thông tin nửa cạnh sau và
nửa cạnh trước cần thiết. Việc thêm bớt đỉnh thửa không làm tăng giảm số vùng.
3.3.4. Tạo đường song song với cạnh chọn
Sau khi chọn được cạnh, nhập khoảng cách và chọn phía tạo đường song song, sẽ
xác định được thửa đất chứa nửa cạnh chọn. Tiến hành tìm giao điểm của đường song
song này với các nửa cạnh của thửa đất, từ đó xác định các điểm v
7
, v
8
và tạo ra hai vùng
mới a


e'
i

e
i+1

e'
i+1
e
j

e'
j

e
j+
e'
j+1

a
5
a
2
a
4
a
3
a
1

thuộc vùng b
1
(Hình 3.11)

Nửa cạnh đảo với e
i
được ký hiệu là e
i
'
, vùng giáp bên phải của e
i
'

là a
2
Nửa cạnh đảo với ej được ký hiệu là ej', vùng giáp bên phải của ej' là b
2

Xét 4 nửa cạnh e
i
, e'

tính vùng phải a
1
, trong đó gốc của nửa cạnh thứ nhất e
i1
trùng với gốc của e
i
là v
1
, còn
gốc của nửa cạnh thứ hai e
i2
là điểm chia v
5

Theo nguyên tắc chia trên ta có nửa cạnh e
j
sẽ được chia thành hai nửa cạnh e
j1
và
e
j2
có cùng hướng, cùng thuộc tính vùng phải b
1
, gốc của e
j1
trùng với gốc của e
j
là v
3
,

j2
, e
j1
'
, e
j2
'

- từ các vùng a
1
, a
2
và b
1
, b
2
ta có các vùng chồng phủ a
1
b
1
, a
1
b
2,
a
2
b
1
, a
2

a
1

b
2

b
1

e
i

e'
i

e
j

e'
j

Hình 3.
11
. Giao nhau c
ủ
a hai c
ạ
nh

v

i
e
j2

e'
j
Hình 3.12
. Nguyên t
ắ
c chia c
ạ
nhv
5

e
i1

e'
i
e
j1

e'
j
a
2
b

5
là e
j2
và
e'
j1

có góc nghiêng ngược nhau 180
o
.
Để tìm nửa cạnh ngoặt về bên phải chỉ
cần tính góc kẹp phải tại v
5
của hai nửa
cạnh e
i1
và e
j2
, nếu góc kẹp này có giá
trị từ 0
o

đến 180
o
thì nửa cạnh e
j2
là nửa
cạnh cần tìm, trường hợp góc kẹp này
lớn hơn 180
o

tính vùng a
1
cho đến giao điểm tiếp
theo. Quá trình này chỉ kết thúc khi
quay trở về giao điểm đầu tiên. Kết quả
một vùng chồng phủ mới sẽ được tạo ra
với thuộc tính a
1
b
1
và thuộc tính vùng
của các nửa cạnh nói trên sẽ phải được lưu thêm thuộc tính là a
1
b
1
.
Bằng cách tạo các vùng mới tại tất cả các giao điểm của vùng a
1
ta sẽ lần lượt tạo
ra các vùng chồng phủ mới có các thuộc tính a
1
b
i
.
Khi lát kín vùng a
1
các cạnh của của vùng b
i
bên trong a
1

và sử dụng thuật toán
định vị điểm theo phương pháp bản đồ hình thang với độ phức tạp O(logn) để xác định
điểm thuộc vùng b
j
nào.
v
2

v
1

v
3

v
4

a
2

a
1

b
2

b
1

e


b
j

a
i

Hình 3.14. Lát kín một vùng khi
có giao điểm trên đường biên
Ph
ần còn lại (nếu có)
sau khi
xét h
ết các nửa cạnh của a
iCác vùng của bản đồ A: nét liền

Các vùng của bản đồ B: nét đứt

18
Biết được vùng b
j
thì toàn bộ vùng a
i

sẽ được lát kín nếu vùng b
j
không chứa các

nửa cạnh này. Tất cả các nửa cạnh bị chia sẽ
lưu thành nửa cạnh lịch sử.
b. Lát từng vùng a
i
(i=1-n) theo sơ đồ thuật
toán ở hình 3.16.
3.4.4. Đánh giá thuật toán chồng phủ
Để thực hiện chồng phủ hai tờ bản đồ
cần xác định giao điểm mà độ phức tạp của
bài toán xác định giao điểm theo các tài liệu
đều là O(nlogn) nên độ phức tạp của cả quá trình chồng phủ sẽ là O(nlogn).
Việc xử lý lát từng vùng theo thuật toán trên với cấu trúc dữ liệu danh sách cạnh
liên kết kép sẽ cho độ phức tạp thuật toán trung bình là O(n) do xử lý lần lượt từng phần
tử của danh sách, trường hợp cần sử dụng thuật toán tìm điểm trong vùng có độ phức tạp
là O(logn). Như vậy, độ phức tạp của thuật toán chồng phủ trên cũng sẽ là O(nlogn).
Điều đó cho thấy, với thuật toán xây dựng, độ phức tạp thuật toán của quá trình
chồng phủ không tăng nhưng lại đem lại sự linh hoạt cho các thao tác biên tập vùng khi
chồng phủ.
3.5. Sử dụng cấu trúc DCEL tạo các ứng dụng bản đồ số địa chính
3.5.1. Lập hồ sơ địa chính
Hồ sơ địa chính bao gồm: Bản đồ địa chính; Sổ mục kê đất đai (thể hiện thông tin
thửa đất theo từng tờ bản đồ); Sổ địa chính (thể hiện thông tin chủ sử dụng); Sổ theo dõi
biến động đất đai (lưu trữ lịch sử biến động đất đai); Bảng tổng hợp số thửa, diện tích, số
chủ sử dụng quản lý đất theo hiện trạng đo đạc lập bàn đồ địa chính; Bản mô tả ranh
a
i

b
j


- Thống kê diện tích đất đai, tạo các bảng biểu báo cáo.
Trong các vấn đề trên, vấn đề liên kết các thửa đất liền kề có cùng mục đích sử
dụng tốn nhiều thời gian và dễ xảy ra nhầm lẫn. Với cấu trúc DCEL thuật toán xử lý vấn
đề này như sau:
- Bước 1. Ghép các DCEL của các lô thửa đất bản đồ thành DCEL tổng; Đối với
các vùng nằm giữa các lô thửa đất thường là các đối tượng giao thông thủy hệ hình
tuyến sẽ thêm các đoạn liên kết giữa các lô thửa để khép kín các đối tượng này bằng
công cụ biên tập thửa đất;
- Bước 2. Xác định thuộc tính loại đất hiện trạng cho các nửa cạnh DCEL tổng;
- Bước 3. Duyệt qua các nửa cạnh của DCEL tổng, nếu các nửa cạnh và nửa cạnh
đảo có cùng thuộc tính loại đất thì sẽ bị loại bỏ đồng thời gắn thuộc tính nửa cạnh trước
và nửa cạnh sau cho các nửa cạnh thay đổi, sau quá trình này sẽ được DCEL mới của
các vùng hiện trạng;
- Bước 4. Khoanh vùng các vùng hiện trạng theo thuật toán khoanh vùng sử dụng
cấu trúc DCEL đã trình bày ở trên.
Với DCEL mới này vấn đề tổng hợp diện tích, tô màu các vùng hiện trạng theo
loại đất trở nên tương đối đơn giản.

3.5.3. Lập bản đồ giải phóng mặt bằng
Trong công tác giải phóng mặt bằng, bản đồ địa chính là tài liệu vô cùng quan
trọng. Nếu có dữ liệu bản đồ địa chính số được cập nhật biến động đất đai thường xuyên
và chính xác thì quá trình lập hồ sơ giải phóng mặt bằng giản đơn hơn nhiều. Lúc này,
20
chỉ cần đưa ranh giới giải phóng mặt bằng lên bản đồ địa chính, từ đó xác định các thửa
đất liên quan đến công tác giải phóng mặt bằng bằng cách xác định các thửa đất có giao
với đường ranh giới giải phóng mặt bằng. Trên bản đồ địa chính chứa đầy đủ các thông
tin như thông tin chủ sử dụng đất, tổng diện tích thửa đất, mục đích sử dụng, địa chỉ
đây là những thông tin quan trọng trong quá trình giải phóng mặt bằng.
Với cấu trúc DCEL thuật toán tạo vùng cho bản đồ giải phóng mặt bằng như sau:
Bước 1. Tiến hành tạo DCEL bản đồ ranh giới giải phóng mặt bằng với các vùng

xử lý Pentium với các lỗi FDIV.
4.3. Xây dựng chương trình thử nghiệm
Chương trình được tác giả xây dựng bằng ngôn ngữ lập trình Visual Basic 6.0.
4.3.1. Giao diện chương trình
Chương trình được thiết kế với giao diện một cửa sổ đồ họa, hệ thống trình đơn
bằng tiếng Việt và hệ thống thanh công cụ.
4.3.2. Các trình đơn
*. Trình đơn Tệp: Tạo mới, mở bản vẽ DXF, Shape file, DCEL, ghi lại
*. Trình đơn Vẽ: Vẽ các đối tượng đồ họa cơ bản như Điểm, Đoạn thẳng, Đa tuyến
21
*. Trình đơn Hiển thị: Các chức năng hiển thị như thu, phóng, trượt
*. Trình đơn Tiện ích: Có các chức năng Sửa lỗi, tạo vùng, gán chỉ số thửa, chính xác
hóa tọa độ, nhập thông tin thuộc tính, tra cứu thông tin, gộp thửa, chia thửa, tạo bản đồ
hiện trạng, chuyển sang Google Earth, chồng xếp bản đồ.
4.3.3. Giải pháp tạo thư viện liên kết động phục vụ xây dựng chương trình
- Tạo ra 1 file Link.exe mới đặt trong thư mục C:\Program Files\Microsoft Visual
Studio\VB98, còn file Link.exe thật thì đổi tên thành 1 file khác (ví dụ là LinkThat.exe).
Khi IDE gọi file Link.exe giả (do ta xây dựng lại) thì file Link.exe này sẽ làm nhiệm vụ
đọc các tham số được IDE truyền sang, thêm tham số "/DEF" vào và gọi file
LinkThat.exe với tham số mới (đã có /DEF). Tất nhiên là phải kiểm tra, nếu có tồn tại
các file *.DEF và Project (dự án) cần tạo là Project kiểu DLL thì mới thêm tham số.
- Tạo một Project mới trong VB6, kiểu Project là ActiveX DLL. Để nguyên
Class1 mà VB6 đã tạo sẵn, không cần viết mã lệnh gì vào đó cả, nhưng vẫn phải giữ lại
vì VB6 cần phải có 1 Class trong Project kiểu ActiveX DLL thì mới chạy. Sau đó, thêm
vào một module để chứa các hàm cần xây dựng bình thường như các Sub hay Function
với khai báo Public (dùng chung).
- Tạo tệp Module Definition File (*.DEF): Sử dụng trình soạn thảo NotePad soạn
một file cùng tên với tên thư viện cần tạo và có đuôi là DEF
- Dịch Project đã tạo ở bước trên tạo thành file DLL dạng Standard, khi đã có thư
viện liên kết động dạng *.DLL (ví dụ: MyLibrary.Dll). Kết quả, được thư viện liên kết

tuyến trục 105
0
, múi chiếu 3
0
.
 Cách sử dụng chương trình:
Bước 1: Sử dụng chức năng mở tệp DXF cần chuyển;
Bước 2: Chọn chức năng chuyển sang Google Earth với kinh tuyến trục 105
0
, múi
chiếu 3
0
;
Bản đồ sau khi chuyển sang Google Earth sẽ giúp cho việc quản lý và đối soát
thuận lợi.
c. Thử nghiệm sử dụng cấu trúc DCEL trong biên tập và xây dựng ứng dụng bản đồ số
địa chính
*. Tạo mô hình Topo

*. Nhập thông tin thửa đất từ cơ sở dữ liệu
Dữ liệu thuộc tính thửa đất được lưu trữ trong bảng tính Excel được liên kết với
dữ liệu không gian thông qua chỉ số duy nhất của thửa đất.
*. Gộp thửa


dựng cũng như những giải pháp hoàn thiện quy trình công nghệ thành lập và ứng dụng
bản đồ số địa chính mang tính khả thi và phù hợp với điều kiện Việt Nam; giải pháp
tăng tốc độ tính toán thực sự hiệu quả, có thể áp dụng trong các ngôn ngữ lập trình và
các chương trình khác nhau.