i

LỜI CẢM ƠN
Trước tiên tôi xin chân thành cảm ơn PGS.TS. Đặng Văn Đức, Viện Công
nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, người đã định
hướng và tận tình hướng dẫn, giúp đỡ tôi trong quá trình thực hiện luận văn tốt
nghiệp.
Tôi xin chân thành cảm ơn các thầy giáo, cô giáo trường Đại học Công nghệ
thông tin và truyền thông - Đại học Thái Nguyên đã tận tình truyền đạt các kiến
thức, quan tâm, động viên trong thời gian tôi học tập và nghiên cứu tại Trường.
Tôi xin chân thành cảm ơn Trường THPT Chuyên Bắc Kạn đơn vị tôi đang
công tác đã hết sức tạo điều kiện để tôi có thể hoàn thành nhiệm vụ học tập của
mình.
Cho phép tôi gửi lời cảm ơn tới các bạn học cùng CK12I - lớp chuyên ngành
Khoa học máy tính, đã giúp đỡ, chia sẻ kinh nghiệm, cung cấp các tài liệu hữu ích
trong thời gian tôi học tập, nghiên cứu tại Trường cũng như trong trong quá trình
thực hiện luận văn tốt nghiệp vừa qua.
Vì lượng kiến thức thực tế còn ít nên trong luận văn của em khó tránh khỏi
những hạn chế và khiếm khuyết, em rất mong nhận được sự đóng góp ý kiến của
các thầy giáo, cô giáo và các bạn để bản thân em có thể hoàn thành tốt hơn kiến
thức của mình.
Em xin trân trọng cảm ơn!
Thái Nguyên, tháng 9 năm 2015

Hạ Thị Thảo


ii

LỜI CAM ĐOAN
Tôi xin cam đoan bản luận văn “Các cấu trúc dữ liệu trong hệ thống thông

tin địa lý.” là công trình nghiên cứu của tôi dưới sự hướng dẫn khoa học của
PGS.TS. Đặng Văn Đức, tham khảo các nguồn tài liệu đã được chỉ rõ trong trích
dẫn và danh mục tài liệu tham khảo. Các nội dung công bố và kết quả trình bày
trong luận văn này là trung thực và chưa từng được ai công bố trong bất cứ công
trình nào.
Thái Nguyên, tháng 09 năm 2015

Hạ Thị Thảo


iii

DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ

Ký hiệu/từ
viết tắt

Viết đầy đủ

CSDL

Cơ sở dữ liệu

ESRI

Environmental

Ý nghĩa
Cơ sở dữ liệu
Systems Viện nghiên cứu Hệ thống môi


Research Institute

trường Mỹ

GIS

Geographic Information System

Hệ thống thông tin địa lý

I/O

Input/Output

Nhập/Xuất

XUB

X on Upper Bound

X ở trên biên

YUB

Y on Upper Bound

Y ở trên biên

XLB


X on Lower Bound

X ở dưới biên

YLB

Y on Lower Bound

Y ở dưới biên


iv

DANH MỤC CÁC BẢNG
Bảng 2.1: Các trường hợp của phép chèn vào cây tứ phân điểm ............................ 33
Bảng 2.2: Mô tả bốn cành của nút N trong cây tứ phân MX ................................... 35
Bảng 3.1 Các nút lệnh trên thanh công cụ .............................................................. 56
DANH MỤC CÁC HÌNH
Hình 1.1 Hệ thông tin địa lý (ESRI) ........................................................................ 3
Hình 1.2: Sự ảnh hưởng của lựa chọn kích thước tế bào .......................................... 5
Hình 1.3: Trật tự không gian.................................................................................... 6
Hình 1.4: Số liệu vectơ được biểu thị dưới dạng điểm (Point). ................................. 8
Hình 1.5: Số liệu vectơ được biểu thị dưới dạng Arc ............................................... 8
Hình 1.6: Số liệu vectơ được biểu thị dưới dạng vùng (Polygon) ............................. 9
Hình 1.7: Các nhóm chức năng trong GIS ............................................................. 12
Hình 2.1: Cây k-d tương ứng khi cho các điểm có sẵn ........................................... 20
Hình 2.2: Lưới bản đồ dựng cây ............................................................................ 21
Hình 2.3: Trình tự chèn vào cây 2-d ...................................................................... 22
Hình 2.4: Phép chèn cây k-d trên bản đồ................................................................ 23

Hình 2.5: Cách phân hoạch mặt phẳng bởi các điểm xã trên cây tứ phân điểm ...... 30
Hình 2.6: Tiến trình chèn vào cây tứ phân điểm..................................................... 31
Hình 2.7: Mô hình một cây tứ phân điểm............................................................... 32
Hình 2.8: Trình tự chèn vào cây tứ phân MX ......................................................... 36
Hình 2.9: Phép chèn điểm vào cây tứ phân MX ..................................................... 37
Hình 2.10: Sơ đồ R - Tree...................................................................................... 39
Hình 2. 11: Bản đồ mẫu mô tả cách nhóm các hình chữ nhật minh họa cây R........ 40
Hình 2.12: Ví dụ về tập hợp các đoạn thẳng được nhúng với lưới 4 x 4 ................. 41
Hình 2.13: Tập hợp các đoạn thẳng và không gian được bao bởi các hình chữ nhật42
Hình 2.14: Trình tự chèn vào cây R ....................................................................... 44
Hình 2.15: Bản đồ mô tả phép chèn trong cây R .................................................... 45
Hình 2.16: Mô tả phép tách ................................................................................... 47
Hình 3.1: Mô hình Use Case của hệ thống ............................................................. 51
Hinh 3.2: Giao diện chính của chương trình .......................................................... 55
Hình 3.3: Bản đồ sau khi hiển thị cả lớp đường và lớp điểm. ................................. 56
Hình 3.4. Bản đồ hiển thị lớp điểm ........................................................................ 57
Hình 3.5 Truy vấn vùng trên bản đồ lớp điểm........................................................ 57
Hình 3.6: Kết quả của truy vấn trên hình 3.5.......................................................... 58
Hình 3.7: Truy vấn vùng trên bản đồ tổng thể ........................................................ 58
Hình 3.8: Kết quả của truy vấn vùng trên bản đồ tổng thể...................................... 59


v

