Khóa luận Phát triển hệ thống hỗ trợ tìm đường trên các thiết bị di động có GPS

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Nguyễn Văn Bách

Phát triển hệ thống hỗ trợ tìm đường trên các

thiết bị di động có GPS

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ thông tin

HÀ NỘIꢀ2010

i

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Nguyễn Văn Bách

Phát triển hệ thống hỗ trợ tìm đường trên các thiết bị

di động có GPS

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công Nghệ Thông Tin

Cán bộ hướng dẫn: TS. Nguyễn Ngọc Hóa

HÀ NỘI ꢀ 2010

ii

Lời cảm ơn

Trước tiên, tôi xin bày tỏ lòng cảm ơn chân thành đến TS.Nguyễn Ngọc Hóa,

người đã hết lòng chỉ bảo, hướng dẫn, cho tôi các phương pháp tiếp cận vấn đề, giúp

tôi giải đáp những thắc mắc, giải quyết các khó khăn mắc phải để có thể hoàn thành

được khóa luận này.

Tôi cũng xin chân thành cảm ơn các thầy cô ở khoa Công Nghệ Thông Tin đã hết

lòng truyền đạt cho tôi những kiến thức nền tảng về CNTT, giúp tôi có đủ kiến thức để

tiếp cận, hoàn thành được khóa luận này. Bên cạnh đó tôi cũng vin gửi lời cảm ơn đến

sự sự giúp đở nhiệt tình của nhà trường tạo điều kiện tốt nhất cho tôi để hoàn thành

khóa luận này.

Tôi xin gửi lời cảm ơn sâu sắc đến những người thân trong gia đình, họ đã động

viên rất nhiều về mặt tinh thần để tôi có đủ nghị lực để hoàn thành khóa luận này. Tôi

cũng xin chân thành cảm ơn bạn bè tôi, những đã luôn luôn bên cạnh, động viên, tạo

mọi điều kiện thuận lợi nhất cho tôi trong quá trình hoàn thành khóa luận.

Hà Nội, tháng 5 năm 2010

Sinh viên

Nguyễn Văn Bách

iii

TÓM TẮT KHÓA LUẬN

Khóa luận này trình bày những hiểu biết cơ bản về một hệ thống thông tin địa lý

(GIS), cũng như các khái niệm liên quan. Qua việc xem xét một số hệ thống GIS tiêu

biểu, để có thể hình dung được cách thức lưu trữ, quản lý dữ liệu trong một dữ liệu

không gian, nhằm phục vụ hiệu quả cho việc quản lý dữ liệu địa lý. Khóa luận cũng

trình bày chi tiết về cấu trúc đánh chỉ số Rꢀtree – một cấu trúc được dùng phổ biến cho

các CSDL không gian. Một số phương pháp xử lý truy vấn trong CSDL không gian

cũng được đưa ra ở mức tìm hiểu sơ qua.

Phần cuối của khóa luận trình bày về việc xây dựng ứng dụng bản đồ trên thiết bị

di động hổ trợ GPS. Bằng việc sử dụng GoogleMaps để cung cấp các chức năng GIS

cơ bản cho người dùng, như hiển thị bản đồ, hướng dẫn lộ trình, tìm lộ trình theo vị trí

hiện tại, điểm đầu điểm cuối.

iv

DANH MỤC TỪ VIÊT TẮT

Từ viết tắt

GIS

Tiếng Anh

Tiếng Việt

Geographic informations

system

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

OGC

Open Geospatial

Consortium

ESRI

Environmental Systems

Research Institute

GRASS

Geographic Resources

Analysis Support System

CSDL

NN

Cơ sở dữ liệu

Nearest Neighbor

Hàng xóm gần nhất

OR

Obstacle range

ONN

ODJ

Obstacle nearest neighbour

Ostacle eꢀdistance join

v

MỤC LỤC

Mở đầu............................................................................................................... 1

CHƯƠNG 1. TỔNG QUAN VỀ HỆ THỐNG THÔNG TIN ĐỊA LÝ ............... 2

1.1. Khái niệm về hệ thống thông tin địa lý .............................................................2

1.2. Lợi ích và hạn chế của việc sử dụng GIS ..........................................................3

1.3. OGC – OPENGIS.............................................................................................3

1.4. Khái niệm chung về bản đồ địa lý.....................................................................4

1.5. Tìm hiểu một số hệ thống GIS tiêu biểu............................................................5

1.5.1. MapInfo.....................................................................................................5

1.5.2. ArcViewcủa ESRI .....................................................................................5

1.6. MobileGIS........................................................................................................6

1.6.1. Hệ thống WebGIS .....................................................................................7

CHƯƠNG 2. TỔ CHỨC DỮ LIỆU TRONG GIS.............................................. 9

2.1. Tổ chức dữ liệu trong hệ thống thông tin địa lý.................................................9

2.1.1. Mô hình dữ liệu Vector............................................................................10

2.1.2. Hệ thống Raster.......................................................................................11

2.1.3. Mô hình TIN............................................................................................13

2.2. Điểm qua cách tổ chức dữ liệu trong một số hệ thống GIS thông dụng. ..........13

2.2.1. Tổ chức dữ liệu trong MapInfo................................................................13

2.2.2. Tổ chức dữ liệu trong ArcGIS của ESRI..................................................14

2.2.3. Tổ chức dữ liệu trong GRASS .................................................................14

2.3. Tìm hiểu cấu trúc lưu trữ của Shapefile ..........................................................15

CHƯƠNG 3. XỬ LÝ TRUY VẤN KHÔNG GIAN......................................... 20

3.1. Cấu trúc RꢀTree index.....................................................................................20

3.1.1. Cấu trúc của Rꢀtree..................................................................................20

3.1.2. Tìm kiếm và cập nhật trong Rꢀtree...........................................................21

3.1.3. Cập nhật và các thao tác khác ..................................................................24

3.2. Tìm hiểu một số thuật toán xử lý truy vấn trong CSDL không gian ................26

3.2.1. Xử lý truy vấn trong không gian Oꢀclit ....................................................27

3.2.2. Xử lý truy vấn trong mạng không gian.....................................................28

3.2.3. Tìm đường đi trong có không gian có chướng ngại vật ............................28

3.3. Tìm hiểu về PostGIS.......................................................................................32

3.3.1. Giới thiệu.................................................................................................32

3.3.2. Sử dụng các chuẩn OpenGIS ...................................................................32

vi

3.3.3. Import dữ liệu GIS...................................................................................32

3.3.4. Xuất bản dữ liệu GIS ...............................................................................32

3.3.5. Tạo indexs ...............................................................................................33

3.3.6. Một số truy vấn spatial SQL đơn giản......................................................33

CHƯƠNG 4. XÂY DỰNG ỨNG DỤNG......................................................... 36

