Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
1
LỜI CẢM ƠN
Trong thời gian thực hiện đề tài khóa luận tốt nghiệp, dưới sự hướng dẫn tận
tình của giáo viên hướng dẫn và được phía nhà trường tạo điều kiện thuận lợi, tôi
đã có một quá trình nghiên cứu, tìm hiểu và học tập nghiêm túc để hoàn thành đề
tài. Kết quả thu được không chỉ do nỗ lực của cá nhân tôi mà còn có sự giúp đỡ
của quý thầy cô, gia đình và các bạn.
Tôi xin chân thành cảm ơn
Bán giám hiệu nhà trường, Ban chủ nhiệm khoa Công Nghệ Thông Tin –
Trường Đại học Công Nghệ đã quan tâm, tạo điều kiện giúp tôi hoàn
thành hoàn thành khóa luận tốt nghiệp.
Thầy Nguyễn Hải Châu: Thầy đã hướng dẫn, hỗ trợ tôi hoàn thành tốt đề
tài về phương pháp, lý luận và nội dung trong suốt thời gian thực hiện
khóa luận tốt nghiệp.
Gia đình đã tạo điều kiện học tập tốt nhất.
Các bạn đã giúp đỡ, trao đổi thông tin về đề tài trong quá trình thực hiện
khóa luận.
Trong quá trình thực hiện và trình bày khóa luận không thể tránh khỏi những
sai sót và hạn chế, do vậy tôi rất mong nhận được sự góp ý, nhận xét phê bình
của quý thầy cô và các bạn.
Kính chúc quý thầy cô và các bạn sức khỏe!
Người thực hiện đề tài
Mục đích nghiên cứu ............................................................................................ 9
4.
Đối tượng nghiên cứu ......................................................................................... 10
5.
Phạm vi nghiên cứu ............................................................................................ 10
B.
NỘI DUNG ............................................................................................................ 11
CHƯƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU KHÔNG GIAN....................... 11
1.
Khái niệm........................................................................................................... 11
1.1
Hệ thống cơ sở dữ liệu không gian............................................................... 11
1.2. Cơ sở dữ liệu không gian (Spatial Database) .............................................. 12
2.
Mô hình cơ sở dữ liệu không gian ................................................................... 16
3
1.6
Nối K vùng lân cận gần nhất........................................................................ 40
1.7 Truy vấn K- nối khoảng cách ......................................................................... 40
2
R – Tree.............................................................................................................. 42
2.1 Khái niệm.......................................................................................................... 43
2.2 Cấu trúc của một R-tree.................................................................................. 45
2.3 Thuật toán R-Tree ........................................................................................... 47
3
Các kỹ thuật tính toán xấp xỉ khoảng cách .................................................... 56
3.1
Thu nhỏ không gian tìm kiếm ...................................................................... 56
Xây dựng thuật toán xấp xỉ như một công cụ hạn chế những khó khăn phát
sinh đối với kích thước địa lý của đối tượng .......................................................... 68
4.
Tính toán độ chính xác về vị trí trên bản đồ và chênh lệch về khoảng cách
giữa các đối tượng trong truy vấn........................................................................... 70
CHƯƠNG 4 MỘT SỐ THUẬT TOÁN TÍNH KHOẢNG CÁCH TRONG KHÔNG
GIAN ĐỊA LÝ & ĐÁNH GIÁ HIỆU NĂNG.............................................................. 74
1.
Tính toán khoảng cách giữa các đối tượng địa lý theo công thức Haversine
74
1.1
Công thức Haversine..................................................................................... 74
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
4
Hướng phát triển ................................................................................................. 92
TÀI LIỆU THAM KHẢO............................................................................................ 93
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
5
MỤC LỤC BẢNG BIỂU
Hình 15: R-Tree và MBRs trong truy vấn ............................................................42
Hình 16: R-Tree và truy vấn trong hai cấu trúc MBR khác nhau.........................42
Hình 17: Ví dụ về R-Tree .....................................................................................44
Hình 18: Cây biểu diễn R-Tree.............................................................................47
Hình 19: Biểu diễn hai chiều của một R-Tree ......................................................47
Hình 20: Cấu trúc một R-Tree ..............................................................................48
Hình 21: Các quan hệ có thể có giữa các MBR (chứa trong, chồng lấn…) .........49
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
6
Hình 22: Trường hợp phân chia node...................................................................53
Hình 23: Phân chia entry thành các nhóm node mới ............................................54
Hình 24: Minh họa cấu trúc sản phẩm ArcGIS của ESRI ....................................66
Hình 25: Kiến trúc CSDL trên nền tảng Microsoft...............................................68
trong cơ sở dữ liệu không gian
2008
7
A. PHẦN MỞ ĐẦU
1. Giới thiệu
Trong vài năm trở lại đây, cùng với sự phát triển không ngừng của các kỹ
thuật công nghệ hiện đại, “kỷ nguyên số” đã được bắt đầu và ứng dụng trong
mọi lĩnh vực khoa học cũng như phục vụ nhu cầu sử dụng của con người. Nếu
như cách đây vài thập kỷ, câu chuyện con người có thể quan sát toàn cảnh trái
đất t
ừ trên cao xuống thông qua các thiết bị kỹ thuật như máy tính, tivi… tại
bất kỳ đâu và bất kỳ lúc nào vẫn là một viễn cảnh xa vời thì ngày nay điều này
đã trở nên quá đơn giản. Để có thể quan sát Trái đất từ mọi góc độ, một cá
nhân chỉ cần trang bị cho mình một máy tính nối mạng, và một phần mềm
hiển thị hình ảnh 3D như Google Earth hay truy cập vào các trang web bản đồ
trực tuyế
n sẵn có trên mạng Internet…
Như vậy, trong bối cảnh hiện tại, sự hiện thực hóa bản đồ số và đưa các kỹ
thuật lập bản đồ cũng như phân tích địa lý vào sử dụng rộng rãi với mục đích
dân sự cho tất cả các tổ chức, cá nhân có nhu cầu đang trở thành một ngành
kinh doanh nhiều lợi nhuận. Trong đó phải kể đến GIS – Hệ thống thông tin
địa lý – v
ới rất nhiều công cụ ứng dụng trợ giúp đắc lực cho quá trình xây
khoảng cách tốt nhất, đảm bảo yêu cầu dung hòa giữa độ phức tạp tính toán,
tốc độ thực thi và độ chính xác càng cao càng tốt.
Nhận thấy sự cần thiết trong ngành khoa học nghiên cứu lý thuyết v
ề các
thuật toán tính toán khoảng cách giữa các đối tượng địa lý trong thực tế và vai
trò to lớn của các bài toán tính toán gần đúng này, đề tài khóa luận tốt nghiệp
“
Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở
dữ liệu không gian” đã được xây dựng dựa trên quá trình nghiên cứu các
thành tựu khoa học trong lĩnh vực này và hệ thống lại một cách bài bản và chi
tiết.
Bố cục khóa luận
Khóa luận tốt nghiệp được trình bày với phần nội dung gồm 04 chương:
Chương 1: Tổng quan về cơ sở dữ liệu không gian.
Chương 2: Bài toán tính toán xấp xỉ với các truy vấn liên quan đến
khoảng cách trong cơ sở dữ liệu không gian.
Chương 3: Một số ứng dụng của bài toán tính toán xấp xỉ khoảng cách
trong thực tế.
Chương 4: Một số thuật toán tính toán khoảng cách trong không gian
địa lý và đánh giá hiệu năng.
2. Ý nghĩa khoa học và thực tiễn
Về khía cạnh nghiên cứu khoa học, các tập đoàn công nghệ trong lĩnh vực
GIS vẫn không ngừng nghiên cứu các phương pháp tối ưu hóa các sản phẩm
sử dụng thông tin địa lý trong các thiết bị hỗ trợ bản đồ, tìm đường và xác
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
thiết bị tìm vết và đường đi ngắn nhất tích hợp GPS (Hệ thống định vị toàn
cầu), ….
3. Mục đích nghiên cứu
Đề tài được thực hiện với mục
đích
Tìm hiểu khái niệm Cơ sở dữ liệu không gian, các công nghệ GIS đương
đại.
Nghiên cứu các kỹ thuật tính toán gần đúng về khoảng cách và các thuật
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
10
toán liên quan sử dụng trong các truy vấn trên CSDL không gian.
Các ứng dụng thiết thực của bài toán tính toán xấp xỉ trong công nghệ
thông tin địa lý.
Thử nghiệm một số truy vấn sử dụng kỹ thuật tính toán xấp xỉ trong một
số truy vấn tiêu biểu.
4. Đối tượng nghiên cứu
Mô hình, cấu trúc dữ liệu và cách xây dựng dữ liệu không gian và hệ
quản trị CSDL không gian, các phép toán thực thi.
Các kỹ thuật tính toán xấp xỉ khoảng cách trong không gian tìm kiếm và
các thuật toán.
Sản phẩm ứng dụng các kỹ thuật tính toán xấp xỉ đang được sử dụng
trong thực tế.
Thuật toán tính toán khoảng cách trên bề mặt cầu ứng dụng trong truy
CHƯƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU KHÔNG GIAN
1. Khái niệm
1.1 Hệ thống cơ sở dữ liệu không gian
Hệ thống cơ sở dữ liệu không gian – Spatial Database System – là hệ thống
quản lý dữ liệu liên quan đến các đối tượng không gian (không gian địa lý), ra
đời trước yêu cầu đặt ra trong thực tế là cần một hệ thống để lưu trữ các dữ
liệu trong không gian địa lý. Như vậy việc quản lý hệ CSDL không gian phụ
thu
ộc vào hai công nghệ: Một là phương tiện lưu trữ cố định và một là CSDL
không gian.
Các không gian:
Không gian hai chiều (2D): Các không gian hình học (Các bề mặt trên mặt
đất ở tỉ lệ co giãn lớn hoặc nhỏ)
Hệ thống thông tin địa lý (GIS – Geographic Information System)
Cơ sở dữ liệu đặt tại Luxembourg (LIS - Luxembourg Income Study)
lưu trữ dữ liệu về các quốc gia.
Urban planning – quy hoạch sử dụng không gian địa lý (sử dụng đất,
quy hoạch xây dựng đô thị….)
Không gian ba chiều (3D): Nghiên cứu vũ trụ, thiên văn học, nghiên cứu
bộ não con người trong y học, nghiên cứu cấu trúc phân tử trong ngành
sinh học.
Yêu cầu đặt ra với hệ thống này là khả năng quản lý và xử lý một khối
lượng thông tin khổng lồ của tập hợp các đối tượng địa lý đặt trong mối quan
hệ chặt chẽ với nhau.
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
tảng để dữ liệu không gian và lý lịch dữ liệu cùng với người sử dụng và các
công cụ có thể
kết nối trong mối quan hệ tương tác lẫn nhau với mục đích sử
dụng được các thông tin dữ liệu không gian một cách hiệu quả và linh hoạt.
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
13
1.2.1 Hạ tầng CSDL không gian
Công nghệ (technology)
Chính sách (policies)
Chuẩn (standards)
Nguồn nhân lực (human resources)
Qui trình (procedures)
Được xây dựng để đáp ứng yêu cầu thu nhận, xử lý, lưu trữ, phân phối và
nâng cao tính hữu dụng của dữ liệu địa lý, làm cơ sở cho việc sản xuất và chia
sẻ dữ liệu địa lý giữa các cơ quan, đơn vị,…
VD:
Cơ sở hạ tầng dữ liệu không gian của một thành phố là một thành phần
trong Cơ sở hạ tầng thông tin quốc gia (siêu xa lộ thông tin) nhằm cung cấp
những thông tin thiết thực cho mọi người.
Các chức năng của quản lý cơ sở dữ liệu
Cho phép giảm thiểu sự trùng lặp dữ liệu nhằm tiết kiệm chi phí, sẵn
sàng trợ giúp ra quyết định trên một vùng địa lý dựa trên dữ liệu chính
xác và hiện thời (cập nhập dữ liệu), người sử dụng dễ dàng biết được tỉ
sở hạ tầng trong các lĩnh vực khác: bưu điện, điện
thọai, đường giao thông,…như vậy người dùng khi có nhu cầu sẽ tham gia kết
nối vào cơ sở hạ tầng để sử dụng và đóng góp các dữ liệu, thông tin về GIS.
Đây là một dự án lớn có nền tảng lý luận và cơ sở thực tiễn cao, được phát
triển theo cách thức: “Phát triển trước, xây dựng đặc tả
sau”. Có nghĩa là: Để
giải quyết 1 vấn đề, các tổ chức nghiên cứu hướng tới nhiều giải pháp, sau
nhiều năm thử nghiệm sẽ đúc kết thành đặc tả (hay chuẩn mở) công bố cho
cộng đồng. Đối với Việt Nam và các nước đang phát triển thì thời điểm hiện
nay là cơ hội lớn để chúng ta tiếp cận những tinh hoa từ các tổ chức này để
xây dựng những hệ thống GIS tương tự (đa mục tiêu, đa thành viên).
Trên cơ sở đó, Việt Nam cần tiến hành xây dựng cơ sở hạ tầng dữ liệu
không gian cho mình với các tầm nhìn đều hướng đến một nền tảng để đưa dữ
liệu không gian địa lý đến tay người sử dụng một cách đơn giản, dễ dàng và
minh bạch.
Khảo sát có một số tổ
chức đã ứng dụng WebGis để xây dựng bản đồ trực
tuyến
Trang web của Nhà xuất bản bản đồ - Bộ Tài nguyên và môi trường
/>
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
Các bảng dữ liệu: Là thành phần quan trọng của cơ sở dữ liệu không
gian, được liên kết với các thành phần đồ họa với nhiều kiểu liên kết khác
nhau.
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
16
2. Mô hình cơ sở dữ liệu không gian
Trong những năm gần đây, đã có rất nhiều nghiên cứu đang được triển
khai về vấn đề quản lý dữ liệu không gian. Cách phương pháp tiếp cận ban
đầu trong lĩnh vực GIS đã gần như làm cạn kiệt những nỗ lực của các nhà
khoa học trong việc tìm kiếm hình thức biểu diễn hình học chính xác của dữ
liệu không gian và việc b
ổ sung những phép toán mới giữa các đối tượng
không gian. Sau đó, chỉ có một cải tiến thô sơ là việc kết hợp dữ liệu không
gian với dữ liệu thông thường. Và kết quả là việc quản lý dữ liệu địa lý phải
chia thành 2 quá trình xử lý riêng biệt nhau: một là cho dữ liệu không gian và
một là để xây dựng các thuộc tính cho dữ liệu thông thường và sự kết hợp của
chúng với dữ liệu không gian. N
ỗ lực để định nghĩa một ngôn ngữ thông dụng
và khả dụng để đơn giản thao tác xử lý các truy vấn hầu như không mang lại
kết quả, và do đó quá nhiều chương trình bắt buộc phải sử dụng đến. Kết quả
là việc xử lý dữ liệu không gian thiếu đi những giải pháp hình thức cơ bản.
Theo một khía cạnh khác, năng lực xử lý của dữ
liệu thông thường chỉ có thể
các đối tượng đồ hoạ ngay trong cơ sở dữ liệu, được gọi là topology (tương
quan không gian) - Phương thức thể hiện các ràng buộc đối với các đối tượng
đồ hoạ ngay trong cơ sở dữ liệu. Đặc điểm chung của một số mô hình CSDL không gian:
Hỗ trợ tập hợp các kiểu dữ liệu đã định dạng sẵn: Tập các điểm, tập các
bề mặt…
Có thể sử dụng một hoặc hai kiểu cấu trúc dữ liệu phức tạp để lưu lại
các dữ liệu không gian, với việc sử dụng hai kiểu cấu trúc cùng một lúc
tức là một để ghi nhận dữ liệu không gian và một để ghi nhận dữ liệu
thông thường.
Định nghĩa được các phép toán áp dụng với một kiểu dữ liệu không
gian riêng biệt bất kỳ.
2.1 Xây dựng mô hình CSDL không gian
Xây dựng mô hình các đối tượng riêng lẻ.
Xây dựng mô hình cho một tập hợp các đối tượng có liên quan đến nhau
trong không gian địa lý.
Việc vận dụng dữ liệu mật
độ cao hoặc dữ liệu không gian để lưu trữ và
phục hồi trong cơ sở dữ liệu đa phương tiện là một điều rất quan trọng.
Dữ liệu không gian bao gồm các điểm, đường, hình chữ nhật, đa giác, bề
mặt hay các đối tượng mật độ cao bao gồm cả thời gian. Các phương thức
đánh chỉ mục cung cấp đường dẫn đến dữ li
ệu hướng không gian được gọi là
các phương thức truy nhập không gian (Spatial Access Methods – SAM). Đến
nay đã có rất nhều SAM được giới thiệu bao gồm các grid file
[1]
, K-D-B-tree
[2]
khoảng cách giữa chúng. Bởi vậy một hệ thống đa phương tiện cần phải có
nhiều phương thức truy cập không gian để xử lý một truy vấn.
Trong quá khứ đã có một số nhà nghiên cứu đề xuất các phép toán ghép
nối không gian cho các tập dữ liệu không gian khác nhau. Tất c
ả các phương
pháp này đề đòi hỏi các cặp SAM có cùng một kiểu cấu trúc.
Các đặc tính cơ bản của phép truy nhập không gian.
Cấu trúc dữ liệu không gian
CSDL không gian bao gồm các đối tượng không gian như điểm, đường,
vùng, hình chữ nhật, bề mặt, hình khối và thậm chí là các dữ liệu mật độ cao
trong đó gồm cả thời gian. Một ví dụ của CSDL không gian là các thành
phố, những con sông, đường xá, quốc gia, bang, các dãy núi, các thành phần
trong một hệ thống CAD
[9]
(Thiết kế sử dụng sự trợ giúp của máy tính),…Ví
dụ về các thuộc tính của dữ liệu không gian có thể có là lưu vực của một con
sông, hay biên giới của một quốc gia…Thông thường các thuộc tính còn có
thể gắn thêm các các thuộc tính thông tin dạng phi không gian (non-spatial)
như độ cao, tên thành phố,…với CSDL không gian. Các cơ sở dữ liệu không
gian thuận tiện cho việc lưu trữ và đạt hiệu quả tốt cho quá trình xử lý các
thông tin dạng spatial
[10]
và non-spatial
[11]
một cách lý tưởng mà không cần
thiết phải quan tâm đến các mối liên hệ khác. Vì thế các sơ sở dữ liệu sẽ
nâng cao khả năng đáp ứng của các ứng dụng kiểm soát môi trường, khoảng
không, phát triển đô thị, quản lý nguồn lực, và trong các hệ thống GIS
[Buchmann et al. 1990; Günther and Schek 1991] [].
Phương pháp lưu trữ, quản lý và biểu diễn dữ liệu không gian
vùng RiverSide”. Yêu c
ầu này đòi hỏi phải trích xuất các bản ghi có trường
“region name” mang giá trị là “trường đại học vùng RiverSide” và xây dựng
một bản đồ A. Kế tiếp, thực hiện phép giao giữa A với bản đồ đường đi B
tạo được bản đồ mới C có các con đường được chọn lựa. Bây giờ tạo một
mối liên kết mới chỉ gồm một thuộc tính là các tên đường hợp lệ từ các
đườ
ng trong bản đồ C. Tất nhiên là còn có các hướng tiếp cận khác trả lời
câu truy vấn trên. Hiệu quả của chúng phụ thuộc vào tính tự nhiên và các
tính chất của dữ liệu.
Khái quát các khái niệm dữ liệu cơ sở trong CSDL không gian
Trong phần dưới đây, đề tài sẽ trình bày một cách khái quát các khái niệm
dữ liệu cơ sở trong CSDL không gian như vùng, điểm, chữ nhật, và đường.
Để biết thêm các thông tin chi tiết về các thành phần này, xin tham khảo thêm
trong [Samet 1990a; Samet 1990b].
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
20
Dữ liệu vùng - Region Data
Một region có thể được biểu diễn bằng đường biên hoặc nội dung bên
trong của chính nó. Trong phần này, region được hiểu theo cách biểu diễn
nội tại của nó. Một cách biểu diễn thông dụng nhất của region là mảng hình
ảnh. Trong trường hợp này, ta có một tập các phần tử ảnh (gọi là các pixel).
Khi số lượng các phần tử trong mảng quá lớn, phải tiến hành động thái là
tắc đệ quy hay còn gọi là các phương pháp chia để trị).
Dữ liệu điểm - Point Data
Dữ liệu điểm đa chiều có thể được biểu diễn dưới rất nhiều hình thức
khác nhau. Sự lựa chọn sau cùng cho một tác vụ cụ thể sẽ bị ảnh hưởng bởi
kiểu operation sẽ được thực hiện trên dữ liệu. Phần này đề cập chủ
yếu đến
kiểu biểu diễn PR quadtree (P: Point và R: Region) là phương thức phân ly
chủ đạo. Đây là sự lắp ghép giữa region quadtree và point data, và PR
quadtree được tổ chức tương tự như region quadtree. Chỉ có một sự khác
biệt đó là các nút lá hoặc là rỗng (ở đây biểu diễn bằng màu TRẮNG), hoặc
chứa dữ liệu điểm (màu ĐEN) và các giá trị tương ứng của chúng.
Hình vẽ sau là một PR quadtree tương ứ
ng với một số lượng nhất định
point data: Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
xác định khuôn
dạng của các liệt kê các cặp giá trị x và y tương xứng với điểm bắt đầu và
kết thúc của chúng. Các véc-tơ thường được sắp xếp theo liên kết của chúng.
Một trong những cách biểu diễn thông dụng nhất là chain code
[13]
[Freeman
1974].
Dữ liệu không gian - Spatial (High-dimentional) Data
Rất nhiều các cấu trúc SAM (Spatial Access methods) thành công dựa
trên nguồn gốc của sự phân ly không gian có thứ bậc. Ý tưởng ở đây là đánh
chỉ mục một cách liên tục các vùng không gian, như vậy việc tìm kiếm có
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
2008
23
thể được xuất phát ở mức cao hướng về những vùng không gian thích hợp.
Một cách thức phổ biến và khả quan để tổ chức và truy cập các đối tượng đa
chiều là sử dụng R-tree hoặc các biến thể của nó bởi vì trong R-tree, không
gian dữ liệu được phân ly liên tiếp nhau thành các rectangle, còn gọi là
hyper-rectangle.
Với hệ thống thông tin địa lý - GIS
Hệ thống thông tin địa lý làm việc với hai dạng mô hình dữ liệu địa lý
khác nhau về cơ bản - mô hình vector và mô hình raster.
9 Trong mô hình vector, thông tin về điểm, đường và vùng được mã hoá và
lưu dưới dạng tập hợp các toạ độ x,y. Vị trí của đối tượng điểm, như lỗ
24
vị trí của nó trên không gian bản đồ chứ không thể hiện phạm vi hay tỉ lệ kích
thước tương ứng của đối tượng.
Đường thẳng, đoạn thẳng:
Dòng sông
Đường dây
Đường giao thông
Hình 4: Biểu diễn dạng đường
Kí hiệu hình học của đối tượng kéo dài trong không gian hoặc kết nối các
không gian địa lý.
Vùng miền, lãnh thổ: Diễn tả phạm vi và khu vực của đối tượng
Rừng
Hồ ao
Thành phố
Hình 5: Biểu diễn dạng khu vực
2.1.2 Xây dựng mô hình cho một tập hợp các đối tượng có liên quan trong
không gian địa lý
Ranh giới phân chia giữa các đối tượng
Qui hoạch đất
Phân chia quận huyện
Sở hữu đất
Không gian các điểm Hình 6: Biểu diễn tập đối tượng trong khu vực
Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách
trong cơ sở dữ liệu không gian
m mới trong giới
hạn các phép toán hình học.
Có 2 cách tiếp cận:
Simplicial Complexes – Tổ hợp đơn giản (từ combinatorial topology –
tổ hợp tương quan không gian)
Realms
2.2.1 Simplicial Complexes
Định nghĩa: Simplicial Complexes – Tổ hợp đơn giản là một tập hữu hạn các
đỉnh (simplices) để giao điểm các đoạn thẳng nối giữa chúng tạo thành các bề
Copyright: Tài liệu đại học ©