MỤC LỤC
LỜI CẢM ƠN .......................................................................................................... i
LỜI CAM ĐOAN .................................................................................................... ii
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ .......................................... iii
DANH MỤC CÁC BẢNG ..................................................................................... iv
DANH MỤC CÁC HÌNH ...................................................................................... iv

MỤC LỤC .............................................................................................................. v
MỞ ĐẦU ................................................................................................................ 1
CHƯƠNG 1: TỔNG QUAN VỀ HỆ THỐNG THÔNG TIN ĐỊA LÝ (GIS) ........... 3
1.1 Một số khái niệm cơ bản về GIS ........................................................................ 3
1.2 Cấu trúc dữ liệu địa lý........................................................................................ 3
1.2.1 Dữ liệu không gian ....................................................................................... 4
1.2.2 Dữ liệu phi không gian ................................................................................. 9
1.3 Các chức năng của GIS .................................................................................... 11
1.4 Tìm kiếm và phân tích dữ liệu không gian ....................................................... 13
1.4.1 Tìm kiếm nội dung trong vùng không gian ................................................. 13
1.4.2 Tìm kiếm trong khoảng cận kề.................................................................... 14
1.4.3 Tìm kiếm hiện tượng và thao tác bao phủ (overlay) .................................... 14
1.4.4 Nội suy và mô hình hóa bề mặt ................................................................... 15
1.4.5 Phân tích đường đi và đường dẫn................................................................ 15
1.4.6 Mô hình hóa tương tác không gian.............................................................. 15
1.4.7 Đồ họa và tương tác .................................................................................... 16
CHƯƠNG 2: MỘT SỐ CẤU TRÚC DỮ LIỆU SỬ DỤNG TRONG GIS ............ 17
2.1 Vấn đề lưu trữ và chỉ mục dữ liệu địa lý .......................................................... 17
2.2 Cây k-d (k-d tree) ............................................................................................ 18
2.2.1 Cấu trúc nút ................................................................................................ 19
2.2.2 Chèn và tìm kiếm trong cây 2-d ................................................................. 20
2.2.3 Xóa trong cây 2-d ....................................................................................... 24
2.2.4 Truy vấn khoảng trong cây 2-d .................................................................. 25
2.2.5 Cây k-d với k≥2 ......................................................................................... 28
2.3 Cây tứ phân điểm (Point quadtree)................................................................... 28
2.3.1 Chèn và tìm kiếm trong cây tứ phân điểm .................................................. 30
2.3.2 Thao tác xoá trên cây tứ phân điểm............................................................ 31
2.3.3 Truy vấn khoảng trong cây tứ phân điểm .................................................... 33



vi

2.4 Cây tứ phân Matrix MX (MX-Quadtree) ......................................................... 34
2.4.1 Chèn và tìm kiếm trong MX-Quadtree ....................................................... 35
2.4.2 Thao tác xoá trong MX-Quadtree ............................................................... 37
2.4.3 Truy vấn khoảng trong MX-Quadtree ........................................................ 38
2.5 Cây R (R - Tree) .............................................................................................. 39
2.5.1 Chèn và tìm kiếm trong R-Tree .................................................................. 42
2.5.2 Xoá trong R-Tree ........................................................................................ 45
2.5.3 Thuật toán tách nút (Node Splitting ) .......................................................... 46
2.5.4 Cây R* (R*- Tree) ...................................................................................... 47
2.6 So sánh các cây dữ liệu .................................................................................... 48
CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH THỬ NGHIỆM .......................... 50
3.1 Lựa chọn bài toán thử nghiệm và công nghệ sử dụng ....................................... 50
3.1.1 Phát biểu bài toán ....................................................................................... 50
3.1.2 Cách giải quyết ........................................................................................... 50
3.2 Mô tả dữ liệu thử nghiệm................................................................................. 52
3.3 Phân tích và thiết kế chương trình thử nghiệm ................................................. 53
3.3.1 Công cụ xây dựng chương trình .................................................................. 53
3.3.2 Đặc tả chức năng của chương trình ............................................................. 53
3.4 Đánh giá kết quả thu được ............................................................................... 54
3.4.1 Cài đặt và thử nghiệm ................................................................................. 54
3.4.2 Kết quả thử nghiệm .................................................................................... 54
3.4.3 Nhận xét kết quả thu được .......................................................................... 59
3.4.4 Hiệu quả truy vấn khi sử dụng các cấu trúc dữ liệu cây............................... 59
KẾT LUẬN ........................................................................................................... 61
TÀI LIỆU THAM KHẢO ..................................................................................... 62
PHỤ LỤC.............................................................................................................. 63



1

MỞ ĐẦU
Ngày nay, hệ thống thông tin địa lý – Geographic Information System(GIS)
đã trở nên phổ biến và là yếu tố không thể thiếu đối với hầu hết các chuyên ngành.
GIS đánh giá được hiện trạng của các quá trình, các thực thể tự nhiên, kinh tế-xã hội
thông qua các chức năng thu thập, quản lý, truy vấn, phân tích và tích hợp thông tin.
Nó được gắn với một nền bản đồ số nhất quán trên cơ sở toạ độ của các dữ liệu đầu
vào. Về bản chất GIS là một hệ thống. Các yếu tố cấu thành GIS là phần cứng, phần
mềm, các cơ sở dữ liệu, phương pháp và con người. Trong các yếu tố này, cơ sở dữ
liệu có vai trò cực kỳ quan trọng trong hệ thống góp phần làm nên sức mạnh của hệ
thống.
Tình hình nghiên cứu, kết quả nghiên cứu đã có:
Cấu trúc dữ liệu là một thành phần quan trọng nhất và được coi là lõi của hệ
thống thông tin địa lý GIS. Do đó đây là vấn đề được đề cập đến rất nhiều trên thế
giới, tuy nhiên cách tiếp xúc tiếp xúc vấn đề có nhiều khía cạnh khác nhau đặc biệt
là ở Việt Nam. Để hình thức hoá, trừu Tượng hoá dữ liệu GIS người ta cần đến các
kỹ thuật như cây k-chiều, cây tứ phân, cây R... Đồng thời còn phải quan tâm đến
các phương pháp cài đặt các kĩ thuật này. Các đề tài nghiên cứu đã có chỉ là ứng
dụng CSDL GIS để xây dựng ứng dụng chứ chưa có đề tài nghiên cứu thể hiện các
cấu trúc dữ liệu GIS cụ thể. Do đó tác giả tập trung nghiên cứu các kỹ thuật trên các
cây dữ liệu GIS.
Có thể nói cấu trúc dữ liệu là phần khung và bản chất nhất của các hệ thống
GIS, nó là cơ sở của các giải thuật GIS cũng như nói đến khả năng lưu trữ khai thác,
phát triển hệ thống dữ liệu. Những nghiên cứu của luận văn không có gì mới so với
thế giới, nhưng là mới ở nước ta. Xuất phát từ thực tế đó tôi chọn đề tài “Các cấu
trúc dữ liệu trong hệ thống thông tin địa lý.”
Trong khuôn khổ luận văn, tôi trình bày một số vấn đề cơ bản về hệ thống
thông tin địa lý (GIS), các kỹ thuật truy vấn không gian trong GIS. Mô tả cấu trúc,
các phép toán xây dựng, chèn, xóa, duyệt, truy vấn trên cấu trúc dữ liệu sử dụng