Dựa trên những kiến thức thu được, trong chương này, tôi sẽ trình bày về hệ thống

dẫn đường (navigator) thử nghiệm với mục đích minh họa những hiểu biết về hệ

thống thông tin địa lý và các vấn đề xử lý truy vấn không gian..............................36

4.1. Một số ứng dụng dẫn đường phổ biến.............................................................36

4.1.1. Việt map..................................................................................................36

4.1.2. Pguider ....................................................................................................37

4.1.3. GoogleMaps cho mobile..........................................................................37

4.2. Các chức năng của chương trình.....................................................................38

4.3. Mô hình đề xuất..............................................................................................39

4.4. Lựa chọn ngôn ngữ.........................................................................................41

4.5. Tìm hiểu cơ chế hoạt động của hệ thống GPS.................................................42

4.5.1. Đo khoảng cách từ máy thu đến các vệ tinh .............................................43

4.5.2. Xác định vị trí hiện tại của các vệ tinh .....................................................44

4.6. Thử nghiệm ứng dụng.....................................................................................44

4.6.1. Các lớp chính của chương trình ...............................................................44

4.6.2. Screenshot của chương trình....................................................................44

4.7. Nhận xét .........................................................................................................49

CHƯƠNG 5. KẾT LUẬN................................................................................ 50

5.1. Kết quả đạt được.............................................................................................50

5.2. Hạn chế ..........................................................................................................50

5.3. Hướng phát triển.............................................................................................50

vii

Mở đầu

Ngày nay với sự phát triển mạnh mẽ của CNTT, các ứng dụng của CNTT đã

được đưa vào hầu hết các lĩnh vực của cuộc sống. Với sự trợ giúp của máy tính, các

công việc phức tạp được xử lý nhanh chóng và chính xác. Cùng với sự phát triển của

Internet, việc chia sẽ thông tin giữa các cá nhân, tổ chức hay làm việc qua mạng đã trở

nên dễ dàng và hiệu quả. Hệ thống thông tin địa lý (Geographic Information System –

GIS) là một nhánh của CNTT đã trở thành một công cụ trợ giúp quyết định rất tốt cho

các tổ chức, chính phủ trong các lĩnh vực liên quan đến thông tin địa lý.

Để hoàn thành khóa học của mình, tôi nhận thấy GIS là một hệ thống thông tin

rất thú vị, việc tìm hiểu về GIS sẽ giúp tôi có một cái nhìn sâu sắc hơn về một hệ thống

thông tin, quản trị CSDL. Giúp tôi có được cái nhìn ban đầu về phương pháp tiếp cận

để xây dựng, quản lý hiệu quả một hệ thống CSDL mô phỏng thực tế ꢀ hệ thống CSDL

địa lý. Với động lực đó, khóa luận tốt nghiệp của tôi hướng đến mục tiêu nghiên cứu,

tìm hiểu về hệ thống thông tin địa lý nói chung, từ đó ứng dụng trong bài toán phát

triển hệ thống dẫn đường dựa trên các thiết bị di động có hỗ trợ định vị vệ tinh (GPS).

1

CHƯƠNG 1. TỔNG QUAN VỀ HỆ THỐNG THÔNG TIN ĐỊA LÝ

1.1. Khái niệm về hệ thống thông tin địa lý

Hệ thống thông tin địa lý (Geographic Information System – gọi tắt là GIS) là

một nhánh của công nghệ thông tin được hình thành vào những năm 1960 và phát triển

rất rộng rãi trong 10 năm lại đây. GIS ngày nay là công cụ trợ giúp quyết định trong

nhiều hoạt động kinh tế ꢀ xã hội, quốc phòng của nhiều quốc gia trên thế giới. GIS có

khả năng cung cấp cho các cơ quan chính phủ, các nhà quản lý, các doanh nghiệp, các

cá nhân … đá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 của các vùng địa lý 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 các thông tin được gắn liền với một nền hình học (bản đồ) nhất quán

trên cơ sở tọa độ của các dữ liệu đầu vào.

Có nhiều cách tiếp cận khác nhau khi định nghĩa GIS. Nếu xét dưới góc độ hệ

thống, thì GIS có thể được hiểu như một hệ thống gồm 5 thành phầm cơ bản: con

người – chuyên viên, thiết bị ꢀ phần cứng, phần mềm, số liệu ꢀ cơ sở dử liệu và các

quy trình kiến thức chuyên gia – nơi tập hợp các quy phạm, tiêu chuẩn, định hướng,

chủ trương ứng dụng của nhà quản lý, các kiến thức chuyên ngành và các kiến thức về

CNTT.

Hình 1: Các thành phần thiết yếu cho công nghệ GIS

Theo cách tiếp cận truyền thống, GIS là một công cụ máy tính để lập bản đồ và

phân tích các sự vật, hiện tượng thực trên trái đất. Công nghệ GIS kết hợp các thao tác

CSDL thông thường kết hợp với cho phép phân tích thống kê, phân tích không gian.

Những khả năng này phân biệt GIS với các hệ thống thông tin khác và khiến GIS có

2

phạm vi ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau (phân tích các sự kiện, dự

đoán tác động và hoạch định chiến lược).

1.2. Lợi ích và hạn chế của việc sử dụng GIS

GIS là một công nghệ ứng dụng tiến bộ của khoa học máy tính, do đó việc sử

dụng GIS trong các mục tiêu nghiên cứu so với các phương tiện cổ điển có thể mang

lại hiệu quả cao.

ꢀ Tiết kiệm thời gian và chi phí trong việc lưu trữ số liệu.

ꢀ Có thể thu thập số liệu với số lượng lớn.

ꢀ Cập nhật số liệu lưu trữ dễ dàng.

ꢀ Chất lượng số liệu được bảo đảm (quản lý, xử lý, sửa chữa).

ꢀ Dễ dàng truy cập, phân tích số liệu từ nhiều nguồn và nhiều loại khác

nhau.

ꢀ Tổng hợp số liệu nhanh chóng và dễ dàng.

Bên cạnh những thuận lợi khi sử dụng GIS thì quá trình sử dụng kỹ thuật GIS

cũng xuất hiện một số trở ngại, và những trở ngại này có ảnh hưởng đặc biệt quan

trọng, do đó cần cân nhắc kỹ càng trước khi quyết định phát triển GIS.

ꢀ Chi phí và những vấn đề kỹ thuật đòi hỏi trong việc chuẩn bị lại các số

liệu thô hiện có, để chuyển từ bản đồ dạng thô (trên giấy) sang dạng số trên

máy tính.

ꢀ Đòi hỏi nhiều kiến thức của các kỹ thuật cơ bản về máy tính, và yêu cầu

lớn về nguồn tài chính ban đầu.

ꢀ Chi phí mua sắm, lắp đặt thiết bị và phần mềm GIS khá cao.

