HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
BÙI THANH HUYỀN
NGHIÊN CỨU MỘT SỐ THUẬT TOÁN PHÂN TÍCH KHÔNG GIAN
TRONG HỆ THÔNG TIN ĐỊA LÝ CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01

Người hướng dẫn khoa học: PGS. TS. Đặng Văn Đức TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI – 2012

- 1 -
MỞ ĐẦU
Hệ thống thông tin địa lý GIS (Geographical Information

Hệ thông tin địa lý (GIS - Geographical Information System), là
một hệ thống thông tin có khả năng thu thập, cập nhập, quản trị và
phân tích, biểu đồ dữ liệu địa lý phục vụ giải quyết các bài toán ứng
dụng có liên quan tới vị trí địa lý trên bề mặt trái đất hoặc được định
nghĩa như làm một hệ thông tin với khả năng truy nhập, tìm kiếm, xử
lý, phân tích và truy xuất dữ liệu địa lý nhằm hỗ trợ cho công tác
quản lý, quy hoạch và quản lý tài nguyên thiên nhiên, môi trường và
y tế.
Mục tiêu của GIS là cung cấp cấu trúc một cách hệ thống để
quản lý các thông tin địa lý khác nhau và phức tạp, đồng thời cung
cấp các công cụ, các thao tác hiển thị, truy vấn, mô phỏng… Cái GIS
cung cấp là cách thức suy nghĩ mới về không gian. Phân tích không
gian chỉ là truy cập mà còn cho phép khai thác các quan hệ và tiến
trình biến đổi của chúng. Công nghệ GIS tích hợp giữa các thao tác
trên cơ sở dữ liệu như: đưa ra các câu hỏi truy vấn (query), phân tích
thống kê (statistcal analysis) với việc thể hiện và các phép phân tích
địa lý.
Những khả năng đó của hệ thống GIS đã phân biệt GIS với các
hệ thống thông tin khác và tạo cho nó một giá trị đến khu vực công
cộng và các nhân để giải thích các sự kiện, và lên kế hoạch chiến
lược.
1.2. Các thành phần của GIS
Hệ thống GIS có 5 thành phần cơ bản bao gồm con người,
phương pháp, phần cứng tin học, phần mềm tin học và dữ liệu. Tầm
quan trong mỗi thành phần và các mối quan hệ giữa chúng:
1.2.1. Con người (People)
Công nghệ GIS sẽ bị hạn chế nếu không có con người tham gia
- 3 -
quản lý hệ thống và phát triển những ứng dụng GIS trong thực tế.
Người sử dụng GIS có thể là những chuyên gia kỹ thuật, người thiết

trong hệ thống địa lý luôn được xây dựng trên một hệ thống tọa độ.
Mô hình dữ liệu quyết định cách thức mà dữ liệu được cấu trúc,
lưu trữ, xử lý và phân tích trong một hệ thông tin địa lý. Mô hình dữ
liệu raster sử dụng lưới để thể hiện đặc trưng không gian. Mô hình
dữ liệu Vector sử dụng các điểm và tọa độ của chúng để xây dựng
các đặc trưng không gian như điểm, đường và vùng. Các đặc trưng
dựa trên mô hình dữ liệu véctơ được coi như các đối tượng riêng biệt
trong không gian. Nhiều hệ thông tin địa lý sử dụng cả hai mô hình
dữ liệu vector và raster
Mô hình dữ liệu dạng raster phản ánh toàn bộ vùng nghiên cứu
dưới dạng một lưới các ô vuông hay điểm ảnh (pixel). Mô hình raster
có các đặc điểm:
Các điểm được xếp liên tiếp từ trái qua phải và từ trên xuống
dưới.
Mỗi một điểm ảnh (pixel) chứa một giá trị.
Một tập các ma trận điểm và các giá trị tương ứng tạo thành một
lớp (layer).
Trong cơ sở dữ liệu có thể có nhiều lớp.
Mô hình dữ liệu raster là mô hình dữ liệu GIS được dùng tương
đối phổ biến trong các bài toán về môi trường, quản lý tài nguyên
thiên nhiên.
Mô hình raster chủ yếu dùng để phản ánh các đối tượng dạng
vùng là ứng dụng cho các bài toán tiến hành trên các loại đối tượng
dạng vùng: phân loại, chồng xếp. Các nguồn dữ liệu raster có thể bao
gồm:
Quét ảnh
Ảnh máy bay, ảnh viễn thám
Chuyển từ dữ liệu Vector sang
Lưu trữ dữ liệu dạng raster.
Nén theo hàng (Run lengh coding).

khác nhau. Kỹ thuật xây dựng các chức năng cũng rất khác nhau.
Chức năng của một hệ thống thông tin địa lý được phân chia thành
năm loại như sau: Thu thập dữ liệu, thao tác dữ liệu, quản lý dữ liệu,
hỏi đáp và phân tích, và hiển thị.
- 6 -
Nhập dữ liệu là quá trình mã hóa dữ liệu thành dạng có thể
dùng trên máy tính và ghi dữ/ liệu vào cơ sở dữ liệu GIS. Nhập
dữ liệu là một công việc đòi hỏi thời gian và công sức và kinh
phí (giá thành xây dựng CSDL ban đầu thường là 5 -10 lần giá
thành phần cứng và phần mềm).
Có những trường hợp các dạng dữ liệu luôn đòi hỏi được
chuyển dạng và thao tác theo một số cách để có thể tương thích với
một hệ thống nhất định. Công nghệ GIS cung cấp nhiều công cụ cho
các thao tác trên dữ liệu không gian và cho loại bỏ dữ liệu không cần
thiết.
- 7 -
CHƯƠNG 2 – NGHIÊN CỨU MỘT SỐ THUẬT
TOÁN PHÂN TÍCH DỮ LIỆU KHÔNG GIAN
2.1. Các thuật toán xếp chồng bản đồ
Xếp chồng bản đồ là phần cốt lõi của hoạt động phân tích GIS.
Nó kết hợp một số tính năng không gian để tạo ra yếu tố mới không
gian. Mặt khác, xếp chồng bản đồ có thể được định nghĩa là một hoạt
động không gian, kết hợp các lớp địa lý khác nhau để tạo ra lớp
thông tin. Xếp chồng bản đồ được thực hiện bằng cách sử dụng số
học, logic, các toán tử quan hệ và được thực hiện trong cả hai loại dữ
liệu Vector và Raster.
Quá trình thực hiện Overlay bản đồ qua 2 bước:
Xác định tọa độ các giao điểm và tiến hành chồng khít 2 lớp
bản đồ tại giao điểm này.
Kết hợp dữ liệu không gian và thuộc tính của hai lớp bản đồ.

một thuật toán quét dòng để liệt kê tất cả các đoạn thẳng giao nhau
trong mặt phẳng. Tương tự như các thuật toán khác để kiểm tra có
hay không các đoạn thẳng giao nhau, với đầu vào là n đoạn thẳng và
k điểm cắt nhau BO có độ phức tạp là O(n+k)logn.
2.1.4. Thuật toán giao của hai đa giác
Đã có nhiều thuật toán tìm giao của hai đa giác được công bố
[RIG] [JOS]. Phần lớn các thuật toán này xuất phát từ tìm giao của
hai đa giác lồi. Do vậy, nếu vùng nghiên cứu đa giác bất kỳ thì chúng
phải được tách ra thành đa giác lồi trước khi thực hiện thuật toán.
Phát biểu bài toán: Hãy tìm phần giao của hai đa giác phẳng
không tự cắt A và B. Cho biết A = a
1
a
2
…a
n
và B = b
1
b
2
… b
m
.
Chi tiết thuật toán
Phần giao của A và B có thể là tập rỗng hay là tập các đa giác
không giao nhau. Để đơn giản ta gọi phần giao của A bà B là tập đa
giác giao, và gọi một cạnh là cạnh của tập đa giác giao với ý nghĩa
nó là cạch của một đa giác trong tập đa giác giao.
Với P là một đa giác thì ta gọi I(P) và O(P) lần lượt là miền
trong và miền ngoài của P.

i
a
i+1
} (nếu trong X
x
có nhiều điểm trùng nhau thì chỉ giữ lại một
điểm trong số các điểm trùng nhau đó).
Sắp xếp các điểm trong X
x
theo chiều tằng dần về khoảng cách
từ mỗi điểm đến a
i
, ta được X
x
= {x
1
= a
i
, x
2
,…,x
lv
= a
i+1
}, với |X
x
|=
lv. Khi đó, cạnh x
i
x