2

trong GIS. Trong đó, tập trung nghiên cứu và cài đặt thử nghiệm một số cấu trúc dữ
liệu không gian.
Bố cục của luận văn bao gồm phần mở đầu, phần kết luận và ba chương nội
dung được tổ chức như sau:
Chương 1: Tổng quan về hệ thống thông tin địa lý
Chương này trình bày tổng quan về hệ thống thông tin địa lý, các kỹ thuật
truy vấn không gian trong GIS, khả năng của GIS.
Chương 2: Một số cấu trúc dữ liệu sử dụng trong GIS
Chương này mô tả cấu trúc, các phép toán chèn, xoá, duyệt, truy vấn trên các
kỹ thuật chỉ mục và tìm kiếm không gian như: cây k-d (k-d Tree), cây tứ
phân(Quadtree), cây R (R Tree), R* Tree và so sánh giữa chúng
Chương 3: Xây dựng chương trình thử nghiệm
Cài đặt thử nghiệm cây tứ phân điểm. Chương trình được cài đặt từ cơ sở
dữ liệu đã có định dạng bằng Shapefile, với ngôn ngữ lập trình C#.NET cùng
với thư viện hỗ trợ SharpMap.


3

CHƯƠNG 1: TỔNG QUAN VỀ HỆ THỐNG THÔNG TIN ĐỊA LÝ (GIS)
1.1 Một số khái niệm cơ bản về GIS
GIS - Geographic Information System hay hệ thống thông tin địa lý được
hình thành từ ba khái niệm địa lý, thông tin và hệ thống. Khái niệm “địa lý” liên
quan đến các đặc trưng về không gian, vị trí. Các đặc trưng này liên kết trực tiếp đến
các đối tượng trong không gian. Chúng có thể là vật lý, văn hoá, kinh tế, tự nhiên...
Khái niệm “thông tin” đề cập đến phần dữ liệu được quản lý bởi GIS. Đó là các dữ

liệu về thuộc tính và không gian của đối tượng. GIS có tính “hệ thống” tức là hệ
thống GIS được xây dựng từ các module. Việc tạo module giúp thuận lợi trong việc
quản lý và hợp nhất.

Hình 1.1 Hệ thông tin địa lý (ESRI) [1]
GIS là một hệ thống có ứng dụng rất lớn. Từ năm 1980 đến nay đã có rất
nhiều các định nghĩa được đưa ra, tuy nhiên không có định nghĩa nào khái quát đầy
đủ về GIS vì phần lớn chúng đều được xây dựng trên khía cạnh ứng dụng cụ thể
trong từng lĩnh vực. Có ba định nghĩa được dùng nhiều nhất:
GIS là một hệ thống thông tin được thiết kế để làm việc với các dữ liệu trong
một hệ toạ độ quy chiếu. GIS bao gồm một hệ cơ sở dữ liệu và các phương thức để
thao tác với dữ liệu đó.GIS là một hệ thống nhằm thu thập, lưu trữ, kiểm tra, tích
hợp, thao tác, phân tích và hiển thị dữ liệu được quy chiếu cụ thể vào trái đất.
GIS là một chương trình máy tính hỗ trợ việc thu thập, lưu trữ, phân tích và
hiển thị dữ liệu bản đồ.
1.2 Cấu trúc dữ liệu địa lý


4

Một cơ sở dữ liệu của hệ thống thông tin địa lý có thể chia ra làm 2 loại dữ
liệu cơ bản: dữ liệu không gian và phi không gian. Mỗi loại có những đặc điểm
riêng và chúng khác nhau về yêu cầu lưu giữ số liệu, hiệu quả, xử lý và hiển thị.
1.2.1 Dữ liệu không gian
Dữ liệu không gian là những mô tả số của hình ảnh bản đồ, chúng bao gồm
toạ độ, quy luật và các ký hiệu dùng để xác định một hình ảnh bản đồ cụ thể trên
từng bản đồ. Hệ thống thông tin địa lý dùng các số liệu không gian để tạo ra một
bản đồ hay hình ảnh bản đồ trên màn hình hoặc trên giấy thông qua thiết bị ngoại vi.
Hệ thông tin địa lý sử dụng hai mô hình dữ liệu cơ bản để biểu diễn các đặc trưng
không gian: mô hình dữ liệu raster và mô hình dữ liệu vectơ. Mô hình không gian

đặc biệt quan trọng vì cách thức biểu diễn thông tin sẽ ảnh hưởng đến khả năng hiển
thị đồ họa của hệ thống.
1.2.1.1 Mô hình dữ liệu raster
Đây là phương pháp biểu diễn các đặc trưng địa lý bằng các điểm ảnh. Được
hình thành dựa trên cơ sở quan sát nền thế giới thực.
Mô hình dữ liệu raster hay còn gọi là lưới tế bào hình thành nền cho một số
hệ thông tin địa lý. Các hệ thống trên cơ sở raster hiển thị, định vị và lưu trữ dữ liệu
đồ họa nhờ sử dụng các ma trận hay lưới tế bào. Độ phân giải dữ liệu raster phụ
thuộc vào kích thước của tế bào hay điểm ảnh, chúng có thể khác nhau từ vài
đêximet đến vài kilômet. Trong cấu trúc dữ liệu raster, point có thể được biểu diễn
bằng một cell. Line được biểu diễn bởi một tập các cell có hướng xác định, độ rộng
của line bằng chiểu rộng của một cell. Polygon được biểu diễn bởi một đãy các cell
nằm kề sát nhau. Tiến trình xây dựng lưới tế bào được mô tả như sau đây:[1]
Giả sử phủ một lưới lên bản đồ, dữ liệu raster được lập bằng cách mã hóa
mỗi tế bào bằng một giá trị dựa theo các đặc trưng trên bản đồ, độ chính xác của
một đối tượng phụ thuộc vào kích thước hay độ phân giải của các tế bào lưới.