ꢀ Trong một số lĩnh vực ứng dụng, hiệu quả tài chính thấp.

1.3. OGC – OPENGIS

OGC – Open Geospatial Consortium là một tổ chức phi lợi nhuận, quốc tế, tự

nguyện đang dẫn đầu trong việc đặt ra các tiêu chuẩn về không gian địa lý và các dịch

vụ dựa trên vị trí.

OpenGIS standard and Specifications là các tài liệu kỹ thuật đặc tả các giao diện

hoặc bảng mã được dùng cho các nhà phát triển phần mềm để đưa các giao diện hoặc

bản mã này vào sản phẩm hay dịch vụ của họ. Các đặc tả này cung cấp cho các nhà

phát triển một khuôn mẫu giao diện chung, đầy đủ để có thể xây dựng các phần mềm

hoạt động chung được với các phần mềm dạng OpenGIS khác.

3

Ưu điểm của OpenGIS Specification thể hiện qua các mặt sau:

ꢀ Đối với người phát triển ứng dụng có thể dễ dàng và linh hoạt trong việc

thiết kế các phần mềm truy cập đến cơ sở dữ liệu địa lý, sử dụng chung những

nguồn tài nguyên địa lý. Từ đó có thể chọn môi trường phát triển hoặc cung cấp

những nền tảng ứng dụng đa dạng mà vẫn có thể sử dụng lại.

ꢀ Đối với các nhà quản lý thông tin: Giúp cho việc sử dụng hoặc phân phối

cơ sở dữ liệu địa lý, cung cấp những khả năng xử lý địa lý tới khách hàng, tích

hợp dữ liệu địa lý và xử lý vào một kiến trúc tính toán liên hợp.

ꢀ Đối với người dùng cuối là những người hưởng lợi tối ưu, họ nhận được

sự truy nhập một cách nhanh chóng đến một hệ thống thông tin rộng lớn với

nhiều ứng dụng.

Với việc ra đời của OGC ꢀ OpenGIS giúp xây dựng nên một ứng dụng có thể

tổng hợp các thông tin từ nhiều hệ thống thông tin địa lý khác nhau. Ví dụ: cổng thông

tin địa lý (GeoPortal), GeoPortal cho phép tổng hợp các thông tin từ các hệ thống địa

lý khác nhau thông qua dịch vụ Web.

1.4. Khái niệm chung về bản đồ địa lý

Định nghĩa: Bản đồ địa lý là sự biểu thị thu nhỏ qui ước của bề mặt trái đất lên

mặt phẳng, xây dựng trên cơ sở toán học, sử dụng các ký hiệu quy ước để phản ánh sự

phân bố, trạng thái và mối quan hệ tương quan của các hiện tượng thiên nhiên và xã

hội.

Trên bản đồ người ta thể hiện các đối tượng và hiện tượng có trên mặt đất trong

thiên nhiên, xã hội và các lĩnh vực hoạt động của con người. Các yếu tố nội dung của

bản đồ là:

ꢀ Thủy hệ

ꢀ Địa hình bề mặt.

ꢀ Dân cư

ꢀ Đường giao thông

ꢀ Ranh giới hành chính – chính trị

ꢀ Lớp phủ thổ nhưỡng – thực vật

ꢀ Các đối tượng kinh tế xã hội

Để phục vụ được công tác địa lý, GIS phải lưu trữ đầy đủ các thông tin địa lý này

của bản đồ, cung cấp các chức năng giúp quản lý, phân tích và hiển thị thông tin địa lý.

Các tri thức này được thể hiện qua các tập thông tin:

4

ꢀ Các bản đồ: giao diện trực tuyến với dữ liệu địa lý để tra cứu, trình bày

kết quả và sử dụng như là một nền giao thức với thế giới thực.

ꢀ Các thông tin địa lý: chứa trong các tệp tin trong cơ sở dữ liệu gồm các

yêu tố cơ bản, mạng lưới, topology, địa hình, thuộc tính, …

ꢀ Các mô hình xử lý: tập hợp các quy trình xử lý để phân tích tự động.

ꢀ Các mô hình dữ liệu: GIS cung cấp các công cụ mạnh hơn là một CSDL

thông thường, bao gồm các quy tắc và sự toàn vẹn dữ liệu giống như các hệ

thống thông tin khác.

ꢀ Siêu dữ liệu (metadata) hay tài liệu mô tả dữ liệu, cho phép người sử

dụng tổ chức, tìm hiểu và truy nhập được tới tri thức địa lý.

1.5. Tìm hiểu một số hệ thống GIS tiêu biểu

1.5.1. MapInfo

MapInfo là công cụ khá hữu hiệu để tạo ra và quản lý một CSDL địa lý trên máy

tính cá nhân, là một phần mềm tương đối gọn nhẹ và dễ sử dụng. Đặc biệt, dùng cho

mục đích giảng dạy và thành lập các bản đồ chuyên đề phân tích trong địa lý.

MapBasic là 1 ngôn ngữ lập trình trong môi trường MapInfo cho phép phát triển

các ứng dụng GIS. Nó tạo ra các hệ thống giao diện người dùng thuận lợi và nhanh

chóng như tạo thanh menu mới, hộp thoại điều khiển như ý muốn cho phép tiết kiệm

thời gian và tiện lợi cho việc triển khai ứng dụng.

MapBasic cũng cung cấp công cụ xử lý dữ liệu, đáp ứng các yêu cầu đa dạng về

dữ liệu. Nó cho phép truy vấn CSDL, lựa chọn và cập nhật dữ liệu bẳng các câu lệnh

theo cú pháp SQL. Hiển thị kết quả truy vấn theo khuôn dạng mong muốn.

Ngoài ra, MapBasic cho phép xây dựng chương trình có cấu trúc mở vì nó có khả

năng liên kết với các ứng dụng khác. Chương trình MapBasic có thể gọi các thủ tục

trong các thư viện các tệp liên kết động của Windows DLL hoặc sử dụng dữ liệu

chuyển đổi động DDE (Dynamic Data Exchange) để lin kết với các phần mềm khác.

1.5.2. ArcViewcủa ESRI

ArcView là phần mềm thương mại của ESRI về hệ thống thông tin địa lí (GIS).

Các chức năng cơ bản của ArcView GIS bao gồm:

ꢀ Chương trình ArcView GIS chạy trên nền Windows

ꢀ Hiển thị các lớp bản đồ dạng vector

ꢀ Tạo và thay đổi cơ sở dữ liệu của các đối tượng địa lí trong bản đồ

5

ꢀ Tạo các biểu đồ đơn giản dựa trên thuộc tính của các đối tượng trên bản

ꢀ Chuẩn bị các bản in ra giấy

đồ

Hình – ArcView chạy trên Windows

Ngoài ra ArcView GIS còn hỗ trợ chức năng lập trình thông qua ngôn ngữ lập