k+1
), thì chèn a
i
vào giữa
b
k
và b
k+1
, tức là coi b
k
a
i
và a
i
b
k+1
là hai cạnh mới của đa giác B.
Xử lý tương tự cho ba đỉnh: a
i+1
, b
k
, b
k+1
.
Sau đó, xét mỗi cặp cạnh trùng nhau v=a
i
a
i+1
 A và u = b
k

,…,x
lv-1
, x
lv
= a
i+2
},
Y
u
= { y
1
= b
k+1
, y
2
,…, y
lu-1
, y
lu
= b
k+2
}.
- 10 -
Để kiểm tra xem cạng a
i
a
i+1
(hoặc b
k
b

nằm cùng phía so với M và O(P) (I(P)) sẽ nằm khác phía so với M,
theo một hướng đi trên một cạnh nào đó thuộc đa giác P.
Xét về vị trí tương đối của M với đa giác A và của N với đa
giác B ta thấy chỉ có bốn trường hợp sau:
1. NI(B) và MO(A).
2. NO(B) và MI(A).
3. NI(B) và MI(A).
4. NO(B) và MO(A).
Xét trường hợp 1:
Vì N I(B) chiều thuận của đa giác B là chiều đi từ b
k
đến
b
k+1
(1)
Vì MO(A) Chiều thuận của đa giác A là chiều đi từ a
i
đến
a
i+1
(2).
Từ (1), (2) và giả thiết a
i
a
i+1
 b
k
b
k+1
=>  một đa giác là giao

i+1
không phải là cạnh
của tập đa giác giao.
Các thuật toán liên quan.
Thuật toán trình bày trên có sử dụng hai thuật toán khác nhau
để cài đặt, đó là kiểm tra điểm trong đa giác và tìm giao của hai đoạn
thẳng. Để kiểm tra một điểm có nằm trong đa giác hay không ta có
thể sử dụng thuật toán sau:
Đầu vào: Cho trước đa giác P và điểm p.
Đầu ra: p nằm trong hay ngoài P.
Begin
if (p nằm trong cạnh P), p trong P
else
đếm =0
l = tia song song trục X vẽ từ p
for (i=1 to n)
begin
if (nếu cạnh (i) cắt l) and not cạng (i) không trùng với l) then
begin
if (một đầu cuối của cạnh (i) nằm phía trên tia l) đếm= đếm
+1
end
end for
if (đếm là lẻ ), p nằm trong P
endif
end
Để tìm giao của hai đoạn thẳng ta sử dụng thuật toán biểu diễn
đoạn thẳng bằng phương pháp tham số như sau:
Phương trình đoạn thẳng là cạnh đa giác được xác định từ hai
tọa độ đỉnh liên tiếp. Giả sử ta có tham số t thay đổi từ 0 đến 1 cho