5

Hình 1.2: Sự ảnh hưởng của lựa chọn kích thước tế bào
Bản đồ lại được chia thành nhiều tầng, mỗi tầng bao gồm hàng triệu tế bào vì
vậy cần áp dụng các thuật toán nén dữ liệu mà vẫn cho khả năng khôi phục dữ liệu
ban đầu.
Hình dạng bao phủ toàn bộ bản đồ gọi là khảm, khảm có thể là hình vuông,
tam giác hay lục giác tuy nhiên khi sử dụng khảm hình tam giác hoặc lục giác sẽ
khó khăn trong việc phân chia tế bào thành các tế bào nhỏ hơn, cách mã hóa, lưu trữ
tế bào khó khăn hơn rất nhiều.
Lợi thế của hệ thống raster là mã dữ liệu đồ họa thành bản đồ trong máy tính
nên các thao tác so sánh tế bào là dễ dàng song không thuận tiện cho việc biểu diễn

đường, đoạn, điểm vì mỗi loại là một tập hợp các tế bào và có đoạn rộng, đoạn hẹp.
Một vấn đề khó khăn nữa là xử lý tế bào trộn là tế bào có nhiều hơn một đặc trưng
(như trong ví dụ trên một số ô có thể đánh một trong hai giá trị tùy theo hoạt động
của chương trình hay quan niệm của người lập), vấn đề này dẫn tới khó khăn khi có
nhu cầu phân tích là phủ bản đồ. Vì thế raster thích hợp hơn với hệ thống GIS
hướng tài nguyên, môi trường vì hình thành trên sơ sở quan sát nền thế giới thực.
Raster có nhiều tầng bản đồ (địa hình, đất đai..) hơn so với mô hình vectơ.
Cấu trúc dữ liệu raster
Số lượng dữ liệu của mô hình là rất lớn do đó cần có kĩ thuật quản lý khối dữ
liệu sao cho dễ quản lý và dễ xâm nhập. Các phương pháp hay dùng là phân hoạch
dữ liệu và xây dựng chỉ số xâm nhập nhanh.
-Phân hoạch dữ liệu: Phân hoạch CSDL không gian để quản lý khối lượng
lớn thông tin bằng tập giới hạn các thao tác. Hai chiến lược được sử dụng đó là: mỗi
phân hoạch chứa số lượng thông tin xấp xỉ nhau và kích thước địa lý có thể khác


6

nhau; phân hoạch địa lý cố định và lượng thông tin trong mỗi phân hoạch có thể
khác nhau.
-Xây dựng chỉ số xâm nhập nhanh (hay chỉ số không gian). Ý tưởng chính
của xây dựng chỉ số không gian là sử dụng khái niệm xấp xỉ qua phân hoạch số
lượng thông tin xấp xỉ. Nếu mỗi đặc trưng có thêm trường chỉ số để chỉ ra nơi chứa
chúng thì việc tìm kiếm địa chỉ sẽ giới hạn trong trường này. Tiến trình đánh số chỉ
số thường sử dụng đó là phân hoạch đệ qui, kết quả là cho ta cấu trúc phân cấp gọi
là cây tứ phân. Trong cây tứ phân mỗi vùng được chia thành bốn vùng và đánh chỉ
số khác nhau, mỗi vùng lại chia tiếp thành bốn phần cho đến khi đạt được kích
thước tế bào cần thiết tuy nhiên phân hoạch như vậy là không hợp lý và tiến trình
phân hoạch chỉ cần tiến hành ở những vùng có nhiều đặc trưng hay được quan tâm
tới nhiều tùy vào các chức năng của bản đồ. Cách đánh chỉ số ở đây thường áp dụng

trật tự Z (sử dụng cách đánh số như nhau ở bốn góc phần tư), trật tự Pi () (sử dụng
cách đánh số đối xứng ở bốn góc phần tư) như sau:

Trật tự Z

Trật tự Pi
Hình 1.3: Trật tự không gian

Ngoài ra có thể sử dụng sơ đồ R-Tree hay R+-tree. R-Tree là cây phân cấp,
mỗi lá của cây là một hình chữ nhật và con trỏ, con trỏ trỏ tới đặc trưng của hình
chữ nhật bao, còn hình chữ nhật xác định bởi tọa độ x,y cực đại và cực tiểu. Tập các
hình chữ nhật được đánh chỉ số là lưu trữ trong tập các thùng. Tuy nhiên R-Tree có
hiện tượng hình chữ nhật trùng nhau nghĩa là hình chữ nhật cắt các thùng nhưng
thùng được biểu diễn chỉ trong một hình chữ nhật, điều này được xử lý trong R+tree bằng cách chia các hình chữ nhật dữ liệu để mỗi hình được biểu diễn trong hai
vùng con.


7

1.2.1.2 Mô hình dữ liệu vectơ
Đây là phương pháp biểu diễn các đặc trưng địa lý bằng các phần tử đồ họa
cơ bản (điểm, đường, đa giác, bề mặt ba chiều và khối trong 3D). Phương pháp
vectơ hình thành dựa trên cơ sở quan sát đối tượng của thế giới thực. Dưới đây là
bảng các thành phần hình học cơ sở:
Kiểu thành

Biểu diễn đồ họa

phần sơ cấp
Điểm


. +

x

Đường

Biểu diễn số
Tọa độ (x,y) trong 2D
Tọa độ(x, y, z) trong 3D
Danh sách tọa độ
Các hàm toán học
Đường có điểm đầu và cuối

Vùng

trùng nhau hay tập các đường
nếu vùng có lỗ hổng
Ma trận điểm; tập các tam giác,

Bề mặt

hàm toán học, đường đồng
mức

Khối

Tập các bề mặt

Kiểu đối tượng điểm (Points)

Điểm được xác định bởi cặp giá trị đơn. Các đối tượng đơn, thông tin về địa
lý chỉ gồm cơ sở vị trí sẽ được phản ánh là đối tượng điểm. Các đối tượng kiểu
điểm có đặc điểm:
* Là toạ độ đơn (x,y)
* Không cần thể hiện chiều dài và diện tích