trình Avenue, được tích hợp sẵn trong phần mềm. ArcView GIS cũng có khả năng cho

phép lập trình liên kết với các ngôn ngữ khác như VB, VC++.

ArcView GIS thích hợp cho những ứng dụng GIS nhỏ, đơn người dùng, thích

hợp cho việc nghiên cứu về GIS và giảng dạy trong các trường Đại học, Cao đẳng.

ArcView cung cấp ngôn ngữ kịch bản riêng của mình.

Các kho tài nguyên scripts mẫu do ESRI cung cấp với ArcView. Nhiều scripts có

thể tải về miễn phí từ trang web ArcScripts của ESRI và đưa vào chương trình.

1.6. MobileGIS

Mobile GIS là phần mở rộng của hệ thông tin địa

lý (GIS), cho phép các ứng dụng GIS có thể hoạt động

trên thực địa thay vì hoạt động trong phòng. Mobile

GIS cho phép người sử dụng ở bên ngoài thực địa thu

thập, lưu trữ, cập nhật, thao tác, phân tích, và hiển thị

các thông tin địa lý.

6

Mobile GIS tích hợp một hoặc nhiều các công nghệ sau:

ꢀ

Các thiết bị Mobile

Hệ thống định vị toàn cầu (GPS)

Công nghệ truyền thông không dây cho truy cập GIS Internet

ArcPad là giải pháp toàn diện GIS cho thiết bị cầm tay với mục đích cập nhật dữ

liệu cho hệ thống GIS như thu thập, truy vấn, phân tích và quản lý dữ liệu địa lý.

ArcPad cung cấp các chức năng đồng bộ hóa dữ liệu với ArcGIS nhằm nâng cao

chức năng xử lý dữ liệu địa lý, cùng với khả năng chuyển đổi dữ liệu. ArcPad là công

cụ cho các chuyên gia về GIS bởi khả năng tích hợp hỗ trợ các thiết bị thu thập dữ

liệu cầm tay tiện ích và hiện đại.

Các khả năng chính

ꢀ

Được xây dựng với các công cụ cập nhật dữ liệu địa lý mạnh, quản lý

dữ liệu không gian tốt, phục vụ quá trình chỉnh sửa, cập nhật thông tin cho dữ

liệu không gian và thuộc tính.

ꢀ

Cho phép sử dụng với các thiết bị như PPC, Smart Phone, Pcphone.

Cho phép sử dụng nhiều dạng dữ liệu.

Xây dựng và quản lý cơ sở dữ liệu, ứng dụng các đoạn mã chương

trình để xử lý các quy trình GIS tự động.

ꢀ

Cho phép cập nhật dữ liệu GIS tự động và đơn giản hóa, đồng thời

cho phép hiện thị và tạo các bản đồ chất lượng cao Hệ thống Mobile ArcGIS

Desktop

1.6.1. Hệ thống WebGIS

WebGIS l hệ thống thông tin địa lý phân tán trên mạng máy tính để thu thập,

phân phát, truyền tải các thông tin địa lý dựa trên nền công nghệ Web. Hệ thống

WebGIS sử dụng mô hình kiến trúc khách – chủ. Mô hình khách chủ có thể triển khai

theo 3 cách tiếp cận “nhẹ khách” (thin client) , “nặng khách” (thick client), hoặc mô

hình cân đối .

Mô hình “nhẹ khách” có nghĩa là hầu hết công việc xữ lý ở phía dịch vụ, phía

khách không làm gì nhiều hơn là hiển thị kết quả. Ưu điểm của mô hình này là người

dùng không cần cài đặt thêm các ứng dụng. Máy khách nhẹ tải nên không cần cấu hình

cao. Tuy nhiên để giảm tải cho phía chủ cung cấp dịch vụ, các máy chủ Web, máy chủ

CSDL và WebGIS có thể không tập trung trên một máy nền duy nhất mà phân tán trên

các máy chủ khác nhau và liên kết qua mạng. Vì ở máy khách chỉ có nhiệm vụ hiển thị

kết quả do đó khi người sử dụng muốn sử dụng các thao tác với dữ liệu không gian, ví

7

dụ cập nhật một đối tượng, một khu vực địa lý trên bản đồ thì sẽ khó thực hiện. Do đó

mô hình nhẹ khách là giải pháp đơn giản để xây dựng tập hệ thống bản đồ chủ yếu

phục vụ tra cứu, tìm kiếm thông tin, chỉ sử dụng bộ duyệt web.

Mô hình “nặng khách” đối lập với “nhẹ khách”. Phía khách đảm nhiệm thêm một

số chức năng xử lý, cần cài đặt thêm các tiện ích ví dụ các trình plugꢀin, ActiveX hay

Javaꢀapplets. Các tiện ích GIS plugꢀin mở rộng khả năng của bộ duyệt web, làm cho

nó có khả năng xử lý các khuôn dạng dữ liệu GIS. Một số chức năng GIS đơn giản có

thể do các trình plugꢀin hay các applet thực hiện tại phía khách, không cần gửi về máy

chủ dịch vụ giúp giảm bớt việc truyền dữ liệu trên mạng. Ưu điểm của giải pháp “nặng

khách” là khả năng tương tác cao hơn, người sử dụng được hòan thiện hơn. Nhược

điểm của giải pháp này chủ yếu là ở khâu phân phát công cụng phần mềm để cài đặt ở

máy khách.

Mô hình “cân đối”, người thiết kế phải quyết định phân phối tính toán giữa máy

chủ và máy trạm sao cho hợp lý cũng như cân nhắc, tính toán dữ liệu truyền.

Ví dụ về mô hình WebGIS: GoogleEarth (KML) là phần mềm GIS của Google

xây dựng trên phạm vi toàn cầu, nó được xây dựng trên nền tảng ClientꢀServer nhờ sử

dụng KML để lưu trữ và quản lý dữ liệu. Cung cấp hệ thống bản đồ phong phú và đa

dạng, tốc độ xử lý nhanh.KML có cấu trúc ngữ pháp XML và khuôn dạng dữ liệu để

mô hình và lưu trữ các đối tượng đồ họa địa lý như các điểm, đường, ảnh và polygon

để hiển thị ở phía Client của GoogleEarth. Google Earth kết hợp với các hệ thống vệ

tinh để đưa ra các hình ảnh mới nhất và sống động nhất cho người dùng. GoogleEarth

là một sản phẩm phục tốt cho người dùng nghiệp dư, với các chuyên gia, GoogleEarth

vẫn chưa đáp ửng đủ yêu cầu.

8

CHƯƠNG 2. TỔ CHỨC DỮ LIỆU TRONG GIS

2.1. Tổ chức dữ liệu trong hệ thống thông tin địa lý

GIS cung cấp đầy đủ các thông tin địa lý của bản đồ, GIS lưu trữ các thành phần