– y
C
) (2)

)3(
))(())((
))(())((
))(())((
))(())((
ABDCDCAB
ABACACAB
ABDCDCAB
ACACDCAC
yyxxyyxx
yyxxyyxx
s
yyxxyyxx
yyxxyyxx
t












được thực hiện theo thuật toán sau:
Đầu vào: Đa giác P, Q
Đầu ra: P và Q có giao nhau?
begin
if (không có cạnh nào của p cắt cạnh nào đó của Q) do
- 13 -
begin
p = điểm bất kỳ nào trên biên của P
if (p nằm trong Q)
P Q
else
begin
q = điểm bất kỳ trên biên của Q
if (q nằm trong Q)
Q P
else P và Q không giao nhau
end if
end if
else P giao với Q
end
Độ phức tạp của thuật toán tìm giao các cạnh hai đa giac sẽ là
O(nlogn).
Bước 2. Phân lớp các đỉnh đa giác p và Q. Mỗi đỉnh đa giác
được gán bởi giá trị I (trong), O (ngoài) hay B (biên) so với đa giác
kia. Các giá trị này được thực hiện nhờ thuật toán điểm trong đa giác
trình bày trên. Các giá trị của đỉnh được lưu vào danh sách P
V
cho đa
giác P và Q
V

Mỗi đoạn của đa giác này sẽ nằm toàn bộ trong hay toàn bộ ngoài đa
giác kia. Ta có thể sử dụng tính chất mô tả ở phần trên để xác định
- 14 -
các đoạn thẳng nằm trong hay ngoài đa giác: nếu điểm giữa đoạn
thẳng nằm trong hay nằm ngoài đa giác thì đoạn thẳng đó sẽ nằm
trong hay nằm ngoài đa giác.
Bước 4. Lập các đa giác kết quả. Từ danh sách P
V
và Q
V
ta lọc
ra các đoạn thẳng có giá trị I hay B để lập các đa giác mới.
Quan sát các bước của thuật toán trên thì bước có độ phức tạp
lớn nhất. Nó đòi hỏi tìm giao điểm của mọi cạnh hai đa giác cho nên
có độ phức tạp O(n
2
), việc xem giá trị giao điểm vào danh sách sẽ có
độ phức tạp O(k
3
), trong đó k là số phần tử trong danh sách. Trường
hợp xấu nhất sẽ là k = n
3
. Do vậy, độ phức tạp của bước này sẽ là
O(n
2
).
Thuật toán tìm giao của hai đa giác là nền tảng của việc xây
dựng chức năng xếp chồng của hệ thống GIS vector.

2.2. Thuật toán vùng đệm không gian

xác định các đối tượng có giao điểm hay nằm chồng nên các đối
tượng khác. Hai đa giác giao nhau nếu chúng có một miền chung.
Hai đường thẳng cắt nhau nếu chúng có một điểm chung. Một đường
thẳng giao nhau với một đa giác khi nó nằm một phần hay toàn bộ
trong đa giác.
Tìm kiếm các đối tượng liền kề với đối tượng khác: Đây là kiểu
tìm kiếm trong đó các đối tượng có chung đường bao (biên). Quan hệ
này chỉ áp dụng cho đường thẳng hoặc đa giác.
Tìm các đối tượng liền kề các đối tượng khác. Đây là kiểu tìm
kiếm trong đó các đối tượng có chung đường bao (biên). Quan hệ
này chỉ áp dụng cho đường thẳng hoặc đa giác.
Tìm các đối tượng nằm bên trong hay bên ngoài một khung
cách xác định: Kiểu tìm kiếm này được sử dụng trong việc xác định
đối tượng xung quanh một hay nhiều các điểm mốc. Quá trình thực
hiện bao gồm việc tạo ra một vùng đệm các điểm mốc này và sau đó
xác định các đối tượng căn cứ vào vị trí của chúng so với vùng đệm
tạo ra.
2.2.4. Xử lý trong buffer
- 16 -
Buffer hay còn gọi là truy vấn không gian trên cơ sở các quan
hệ không gian giữa các đối tượng. Các quan hệ này thông thường nói
lên vị trí tương đối của đối tượng này với đối tượng kia. Phương
pháp buffer được chia làm nhiều loại khác nhau, nhưng cách xử lý
thì luôn tuân theo các bước cơ bản sau:
Chọn một hay nhiều đối tượng trên bản đồ, gọi là các đối tượng
gốc.
Hiển thị tập các đối tượng tìm thấy cả trên dữ liệu không gian
và thuộc tính.
Áp dụng một quan hệ không gian để tìm ra các đối tượng khác
mà có quan hệ đặc biệt với các đối tượng gốc.

quốc gia và lãnh thổ trong đất liền đến 200 dặm ngoài biển (hoặc 200
dặm đối với đất liền và 12 dặm đối với các đảo – Mỗi dặm tương
đương 1,6Km). Như vậy, để qui trình tự động hóa xác định đường
cách đều được tổ chức một cách chặt chẽ và đúng với thực tiễn, ta
chỉ xét đường ranh giới cách đều đối với những quốc gia đối diện
nhau mà có khoảng cách nhỏ nhất giữa hai đường biển không được
lớn quá 400 dặm. Ngoài ra qui trình xác định hoàn toàn dựa trên căn
cứ toán học, hình học, không xét đến các yếu tố ngoại lệ, các đảo
được xét đến với mức ưu tiên tương tự như đường biên thuộc phần
đất liền.
Trên thực tế có 3 dạng cấu hình bờ biển giữa hai quốc gia là:
dạng kết thúc mở, dạng đóng và dạng nửa đóng. Ta có thể hiểu các
thuật ngữ này một cách đơn giản như sau:
- Dạng kết thúc mở là dạng cấu hình của vùng biển mà bao gồm
hai đường bờ biển đối diện nhau và không có điểm chung.
- Dạng đóng là trường hợp một vùng nước biển được giới hạn
bởi hai quốc gia gần kề và đối diện nhau tạo thành hồ khép kín.
- Dạng nửa đóng là dạng vùng biển mà tạo bởi hai quốc gia kề
sát nhau. Ta có điểm khởi đầu để xác định đường cách đều chính là
điểm mà biên giới trên đất liền gặp bờ biển còn điểm kết thúc chưa
xác định.
Đối với mỗi trường hợp kết thúc đóng, mở và nửa đóng thì có
điều kiện khởi đầu và két thúc qui trình xác định đường cách đều
- 18 -
khác nhau.
2.3. Một số thuật toán tìm đường đi tối ưu ứng dụng trong
GIS
2.3.1. Phát biểu bài toán
Các thuật toán đồ thị nổi tiếng xác định đường đi “ngắn nhất ”
giữa hai điểm A và B trên mạng lưới đường phố mà tiêu chuẩn “ngắn

E: tập cạnh), một hàm trọng số w: E [0,∞) và một đỉnh nguồn s
Đầu ra: Hãy tìm đường đi ngắn nhất từ tập nguồn s đến mỗi
đỉnh trong đồ thị.
2.3.3. Thuật toán Bellman-Ford
Ban đầu, giả sử rằng tất cả chiều dài của các cung là không âm.
Nếu một số chiều dài cung là âm thì điều gì sẽ xảy ra? Ví dụ, xét đồ
thị trong hình 2.2. Đường đi ngắn nhất từ đỉnh s đến đỉnh t là (s, 1),
(1, t), chiều dài của nó là +2 – 2 = 0. Có thể dễ dàng nhận thấy rằng
nếu thuật toán tìm đường đi ngắn nhất Dijkstra được áp dụng trong
đồ thị này thì đường đi (s, t) được chọn nhầm là đường đi ngắn nhất
từ đỉnh s đến đỉnh t. Vì vậy, không đảm bảo rằng thuật toán tìm
đường đi ngắn nhất Dijkstra sẽ sinh ra đường đi ngắn nhất khi chiều
dài cung được cho phép là âm.
2.3.4. Thuật toán A*
Thuật toán A* được mô tả lần đầu vào năm 1968 bởi Peter Hart,
Nils Nilsson, và Bertram Raphael. Trong bài báo của họ, thuật toán
được gọi là thuật toán A; khi sử dụng thuật toán này với một đánh
giá heuristic thích hợp sẽ thu được hoạt động tối ưu, do đó mà có tên
A*. Thuật toán A* (đọc là A sao) là một thuật toán tìm kiếm trong đồ
thị. Thuật toán này tìm một đường đi từ một nút khởi đầu tới một nút
đích cho trước (hoặc tới một nút thỏa mãn một điều kiện đích). Thuật
toán này sử dụng một "đánh giá heuristic" để xếp loại từng nút theo
ước lượng về tuyến đường tốt nhất đi qua nút đó. Thuật toán này
duyệt các nút theo thứ tự của đánh giá heuristic này. Do đó, thuật
toán A* là một ví dụ của tìm kiếm theo lựa chọn tốt nhất (best-first
search).
- 20 -
CHƯƠNG 3 – CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT
TOÁN
3.1. Mục đích của việc xây dựng công cụ hỗ trợ biên tập

.
Chương trình hoạt động gồm các bước như sau:
Bước 1: Các bản đồ được tải vào chương trình bằng việc người
sử dụng chọn các tệp bản đồ để mở. Khi đó bản đồ sẽ được đưa vào
khung làm việc phần mềm.
Bước 2: Sau khi các đa giác đã được đưa vào trong chương
trình, chương trình cần kiểm tra xem các đa giác đưa vào có cặp nào
song song và giao nhau không. Nếu có cặp cạnh song song và giao
nhau thì chèn thêm những điểm mới vào cho bản đồ và tiến hành sắp
xếp lại các điểm để tìm điểm giao và điểm nằm trong bản đồ.
- 21 -
Bước 3: Dựa vào các điểm giao nhau của các cặp cạnh giữa các
bản đồ và các điểm nằm trong bản đồ, chương trình sẽ tiến hành nối
các điểm đó theo trình tự đã được xác định để tạo ra một bản đồ mới,
đây chính là phần giao của 2 đa giác.
Bước 4: Tiến hành tô màu mới cho phần bản đồ mới được tạo ra
để thuận tiện cho việc theo dõi.
Nhấn vào nút Bản đồ\ Mở bản đồ để mở tệp bản đồ cần đưa vào
kiểm tra.
Nhấn chọn nút Bản đồ\ Phóng to hay thu nhỏ để điều chỉnh sự
hiển thị của bản đồ.
Nhấn nút Bản đồ\ Lưu bản đồ để lưu lại kết quả.
Nhấn nút Công cụ\Chồng phủ bản đồ để tiến hành chồng phủ
bản đồ và tìm ra phần giao của các bản đồ.
Nhấn vào nút Quản lý bản đồ để điều chỉnh mầu nền hoặc mầu
đường viên cho các bản đồ.
Thực hiện chồng phủ hai lớp bản đồ cho kết quả chính xác với
nhiều kiểu giao nhau của bản đồ. Phần mầu vàng cho kết quả chồng
phủ của hai lớp bản đồ.


Thuật toán tìm giao của hai đa giác là nền tảng của việc xây
dựng chứa năng xếp chồng phủ các lớp bản đồ của hệ thống GIS
vector. Kết quả thực nghiệm cho thấy thuật toán giao của hai đa giác
chính xác gần như hoàn toàn. Các thuật toán còn lại tôi chỉ dừng lại ở
mức độ nghiên cứu chưa đi vào cài đặt thử nghiệm. Tuy nhiên các
thuật toán đã trình bày trong luận văn là thuật toán khả thi trong việc
xác định đường phân chia hải giới và tìm đường đi ngắn nhất.
KIẾN NGHỊ VÀ HƯỚNG PHÁT TRIỂN:
Với bước đầu nghiên cứu cài đặt thử nghiệm chương trình đã
tạo tiền đề ứng dụng an toàn dữ liệu trao đổi trong môi trường web
và từ đó đưa chương trình vào ứng dụng thực tế. Trong thời gian tới,
tôi sẽ tiếp tục phát triển đề tài với phương hướng cụ thể như sau:
Hoàn thiện công cụ với tất cả các phép toán xử lý thông dụng
trong GIS.
Nghiên cứu một số một số vấn đề giúp người biên tập bản đồ.
Xây dựng một công cụ hỗ trợ xử lý bản đồ số, thực hiện tự động
phép toán tính vùng đệm của đối tượng bản đồ, nhằm giúp giảm bớt
thời gian và công sức xử lý, biên tập bản đồ.
Cải tiến và nâng cao hiệu quả của các chức năng năng đã cài đặt
trên giao diện cũng như các kỹ thuật cài đặt khác.