8

Hình 1.4: Số liệu vectơ được biểu thị dưới dạng điểm (Point).
Tỷ lệ trên bản đồ tỷ lệ lớn, đối tượng thể hiện dưới dạng vùng. Tuy nhiên
trên bản đồ tỷ lệ nhỏ, đối tượng này có thể thể hiện dưới dạng một điểm. Vì vậy,
các đối tượng điểm và vùng có thể được dùng phản ánh lẫn nhau.
Kiểu đối tượng đường (Arcs)
Đường được xác định như một tập hợp đãy của các điểm. Mô tả các đối
tượng địa lý dạng tuyến, có các đặc điểm sau:
*

Là một đãy các cặp toạ độ

*

Một arc bắt đầu và kết thúc bởi node

*

Các arc nối với nhau và cắt nhau tại node

*


Hình dạng của arc được định nghĩa bởi các điểm vertices

*

Độ dài chính xác bằng các cặp toạ độ

Hình 1.5: Số liệu vectơ được biểu thị dưới dạng Arc


9

Kiểu đối tượng vùng (Polygons)
Vùng được xác định bởi ranh giới các đường thẳng. Các đối tượng địa lý có
diện tích và đóng kín bởi một đường được gọi là đối tượng vùng polygons, có các đặc
điểm sau:
* Polygons được mô tả bằng tập các đường (arcs) và điểm nhãn (label points)
* Một hoặc nhiều arc định nghĩa đường bao của vùng
* Một điểm nhãn label points nằm trong vùng để mô tả, xác định cho mỗi
một vùng.

Hình 1.6: Số liệu vectơ được biểu thị dưới dạng vùng (Polygon)
Mô hình vectơ hợp với các hệ GIS định hướng các hệ thống quản trị CSDL,
chúng ưu việt trong lưu trữ số liệu bản đồ bởi chỉ lưu đường biên của các đặc trưng
chứ không lưu cả vùng như trong mô hình raster nên truy nhập, tìm kiếm, hiển thị
dễ dàng thông tin từ CSDL.
1.2.2 Dữ liệu phi không gian
Dữ liệu phi không gian là những diễn tả đặc tính, số lượng, mối quan hệ của
các hình ảnh bản đồ với vị trí địa lý của chúng. Các dữ liệu phi không gian được gọi
là dữ liệu thuộc tính, chúng liên quan đến vị trí địa lý hoặc các đối tượng không
gian và liên kết chặt chẽ với chúng trong hệ thống thông tin địa lý thông qua một cơ

chế thống nhất chung. Thông thường hệ thống thông tin địa lý có 4 loại số liệu
thuộc tính:


10

- Đặc tính của đối tượng: liên kết chặt chẽ với các thông tin không gian có
thể thực hiện SQL (Structure Query Language) và phân tích.
- Số liệu hiện tượng, tham khảo địa lý: miêu tả những thông tin, các hoạt
động thuộc vị trí xác định.
- Chỉ số địa lý: tên, địa chỉ, khối, phương hướng định vị, …liên quan đến các
đối tượng địa lý.
- Quan hệ giữa các đối tượng trong không gian, có thể đơn giản hoặc phức
tạp (sự liên kết, khoảng tương thích, mối quan hệ đồ hình giữa các đối tượng).
Để mô tả một cách đầy đủ các đối tượng địa lý, trong bản đồ số chỉ dùng
thêm các loại đối tượng khác: điểm điều khiển, toạ độ giới hạn và các thông tin
mang tính chất mô tả (annotation).
Annotation: Các thông tin mô tả có các đặc điểm:


Có thể nằm tại một vị trí xác định trên bản đồ



Có thể chạy dọc theo arc



Có thể có kích thước, màu sắc, các kiểu chữ khác nhau




Nhiều mức của thông tin mô tả có thể được tạo ra với ứng dụng khác nhau.



Có thể tạo thông tin cơ sở dữ liệu lưu trữ thuộc tính



Có thể tạo độc lập với các đối tượng địa lý có trong bản đồ



Không có liên kết với các đối tượng điểm, đường, vùng và dữ liệu thuộc

tính của chúng
* Bản chất một số thông tin dữ liệu thuộc tính như sau:
- Số liệu tham khảo địa lý: mô tả các sự kiện hoặc hiện tượng xảy ra tại một
vị trí xác định. Không giống các thông tin thuộc tính khác, chúng không mô tả về
bản thân các hình ảnh bản đồ. Thay vào đó chúng mô tả các danh mục hoặc các hoạt
động như cho phép xây dựng, báo cáo tai nạn, nghiên cứu y tế, … liên quan đến các
vị trí địa lý xác định. Các thông tin tham khảo địa lý đặc trưng được lưu trữ và quản
lý trong các tệp độc lập và hệ thống không thể trực tiếp tổng hợp chúng với các hình
ảnh bản đồ trong cơ sở dữ liệu của hệ thống. Tuy nhiên các bản ghi này chứa các
yếu tố xác định vị trí của sự kiện hay hiện tượng.


11


- Chỉ số địa lý: được lưu trong hệ thống thông tin địa lý để chọn, liên kết và
tra cứu số liệu trên cơ sở vị trí địa lý mà chúng đã được mô tả bằng các chỉ số địa lý
xác định. Một chỉ số có thể bao gồm nhiều bộ xác định cho các thực thể địa lý sử
dụng từ các cơ quan khác nhau như là lập danh sách các mã địa lý mà chúng xác
định mối quan hệ không gian giữa các vị trí hoặc giữa các hình ảnh hay thực thể địa
lý. Ví dụ: chỉ số địa lý về trường học và địa chỉ địa lý liên quan đến trường học đó.
- Mối quan hệ không gian: của các thực thể tại vị trí địa lý cụ thể rất quan
trọng cho các chức năng xử lý của hệ thống thông tin địa lý. Các mối quan hệ không
gian có thể là mối quan hệ đơn giản hay lôgic, ví dụ tiếp theo số nhà 100 phải là số
nhà 102 nếu là số nhà bên chẵn hoặc nếu là bên lẻ thì cả hai đều phải là các số lẻ kề
nhau. Quan hệ Topology cũng là một quan hệ không gian. Các quan hệ không gian
có thể được mã hoá như các thông tin thuộc tính hoặc ứng dụng thông qua giá trị
toạ độ của các thực thể.
- Mối quan hệ giữa dữ liệu không gian và phi không gian: thể hiện phương
pháp chung để liên kết hai loại dữ liệu đó thông qua bộ xác định, lưu trữ đồng thời
trong các thành phần không gian và phi không gian. Các bộ xác định có thể đơn
giản là một số duy nhất liên tục, ngẫu nhiên hoặc các chỉ báo địa lý hay số liệu xác
định vị trí lưu trữ chung. Bộ xác định cho một thực thể có thể chứa toạ độ phân bố
của nó, số hiệu mảnh bản đồ, mô tả khu vực hoặc con trỏ đến vị trí lưu trữ của số
liệu liên quan. Bộ xác định được lưu trữ cùng với các bản ghi toạ độ hoặc mô tả số
khác của các hình ảnh không gian và cùng với các bản ghi số liệu thuộc tính liên quan.
1.3 Các chức năng của GIS
Các chức năng của GIS được chia thành 5 loại sau:
- Thu thập dữ liệu
- Xử lý sơ bộ dữ liệu
- Lưu trữ và truy cập dữ liệu
- Tìm kiếm và phân tích không gian
- Hiển thị đồ họa và tương tác
Sức mạnh của các chức năng của hệ thống GIS khác nhau là khác nhau. Kỹ