của bản đồ thành 1 tập các lớp theo chủ đề, liên kết với nhau. Cách tiếp cận thành từng

lớp (layer) cho phép tổ chức thế giới thực phức tạp thành dạng đơn giản hơn, dễ quản

lý hơn.

Hình 2 – Tổ chức các lớp của thế giới thực

Trong hệ thống thông tin địa lý, dữ liệu được chia làm hai loại dữ liệu cơ bản: dữ

liệu không gian và dữ liệu 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ị.

Dữ liệu không gian là dữ liệu về vị trí địa lý của các đối tượng theo một hệ tọa độ

hay hệ quy chiếu nào đó, 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 đối tượng địa lý cụ thể trên 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, … Dữ liệu không

gian có thể biểu diễn bằng mô hình dữ liệu raster hay mô hình dữ liệu vector.

Dữ liệu phi không gian hay dữ liệu thuộc tính là những đặc tính, số lượng, mối

quan hệ kết nối logic giữa các dữ liệu không gian của các đối tượng bản đồ với vị trí

địa lý của chúng. Dữ liệu thuộc tính nói chung thuộc kiểu số, hoặc chữ số và chúng

được tổ chức lưu thành các bảng dữ liệu trong CSDL theo mô hình quan hệ.

9

2.1.1. Mô hình dữ liệu Vector

Mô hình dữ liệu vector xem các sự vật, hiện tượng là tập các thực thể không gian

cơ sở và tổ hợp của chúng. Trong mô hình 2D thì các thực thể cơ sở bao gồm: điểm

(point), đường (line), vùng (polygon). Các thực thể cơ sở này được hình thành trên cở

sở các vector hay toạ độ của các điểm trong một hệ trục toạ độ nào đó.

Loại thực thể cơ sở được sử dụng phụ thuộc vào tỷ lệ quan sát hay mức độ khái

quát của bản đồ. Với bản đồ có tỷ lệ nhỏ thì thành phố được biểu diễn bằng điểm

(point), đường đi, sông ngòi được biểu diễn bằng đường (line). Khi tỷ lệ thay đổi kéo

theo sự thay đổi về thực thể biểu diễn. Thành phố lúc này sẽ được biểu diễn bởi vùng

có đường ranh giới. Khi tỷ lệ lớn hơn, thành phố có thể được biểu diễn bởi tập các

thực thể tạo nên các đối tượng nhà cửa, đường sá, các trình tiện ích,… Có thể nói mô

hình dữ liệu vector sử dụng các đoạn thẳng hay các điểm rời rạc để biểu diễn các đối

tượng địa lý của thế giới thực.

Hình 2 – số liệu Vector được biểu diễn dưới dạng vùng (polygons)

Đối tượng điểm được biểu diễn dưới dạng một vector 2 chiều (x,y), xác định vị

trí của điểm đó trên bản đồ. Đối tượng là đường được xác định như tập hợp dãy của

các điểm, vùng được xác định bởi ranh giới các đường thẳng, những đối tượng này

được gọi là các polygons, được mô tả bằng tập các đường và điểm nhãn (lable points).

Mô hình dữ liệu vector định hướng đến các hệ thống quản trị cơ sở dữ liệu.

Chúng có ưu việt trong việc lưu trữ số liệu bản đồ. Vì các thành phần đồ họa biểu diễn

các đặc trưng của bản đồ liên kết trực tiếp với các thuộc tính được lưu trong CSDL, do

đó việc tìm kiếm có thể được thực hiện dễ dàng.

10

2.1.2. Hệ thống 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 (cell). Độ 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, khác nhau từ vài chục dm đến vài km. Dữ liệu raster

gắn liền với dữ liệu dạng ảnh hoặc dữ liệu có tính liên tục cao. Dữ liệu raster có thể

biểu diễn được rất nhiều các đối tượng từ hình ảnh bề mặt đất đến ảnh chụp từ vệ tinh,

ảnh quét và ảnh chụp. Định dạng dữ liệu raster rất đơn giản nhưng hỗ trợ rất nhiều

kiểu dữ liệu khác nhau. 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 chứa 1 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ý thiên nhiên. Trong một hệ thống CSDL cơ

bản, raster được lưu trữ trong các ô (thường hình vuông) được sắp xếp trong một mảng

hoặc dãy các hàng và cột.

Trong cấu trúc dữ liệu raster, các điểm (points) 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 dãy các cell nằm kề sát

nhau.

Hình 3 ꢀ Mảng cell và bảng thuộc tính

Hình 4 ꢀ Biểu diễn các đối tượng cơ sở trong raster

11

Cũng như mô hình vector, mô hình raster có các tầng bản đồ cho địa hình, hệ

thống thủy lợi, sử dụng đất, … Tuy nhiên do cách thức xử lý thông tin thuộc tính khác

nhau, nên mô hình raster thường có nhiều bản đồ hơn. Ví dụ, trong mô hình vector để

biểu diễn mức độ ô nhiểm của một “con sông” có thể được gán trực tiếp cho nó.

Nhưng trong mô hình raster không làm được như vậy. Trước hết phải tạo lập tầng bản

đồ cho “con sông”, sau đó tạo tầng bản đồ thứ hai để chỉ mức độ ô nhiểm. Kết quả là

số lượng tầng bản đồ của một hệ thống raster tăng lên đáng kể so với mô hình vector.

Ưu điểm của mô hình raster là đơn giản, lưới là một bộ phận của bản đồ đã được

sử dụng để kiến tạo thông tin địa lý. Khi các số liệu đầu vào là các ảnh vệ tinh hay ảnh

từ máy quét – có khuôn mẫu lưới, chúng sẽ phù hợp cho mô hình dữ liệu này. Lợi thế

lớn nhất của hệ thống raster là dữ liệu hình thành trong bản đồ trong bộ nhớ máy tính.

Do vậy, các thao tác kiểu như so sánh lưới tế bào được thực hiện dễ dàng. Tuy nhiên

hệ thống raster không thuận tiện cho việc biểu diễn đường, điểm vì mổi chúng là tập

các tế bào trong lưới, do đó đường thẳng dễ bị đứt đoạn hoặc rộng hơn thực tế.

Điểm yếu nhất của mô hình dữ liệu raster là phải xử lý khối dữ liệu rất lớn. Nếu

độ phân giải của lưới càng thấp thì các thực thể trên bản đồ càng có thể bị mất đi.

Ngược lại nếu độ phân giải cao thì phải lưu trữ một khối lượng lớn các thông tin trong

CSDL.

Mô hình dữ liệu vector cho ta nhiều thao tác hơn trên các đối tượng so với mô

hình raster. Việc tính diện tích, đo khoảng cách của các đối tượng được trong mô hình

Vector thực hiện bằng các tính toán hình học từ toạ độ của các đối tượng thay vì việc

tính toán trên các điểm ảnh như ở mô hình raster.

Hình 3 – Kết hợp giữa mô hình vector và raster

12

Mỗi mô hình raster và vector đều có những ưu và nhược điểm riêng. Tùy theo

mục tiêu sử dụng của GIS mà có thể thiết kế chức năng biến đổi Raster/Vector nếu cần

thiết. Thông thường người ta biểu diễn thế giới thực bởi sự kết hợp giữa giữ liệu

vector và raster.

2.1.3. Mô hình TIN

Các ứng dụng mô hình hoá địa hình đòi hỏi phương pháp biểu diễn độ cao so với

bề mặt nước biển. Có rất nhiều mô hình biểu diễn bề mặt thực hiện công việc này,

trong đó mô hình “lưới tam giác không đều” ꢀ gọi tắt là mô hình TIN được đánh giá là

hiệu quả nhất.

Hình 5 ꢀ Bản đồ với mô hình dữ liệu TIN

TIN có khả năng biểu diễn bề mặt liên tục từ những tập hợp điểm rời rạc. Về mặt

hình học, TIN là tập các điểm được nối với nhau thành các tam giác. Các tam giác này

hình thành nên bề mặt 3 chiều. Các điểm được lưu trữ cùng với giá trị gốc chiếu của

chúng. Các điểm này không cần phải phân bố theo một khuân mẫu nào và mật độ phân

bố cũng có thể thay đổi ở các vùng khác nhau. Một điểm bất kỳ thuộc vùng biểu diễn

sẽ nằm trên đỉnh, cạnh hoặc trong một tam giác của lưới tam giác. Nếu một điểm

không phải là đỉnh thì giá trị hình chiếu của nó có được từ phép nội suy tuyến tính (của

hai điểm khác nếu điểm này nằm trên cạnh hoặc của ba điểm nếu điểm này nằm trong

tam giác). Vì thế mô hình TIN là mô hình tuyến tính trong không gian 3 chiều có thể

được hình dung như sự kết nối đơn giản của một tập hợp các tam giác.

Ta có thể lưu trữ sơ đồ của TIN bằng danh sách liên kết đôi hoặc cấu trúc tứ

phân. Cả hai phương pháp này đều mô tả cấu trúc hình học tô pô của bản đồ chia nhỏ.

2.2. Điểm qua cách tổ chức dữ liệu trong một số hệ thống GIS thông dụng.

2.2.1. Tổ chức dữ liệu trong MapInfo

Các thông tin trong MapInfo được tổ chức theo từng bảng, mỗi một bảng là một

tập các File về thông tin đồ họa hoặc phi đồ họa chứa các bản ghi dữ liệu mà hệ thống

tạo ra. Cơ cấu tổ chức thông tin của các đối tượng địa lý được tổ chức theo các File

sau đây:

13

ꢀ .tab: mô tả khuôn dạng tab, chứa thông tin để kết nối tất cả các tệp khác

trong ứng dụng MapInfo, thông tin về kiểu dữ liệu.

ꢀ .dat hoặc .dbf: tệp chứa dữ liệu thuộc tính, có cấu trúc tương tự như tệp

CSDL dBase III.

ꢀ .map: file chứa các thông tin mô tả đối tượng địa lý dưới dạng mã nhị

phân, cho phép hiển thị một bản đồ trên màn hình.

ꢀ .id: file chứa các thông tin liên kết các đối tượng lại với nhau

ꢀ .ind: file chứa các chỉ số đối tượng

ꢀ .wor: tập tin lưu trữ tổng hợp các table hoặc các cửa số thông tin khác

nhau của MapInfo.

2.2.2. Tổ chức dữ liệu trong ArcGIS của ESRI

Khuôn dạng shapefile được đưa vào sử dụng trong ArcGIS 2 từ đầu những năm

90. Thuật ngữ “shapefile” thường được dùng để chỉ một tập hợp nhiều tệp có chung

tên nhưng với phần mở rộng khác nhau, cùng trong 1 thư mục. Để hiểu sâu hơn về cấu

trúc lưu trữ của một GIS ta sẽ đi sâu tìm hiểu shapefile như là một ví dụ ở phần sau.

2.2.3. Tổ chức dữ liệu trong GRASS

GRASS là một trong những ứng dụng GIS nguồn mở rất mạnh. GRASS nổi tiếng

về phân tích dữ liệu raster, điều mà chúng ta không thấy ở các GIS thương mại như

MapInfo Professional hoặc Arcview. Tuy nhiên, sau này các chức năng liên quan đến

dữ liệu vector cũng đang được phát triển.

Dữ liệu GIS trong GRASS nằm trong một thư mục được gọi là CSDL GIS

(GISDBASE). Trong CSDL GIS đó có các thư mục con được gọi là LOCATION (vị

trí), trong các LOCATION có các thư mục con gọi là MAPSET (bộ bản đồ). Các

mapset sẽ chứa các tệp và các thư mục con, gọi là các phần tử (thành phần) cơ sở dữ

liệu. Mỗi một phiên làm việc của GRASS chỉ được làm việc với một MAPSET trong

một LOCATION mà thôi. Nếu không có dữ liệu sẵn, bạn phải tự tạo ra LOCATION

và MAPSET mới.

Bản đồ vector trong GRASS được lưu trữ theo các biểu diễn cungꢀnút, bao gồm

các đường cong gọi là cung. Một cung được lưu trữ như một danh sách các cặp tọa độ

x,y. Điểm đầu, điểm cuối của một cung được gọi là nude. Hai cặp tọa độ x, y liên tiếp

nhau xác định một đoạn (segment) của cung. Các cung đơn lẽ hay kết hợp với các

cung khác tạo ra các đối tượng bản đồ ở mức cao hơn. Các cung đơn lẽ tạo nên các

line biểu diễn các đối tượng như đường, sông suối, … các cung bao quanh 1 vùng

được gọi là area edges hay areas lines.

14

Hình – Cấu trúc thư mục của Grass

Các tệp của cùng một lớp bản đồ vector có cùng một tên, nhưng mỗi tệp nằm

trong một thư mục CSDL khác nhau trong mapset.

2.3. Tìm hiểu cấu trúc lưu trữ của Shapefile

Shapefile là một cấu trúc dữ liệu GIS được đưa ra bởi ESRI cho cácn phần

mềm hệ thống thông tin địa lý, như một chuẩn mở cho việc chia sẽ dữ liệu giữa ESRI

và các phần mềm GIS khác. Một shapefile thường là 1 tập các files cùng tên với đuôi

.shp, .shx , .dbf,…

Shapefile dùng để mô tả các đối tượng địa lý: điểm, đường, đa giác. Mổi đối

tượng có các thuộc tính địa lý, ví dụ: tên, nhiệt độ, độ cao,…