12

thuật xây dựng các chức năng trên cũng khác nhau. Hình 1.7 mô tả quan hệ giữa các
nhóm chức năng và cách biểu diễn thông tin khác nhau của GIS. [1]
Chức năng thu thập dữ liệu tạo ra dữ liệu từ các quan sát hiện tượng thế giới
thực và từ các tài liệu, bản đồ giấy, đôi khi chúng có sẵn dưới dạng số. Kết quả ta có
“tập dữ liệu thô”, có nghĩa là dữ liệu này không được phép áp dụng trực tiếp cho
chức năng truy nhập và phân tích của hệ thống. Chức năng xử lý sơ bộ dữ liệu sẽ
biến đổi dữ liệu thô thành dữ liệu có cấu trúc để sử dụng trực tiếp các chức năng tìm
kiếm và phân tích không gian. Kết quả tìm kiếm và phân tích được xem như diễn
giải dữ liệu, đó là tổ hợp hay biến đổi đặc biệt của dữ liệu có cấu trúc. Hệ thống GIS
phải có phần mềm công cụ để tổ chức và lưu trữ các loại dữ liệu khác nhau từ dữ
liệu thô đến dữ liệu diễn giải. Phần mềm công cụ này phải có các thao tác lưu trữ,
truy nhập; đồng thời có khả năng hiển thị, tương tác đồ họa với tất cả loại dữ
liệu.[1]

Hình 1.7: Các nhóm chức năng trong GIS


13

Khả năng của GIS là có thể trả lời các câu hỏi:
Location:What is at...? Tìm ra cái gì tồn tại ở vị trí cụ thể. Vị trí được thể
hiện bằng tên, mã bưu điện hay tọa độ địa lý (kinh/vĩ độ)
Condition: Where is it? Tìm ra vị trí thỏa mãn một số điều kiện (vùng không
có rừng diện tích 2000m2 và xa đường quốc lộ 100m và loại đất phù hợp cho xây
dựng nhà)
Trends: What has changed since...? Tìm ra sự khác biệt theo thời gian trong
vùng

Patterns: What spatial patterns exist? Tìm ra nơi nào phù hợp mẫu, ví dụ
ung thư là nguyên nhân chính của cái chết của người dân gần nhà máy nguyên tử?
Modeling:What if...? Câu hỏi này xác định cái gì xảy ra, ví dụ, nếu có đường
mới mở hay nếu chất độc thải vào nguồn nước...
1.4 Tìm kiếm và phân tích dữ liệu không gian
Có rất nhiều các phương pháp tìm kiếm và phân tích dữ liệu không gian. Đây
là chức năng đóng vai trò rất quan trọng trong GIS. Nó tạo nên sức mạnh thực sự
của GIS so với các phương pháp khác. Truy vấn dữ liệu không gian giúp tìm ra
những đối tượng đồ hoạ theo các điều kiện đặt ra hay hỗ trợ việc ra quyết định của
người dùng GIS. Các phương pháp khác nhau thường tạo ra các ứng dụng GIS khác
nhau. Sau đây là một số phương pháp được dùng phổ biến nhất:
1.4.1 Tìm kiếm nội dung trong vùng không gian
Các phép phân tích không gian tương đối đơn giản là tìm đặc trưng bản đồ
hay một phần của chúng nằm trong vùng cho trước. Vùng có thể là hình chữ nhật
và được xác định bằng hai cặp tọa độ. Phép phân tích này có thể được xem như
phép truy vấn CSDL không gian cơ bản. Lý do để coi chúng là mức độ cao hơn truy
nhập CSDL cổ điển là khả năng cắt xén đối tượng bao như đường và các cạnh đa
giác theo biên cửa sổ. Nhiệm vụ này không thể hoàn thành chỉ bằng ngôn ngữ truy
nhập CSDL quan hệ như SQL mà phải có những xử lý đăck biệt khác. Tìm kiếm nội
dung trong vùng không gian còn được thực hiện trên vùng tạo ra từ các đối tượng


14

không gian sẵn có như vùng xác định bởi các đường biên hành chính xã huyện, khu
công nghiệp....[1]
1.4.2 Tìm kiếm trong khoảng cận kề
Có một vài phương pháp tìm kiếm trong khoảng cận kề. Phương pháp thứ
nhất được xem như mở rộng của tìm kiếm nội dung trong vùng, trong đó vùng được
tìm kiếm được xác định bởi xấp xỉ tới hiện tượng có sẵn. Việc tìm kiếm này được

thực hiện trong vùng tạo bởi mở rộng đối tượng nào cho trước theo một khoảng
cách cho trước. Theo khái niệm GIS thì vùng này được gọi là vùng đệm. Vùng đệm
được xây dựng xung quanh đối tượng điểm, đối tượng đường hay đối tượng vùng.
Trong các hệ thống trên cơ sở raster thì việc tạo lập vùng đệm được thực hiện nhờ
chức năng spread.
Phương pháp thứ hai của tìm kiếm cận kề là tìm ra các vùng nối trực tiếp với
đối tượng xác định từ trước, thí dụ tìm các mảnh đất liền kề với mảnh sẽ xây dựng
nhà máy.
Phương pháp thứ ba xảy ra khi cần phải tìm kiếm những vùng đất gần nhất
với tập các vị trí mẫu phân tán không đều. Các mẫu thường là các điểm. Tìm kiếm
này thực hiện bằng cách tạo lập đa giác Thiessen, nó xác định các vùng xung quanh
mỗi điểm mà gần điểm này hơn các điểm khác. Sơ đồ đa giác Thiessen được gọi là
sơ đồ Voronoi. Chúng được sử dụng để lập ra bản đồ đất sử dụng từ các mẫu đất
cách biệt. [1]
1.4.3 Tìm kiếm hiện tượng và thao tác bao phủ (overlay)
Kỹ thuật tìm kiếm hiện tượng được chia thành nhóm dữ kiện dựa trên tính
chất tìm kiếm đó là:
Tìm một hiện tượng, không quan tâm đến các hiện tượng còn lại. Trường
hợp này khá đơn giản, việc tìm kiếm sẽ là truy nhập các đối tượng không gian chỉ
dựa trên thuộc tính xác định trước. Thí dụ yêu cầu tìm kiếm tất cả các huyện có số
người thật nghiệp vượt quá mức cho trước. Trong thực tế tìm kiếm loại này thường
phải được giới hạn bởi địa điểm. Chúng có thể được giới hạn bởi khoảng cận kề.
Thí dụ tìm các thành phố cách đường quốc lộ 500m.


15

Tìm những vùng được xác định bởi tổ hợp các hiện tượng. Một yếu tố thúc
đẩy phát triển GIS là nhu cầu phân tích dữ liệu. Mục đích của chúng là tìm kiếm các
vùng thỏa mãn điều kiện cho trước.Thí dụ các ứng dụng về sử dụng đất hoặc đặc

tính đất trồng. Tiến trình này được thực hiện nhờ phép phủ các bản đồ chuyên đề
biểu diễn từng chỉ báo quan tâm như loại thực vật, loại đất trồng, độ dốc...để điều
chỉnh kế hoạch trồng trọt. Ngày nay kỹ thuật này đã được tự động hóa nhờ công
nghệ GIS trên mô hình dữ liệu raster hay vectơ. Nói chung phân tích phủ hợp với hệ
thống lưu trữ dữ liệu theo tầng.[1]
1.4.4 Nội suy và mô hình hóa bề mặt
Nhu cầu thực tế đòi hỏi chức năng nội suy tăng lên khi dữ liệu đo đạc được
xem như các điểm mẫu bề mặt; nói cách khác là phải tính toán giá trị tại mọi điểm
trong không gian. Khi dữ liệu được nội suy từ các điểm mẫu thành lưới đều các
điểm thì kỹ thuật thường được sử dụng là ước lượng mỗi điểm (nút) lưới như tổng
trọng lượng của các điểm mẫu lân cận của điểm lưới đó.[1]
1.4.5 Phân tích đường đi và đường dẫn
Phân tích đường đi là việc tìm kiếm đường đi ngắn nhất, rẻ nhất giữa hai vị
trí. Giải pháp của vấn đề này hình thành nhờ sử dụng mô hình mạng hay mô hình
dữ liệu raster trên cơ sở tế bào lưới. Mô hình dữ liệu mạng được sử dụng để biểu
diễn tập xác định các đường dẫn như đường quốc lộ, sông ngòi. Sự chuyển động
thực hiện từ nút này đến nút khác hay từ tế bào này đến tế bào lân cận của mô hình
dữ liệu raster. Trong mạng giao thông thì đường đi còn liên quan đến tốc độ hạn
chế, chất lượng mặt đường... Trong mô hình địa hình tìm đường đi liên quan đến
loại mặt đất và hiện diện của chướng ngại vật như đầm lầy, ...[1]
1.4.6 Mô hình hóa tương tác không gian
Ngày nay GIS được sử dụng rộng rãi cho mục đích nhận ra các vùng tối ưu
để xây dựng các công trình công cộng như chợ, trạm cứu hỏa, cây ATM, trạm xe
buýt... Khi xác định được vị trí các điểm này kỹ thuật định vị được sử dụng để xác
định toàn bộ vị trí trên mạng giao thông sao cho phù hợp nhất.[1]


16

1.4.7 Đồ họa và tương tác

Tầm quan trọng bản chất không gian trong GIS là đặc tả truy vấn và báo cáo
kết quả được thực hiện hiệu quả là nhờ sử dụng bản đồ. Do vậy chức năng lập bản
đồ thường thấy trong GIS. Trong các hệ thống GIS đơn giản chỉ có các công cụ cơ
sở thì cũng có được bản đồ động và mềm dẻo hơn bản đồ giấy rất nhiều. Khi truy
vấn dữ liệu bản đồ trên hệ thống GIS người dùng sẽ có các đặc trưng trên màn hình
máy tính hay có các đường biên giới hạn kết quả không gian tìm kiếm trên chúng.
Kết quả truy vấn thu được bằng xen thêm các đặc trưng khác vào bản đồ đang hiển
thị hay phát sinh ra bản đồ hoàn toàn mới. Chúng còn có thể in thành bản đồ giấy
hoặc hiển thị bản đồ 3D từ các điểm quan sát khác nhau.[1]
Trong chương này đã trình bày những kiến thức tổng quan nhất về GIS từ đó
cho ta thấy lập bản đồ và phân tích địa lý không phải là kỹ thuật mới, nhưng GIS
thực thi các công việc này tốt hơn và nhanh hơn các phương pháp thủ công cũ.
Trước công nghệ GIS, chỉ có một số ít người có những kỹ năng cần thiết để sử dụng
thông tin địa lý giúp ích cho việc giải quyết vấn đề và đưa ra các quyết định. Khi
nói đến GIS, chúng ta cũng có thể nghĩ đến việc lưu trữ và truy vấn dữ liệu, đặc biệt
là dữ liệu không gian đồ sộ và CSDL không gian trong GIS chiếm vai trò trung
tâm. Việc phân tích một số cấu trúc dữ liệu trong GIS sẽ được trình bày rõ hơn
trong chương tiếp theo.


17