Shapefile lưu trữ dữ liệu dưới dạng vector để chứa các đối tượng địa lý và các

thông tin liên quan. Tuy nhiên, nó không có khả năng chứa thông tin mạng topo hình

học.

Shapefile lưu trữ các loại dữ liệu địa lý cơ bản của các điểm, đường, đa giác. Để

có những thông tin thuộc tính về các đối tượng để xác định đối tượng nào mà chúng

biểu diễn, một bảng các bản ghi sẽ chứa các thuộc tính cho mỗi đối tượng trong

shapefile. Những biểu diễn của các đối tượng địa lý (các điểm, các đường, các đa giác)

này có thể tạo ra rất nhiều biểu diễn của dữ liệu địa lý cung cấp khả năng tính toán địa

lý mạnh mẽ và chính xác.

15

Shapefile là một tập của một số file (thông thường có 3 file cơ bản). Mỗi file tuân

theo quy tắc đặt tên file của MS DOS.

3 file bắt buộc:

- .shp: thông tin về dạng hình học của đối tượng địa lý.

- .shx: định dạng index của shapefile;

- .dbf: định dạng thuộc tính; các cột thuộc tính cho mỗi shape trong dBase

III.

Các file tùy chọn:

- .prj: định dạng projection; lưu thông tin hệ tọa độ và thông tin project, sử

dụng định dạng WKT.

- .sbn và .sbx: một kiểu index không gian của các đặc trưng (features).

- .fbn và .fbx: một index không gian của các đặc trưng cho những

shapefile chỉ đọc

- .ain và .aih: một index thuộc tính của các của các trường hoạt động trong

bảng hoặc trong các thuộc tính của bảng.

- …

Định dạnh của shapefile (.shp)

File chính (.shp) chứa dữ liệu tham chiếu của đối tượng địa lý chính trong

shapefile. Nó gồm 1 tiêu đề độ dài cố định theo sau bởi một hoặc nhiều bản ghi độ dài

có thể thay đỗi. Mỗi bản ghi này chứa một thành phần bản ghi tiêu đề và một thành

phần bản ghi nội dung.

Tiêu đề của main file với chiều dài cố định: 100bytes:

(Trong các bảng, cột Endianness chỉ mức độ quan trọng của dữ liệu).

Bytes

0ꢀ3

Type

Int32

Endianness

Usage

File code (always hex value 0x0000270a)

Unused; five uint32

Big

4ꢀ23

24ꢀ27

File length (in 16ꢀbit words, including the

header)

16

28–31

32–35

36–67

int32

little

Version

int32

Shape type (see reference below)

double

Minimum bounding rectangle (MBR) of

all shapes contained within the shapefile;

four doubles in the following order: min

X, min Y, max X, max Y

68ꢀ83

84ꢀ99

Double

Little

Range of Z; two doubles in the following

order: min Z, max Z

Range of M; two doubles in the

following order: min M, max M

File .shp chứa số lượng bản ghi thay đổi với số lượng bất kỳ. Mỗi bản ghi được

thêm vào đầu bởi 1 bản ghi tiêu đề dài 8bytes

Bytes

0ꢀ3

Type

Int32

Endianness

Usage

Big

big

Record number (1ꢀbased)

Record length (in 16ꢀbit words)

4ꢀ7

Theo sau bản ghi tiêu đề là bản ghi thật

Byte

0ꢀ3

4ꢀ

Type

Int32

ꢀ

Endianness

Usage

Little

ꢀ

Shape type

Shape content

Nội dung của các bản ghi có chiều dài thay đổi phụ thuộc vào loại của đối tượng

biểu diễn

17

Shapefile index (.shx)

File chỉ số của shapefile cũng chứa tiều đề 100ꢀbyte như .shp, theo sau bởi bất kỳ

một số các bản ghi có độ dài có định 8byte với 2 trường.

Bytes

0ꢀ3

Type

Int32

Endianness

Usage

Big

Record offset (in 16ꢀbit words)

Record length (in 16ꢀbit words)

4ꢀ7

Sử dụng chỉ số này, cho phép tìm giật lùi trong shapefile bằng cách tìm kiếm giật

lùi trong shape index, đọc record offset, và sử dụng nó để tìm đến vị trí tương ứng

trong .shp file. Tương tự, nó cũng cho phép tìm kiếm trên một số tùy ý bản ghi bởi

cùng phương pháp.

File dữ liệu (.dbf)

Các thuộc tính cho mỗi shape được chứa dưới dạng dBase. Một định dạng thay

thể cũng có thể được sử dụng là xBase.

File định dạng Project (.prj)

18

Thông tin Project được chứa trong .prj file giúp người dùng có thể hiểu được dữ

liệu được chứa trong .shp file một cách chính xác. Mặc dù file này là tùy chọn, nhưng

nó thường luôn được tạo.

19

CHƯƠNG 3. XỬ LÝ TRUY VẤN KHÔNG GIAN

3.1. Cấu trúc RꢀTree index

Rꢀtree là một cây cân bằng tương tự như Bꢀtree với các các bản ghi index trên

các nốt lá trỏ đến các đối tượng dữ liệu. Cấu trúc Rꢀtree được thiết kế sao cho việc tìm

kiếm các đối tượng không gian sẽ có số lượng lần thăm các node nhỏ nhất. Rꢀtree cho

phép xóa hoặc chèn các index mới mà không cần phải thường xuyên tổ chức lại.

Một CSDL không gian chứa một tập các tuples – biểu diễn cho các đối tượng

không gian và mỗi tuble có một ID duy nhất. Trong Rꢀtree các nốt lá chứa các bản ghi

index có dạng:

(I, tuple – identifier)

Với tuple – identifier tham chiếu đến tuple trong CSDL và I là một hình chử nhật

nꢀchiều, là hộp bao của đối tượng không gian được index

I=(I₀, I₁,…, I_nꢀ1)

Ở đây n là số chiều và I_ilà một khoảng bị chặn đóng [a, b] mô tả sự mở rộng của

đối tượng theo chiều i. Tuy nhiên, I_icó thể có một hoặc hai điểm cuối bằng vô cùng để

chỉ rằng đối tượng mở rộng vô cùng theo hướng i. Một node không phải là lá chứa

những entries có dạng

(I, child – pointer)

Với childꢀpointer là địa chỉ của node con trong Rꢀtree và I bọc tất cả các hình chử

nhật trong các mục của node con.

3.1.1. Cấu trúc của Rꢀtree

Đặt M là số lượng tối đa các entry trong 1 node, và m <= M/2 xác định số lượng

entry ít nhất phải có trong 1 node. Rꢀtree thõa mản các thuộc tính sau:

(1)

Mọi node lá chứa từ m đến M bản ghi index trừ khi nó là root

(2)

Với mỗi bản ghi (I, tupleꢀidentifier) trong 1 node lá, I là hình chử