CHƯƠNG 2: MỘT SỐ CẤU TRÚC DỮ LIỆU SỬ DỤNG TRONG GIS
2.1 Vấn đề lưu trữ và chỉ mục dữ liệu địa lý
Chỉ mục CSDL là trình diễn thông tin đặc biệt về đối tượng để nâng cao hiệu
năng tìm kiếm. Tệp chỉ mục là tệp bổ trợ để nâng cao khả năng tìm kiếm. Mỗi bản
ghi trong tệp chỉ mục chỉ có 2 trường: giá trị khóa, địa chỉ của những trang trong tệp
dữ liệu, những bản ghi trong tệp chỉ mục thường có thứ tự, có thể sử dụng thứ tự
không gian và tổ chức cấu trúc dữ liệu để sử dụng tìm kiếm riêng. Một cấu trúc chỉ
mục không gian tổ chức những đối tượng với một tập những thùng (bucket) thông

thường những thùng này tương ứng với những trang trong bộ nhớ phụ (second
memory), mỗi thùng có một liên kết vùng, một phần của không gian chứa tất cả
những đối tượng lưu trữ trong thùng, những vùng thường là những hình chữ nhật
đối với những cấu trúc dữ liệu điểm, những vùng này thường rời rạc và chúng chia
cắt không gian và chính vì vậy mỗi điểm có liên quan chính xác đến một thùng đối
với một vài cấu trúc dữ liệu hình chữ nhật những vùng có thể chồng lên nhau.
Chỉ mục không gian được sử dụng bởi những cơ sở dữ liệu không gian để tối
ưu truy vấn không gian. Những phương pháp chỉ mục không gian phổ biến bao
gồm: cây tứ phân (Quadtree), Cây R (R tree), cây kd (k-d tree)...
Lợi ích cơ bản của chỉ mục không gian:
Chỉ mục làm tăng tốc độ tìm kiếm bản ghi dữ liệu trong CSDL. Cho khả
năng xâm nhập ngẫu nhiên thay cho trình tự. Về mặt logic, chỉ mục CSDL tương
tự chỉ mục trong quyển sách in. Cấu trúc dữ liệu không gian ngoài được thêm
vào hệ thống, cung cấp những thuộc tính không gian cây B (B tree) cho những
thuộc tính tuyến tính.
Những đối tượng không gian được ánh xạ vào không gian một chiều 1- D,
sử dụng một trật tự không gian (ví dụ: trật tự Z, trật tự Hilbert), vì vậy chúng
được lưu trữ trong một chỉ mục chuẩn 1-D như cây B (B tree). Dưới đây là Ví dụ
chỉ mục B tree (Balanced Tree) một chiều. Thay vì phải mất 8 lần tìm kiếm trong
dữ liệu không được chỉ mục khi tìm kiếm số 36, thì với chỉ mục dữ liệu thì chỉ
mất 5 lần tìm kiếm bằng cách sắp xếp dữ liệu thành 3 mức khác nhau, mỗi mức


18

chia thành các thùng. Mức 1 chứa giá trị nhỏ hơn hoặc lớn hơn 36, mức 2 chứa
giá trị nhỏ hơn hoặc lớn hơn 68, mức 3 chứa giá trị nhỏ hơn hoặc lớn hơn 72. Số
mức và số thùng đối với mỗi mức có thể tối ưu hóa đối với mỗi loại dữ liệu. [3]

Chỉ mục không gian giống như bất kỳ chỉ mục khác, cung cấp một cơ chế để

giới hạn việc tìm kiếm, nhưng trong trường hợp này cơ chế là dựa vào tiêu chuẩn
không gian như sự giao nhau và chứa đựng nhau. Một chỉ mục không gian cần:
- Tìm những đối tượng trong khoảng một không gian dữ liệu chỉ mục mà
nó tương tác với một điểm đã cho hoặc một vùng quan tâm (truy vấn vùng)
- Tìm những cặp đối tượng từ khoảng 2 không gian dữ liệu chỉ mục mà
chúng tương tác không gian với mỗi trong chúng (kết nối không gian).
Chỉ mục không gian được sử dụng bởi những cơ sở dữ liệu không gian để
tối ưu truy vấn không gian. Có nhiều cấu trúc dữ liệu khác nhau được sử dụng để
biểu diễn việc tách phân cấp vùng.
2.2 Cây k-d (k-d tree)
Cây k-d được sử dụng để lưu trữ dữ liệu điểm k-chiều không sử dụng nó để
lưu trữ dữ liệu vùng. Như vậy, cây 2-d (khi k=2) lưu trữ dữ liệu điểm 2-chiều, cây
3-d lưu trữ dữ liệu điểm 3-chiều...


19

2.2.1 Cấu trúc nút
Trong cây 2-d, mỗi nút có cấu trúc bản ghi nhất định với kiểu như sau:
INFO
XVAL
YVAL
LLINK
RLINK
nodetype = record INFO: infotype;
XVAL: real; YVAL: real;
LLINK: ↑ nodetype;
RLINK: ↑nodetype;
end
Trường INFO có thể có kiểu bất kỳ do người sử dụng định nghĩa và phụ

thuộc vào ứng dụng cụ thể. Thí dụ, nó có thể là trường xâu ký tự mô tả địa danh,
hay nó có thể là bản ghi bao gồm các trường name:string và population:integer...
Trường XVAL, YVAL biểu thị tọa độ điểm kết hợp với nút. Các trường
LLINK và RLINK trỏ đến hai cành. Giả sử T trỏ đến gốc của cây 2-d. Nếu N là nút
trong cây, thì mức của N được xác định qui nạp như sau:
level(N)=

0nếuNlàgốccủacây
level(P)+1nếuchacủaNlàP

Cây 2-d là cây nhị phân bất kỳ nếu thoả mãn điều kiện sau:
1. Nếu N là nút trong cây và level(N) là chẵn thì mỗi nút M trong cành rẽ
nhánh từ N.LLINK có tính chất M.XVAL < N.XVAL, mỗi nút P trong cành rẽ
nhánh từ N.RLINK có tính chất P.XVAL ≥ N.XVAL.
2. Nếu N là nút trong cây và level(N) là lẻ thì mỗi nút M trong cành rẽ nhánh
từ N.LLINK có tính chất M.YVAL < N.YVAL, mỗi nút P trong cành rẽ nhánh từ
N.RLINK có tính chất P.YVAL ≥ N.YVAL.
Thuật toán dựng cây k-d [2]
Algorithm BuildKdTree(P, depth)
1. If P chỉ chứa duy nhất 1 điểm
2. then return Một lá chứa điểm
3. else if depth là chẵn