nhật nhỏ nhất chứa đối tượng không gian biểu diễn bởi tupleꢀidentifier.

(3)

Mỗi node không phải node lá có từ m đến M con trừ khi nó là

root

(4)

Với mỗi entry (I, childꢀpointer) trong 1 node không phải lá, I là

hình chử nhật nhỏ nhất bao các hình chử nhật con.

20

(5)

(6)

Node root có ít nhất 2 con trừ khi nó là lá.

Tất cả các lá xuất hiện với cùng mức.

Hình 6 – Cấu trúc Rꢀtree

Hình 6a, và 6b biểu diễn cấu trúc của một Rꢀtree và minh họa mối quan hệ

bao hàm và chồng phủ lẫn nhau có thể tộn tại giữa các hình chử nhật trong Rꢀtree.

Chiều cao của một Rꢀtree chứa N bản ghi index ít nhất là |log_mN|ꢀ1, vì hệ số

nhánh của mỗi node ít nhất là m, số node tối đa là |N/m|+|N/m²|+..+1. Trường hợp

xấu nhất là tất cả các node chứa m entry. Thông thường, các node thường có nhiều

hơn m entry, vì vậy chiều cao của cây sẽ ít hơn |log_mN|ꢀ1.

3.1.2. Tìm kiếm và cập nhật trong Rꢀtree

Tìm kiếm

21

Thuật toán tìm kiếm đi xuống từ root tương tự như Bꢀtree. Tuy nhiên, do cấu

trúc bao hàm và chồng phủ lẫn nhau có thể tồn tại nên số cây con được tìm kiếm có

thể lớn hơn 1, vì vậy không thế đảm bảo một hiệu năng tốt trong trường hợp xấu

nhất. Tuy nhiên với hầu hết các loại dữ liệu thuật toán update sẽ duy trì cây ở dạng

cho phép thuật toán tìm kiếm đánh giá các miền không phù hợp của không gian

index, và chỉ xem xét những dữ liệu gần vùng tìm kiếm.

Thuật toán Search. Cho một Rꢀtree với node root là T, tìm tất cả các bản ghi

index chứa những hình chử nhật chồng lên hình chử nhật đang tìm S.

- S1[Tìm cây con] Nếu T không phải là lá, kiểm tra mỗi entry E của T để

xác định xem EI có chồng lên S hay không. Với tất cả entries chồng, gọi hàm

Search trên cây mà node root được trỏ bởi Ep.

- S2[Tìm node lá] Nếu T là 1 lá, kiểm tra tất cả entry E để xác định EI có

chồng lên S hay không. Nếu có, E là 1 bản ghi “có chất lượng”.

(Ở đây EI là hình chử nhật được trở đến bởi entry E, Ep là con trỏ trong entry E)

.

Chèn

Việc chèn các bản ghi index cho những tuples data mới cũng có tư tưởng

tương tự như chèn trong Bꢀtree: các bản ghi mới sẽ được thêm vào các lá, các node

bị tràn sẽ được cắt ra, và việc cắt sẽ lan truyền lên.

Thuật toán Insert chèn 1 index mới E vào Rꢀtree:

- I1 [Tìm vị trí cho bản ghi mới] Gọi hàm ChoseLeaf để tìm một node lá L

để đặt E.

- I2 [Thêm bản ghi vào node lá] Nếu L có chố trống, đưa E vào L. Nếu

không gọi hàm SplitNode để được L và LL chứa E và tất cả các entries củ của

L.

- I3 [Lan truyền thay đổi lên trên] Gọi hàm AdjustTree trên L, cả LL nếu

xảy ra việc chia node.

- I4 [Mọc cây cao hơn] Nếu việc lan truyền chia node làm cho root cũng

bị chia, tạo một root mới có các con là 2 node được tạo ra.

Thuật toán AdjustTree: Đi lên từ node lá L đến root, điểu chỉnh các hỉnh chử

nhật bao phủ và lan truyền việc chia các node nếu cần thiết.

- AT1 [khởi tạo] Đặt N=L, nếu L đã bị chia trước đó, đặt NN là kết quả

thứ 2 (NN=LL).

- AT2[kiểm tra hoàn thành] Nếu N là root, dừng

22

- AT3[điều chỉnh hình chử nhật bao trong entry cha]Đặt P là node cha của

node N, và E_Nlà entry của N trong P. Điểu chỉnh E_NI để nó bao quanh sít với

tất các entry hình chử nhật trong N.

- AT4[Lan truyền chia node lên trên] Nếu có NN, tạo 1 entry mới E_NNvới

E_NNp trỏ đến NN và E_NNI bao quanh tất cả hình chử nhật trong NN. Thêm E_NN

vào P nếu còn chổ trống. Nếu không gọi hàm SplitNode để xử lý node P và PP

chứa E_NNvà các entries cũ của P.

- AT5[Di chuyển lên mức tiếp theo] Đặt N=P và đặt NN=PP nếu 1 phân

chia xảy ra. Lặp từ AT2.

Xóa

Thuật toán Delete. Xóa bản ghi index E từ Rꢀtree

- D1 [Tìm node chứa bản ghi] Gọi hàm FindLeaf để xác định vị trí của

node lá L chứa E. Dừng nếu không tìm thấy bản ghi.

- D2 [Xóa bản ghi] Xóa bản ghi E từ L

- D3 [lan truyền thay đổi] gọi hàm CondenseeTree cho L.

- D4 [Thu ngắn cây] nếu node root chỉ có 1 cây con sau khi điều chỉnh

cây, đặt con thành root.

Thuật toán FindLeaf. Cho 1 Rꢀtree có root node là T, tìm node lá chứa index

entry E.

- FL1 [tìm cây con] nếu T là không phải là node lá, kiểm tra mỗi entry F

trong T để xác định FI có chồng lên EI hay không. Với mỗi entry nếu có thì gọi

FindLeaf trên cây có root trỏ bởi Fp cho đến khi tìm thấy E hoặc đến khi tất cả

entries đã được kiểm tra.

- FL2 [tìm node lá cho bản ghi] Nếu T là 1 lá, kiểm tra mỗi entry xem có

phù hợp, nếu có trả lại T.

Thuật toán CondenseTree: cho 1 node lá L từ 1 entry đã bị xóa, loại các node

nếu nó có quá ít entry và xây dựng lại các entry của nó. Lan truyền loại các node

lên trên nếu cần thiết. Điều chỉnh tất các các hình chử nhật trên đường tới root, làm

cho nó nhỏ hơn nếu có thể.

- CT1 [khởi chạy] đặt N=L, đặt Q là tập các node bị loại, Q=null

- CT2 [tìm entry cha] Nếu N là root đi tới CT6. Nếu không lấy P là cha

của N, và lấy E_Nlà entry ở trong P trỏ đến N.

23