Luận vă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 ĐẠ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 KHỐ 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 ii ĐẠ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 KHỐ 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 iii 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ể hồ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, hồ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 để hồ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 để hồ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 hồ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 iv 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. v DANH MỤC TỪ VIÊT TẮT Từ viết tắt Tiếng Anh Tiếng Việt GIS 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 Cơ sở dữ liệu NN Nearest Neighbor Hàng xĩm gần nhất OR Obstacle range ONN Obstacle nearest neighbour ODJ Ostacle e-distance join vi 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 tố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 vii 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 1 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ý. Để hồ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 tố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). 2 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ĩ 3 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ự đố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. 4 Ư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 tố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ở tố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: 5 - 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ự tồ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. Ngồ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 đồ 6 - 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 Ngồ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 ngồ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ý. 7 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ị tồ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 tồ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í 8 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 tố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 tố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 tồ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. 9 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ệ. 10 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. 11 2.1.2. Hệ thống Raster Mơ hình dữ liệu dạng raster phản ánh tồ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 tố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 12 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 tốn hình học từ toạ độ của các đối tượng thay vì việc tính tố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 13 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 hố đị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: 14 - .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. 15 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 tốn địa lý mạnh mẽ và chính xác. 16 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 Type Endianness Usage 0-3 Int32 Big File code (always hex value 0x0000270a) 4-23 Int32 Big Unused; five uint32 24-27 Int32 Big File length (in 16-bit words, including the header) 17 28–31 int32 little Version 32–35 int32 little Shape type (see reference below) 36–67 double little 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 Double Little Range of Z; two doubles in the following order: min Z, max Z 84-99 Double Little 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 Type Endianness Usage 0-3 Int32 Big Record number (1-based) 4-7 Int32 big Record length (in 16-bit words) Theo sau bản ghi tiêu đề là bản ghi thật Byte Type Endianness Usage 0-3 Int32 Little Shape type 4- - - 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 18 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 Type Endianness Usage 0-3 Int32 Big Record offset (in 16-bit words) 4-7 Int32 Big Record length (in 16-bit words) 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) 19 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. 20 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=(I0, I1,…, In-1) Ở đây n là số chiều và Ii là 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, Ii cĩ 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. 21 (5) Node root cĩ ít nhất 2 con trừ khi nĩ là lá. (6) 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à |logmN|-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/m2|+..+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 |logmN|-1. 3.1.2. Tìm kiếm và cập nhật trong R-tree Tìm kiếm 22 Thuật tố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 tốn update sẽ duy trì cây ở dạng cho phép thuật tố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 tố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 tố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 tố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 hồn thành] Nếu N là root, dừng 23 - AT3[điều chỉnh hình chử nhật bao trong entry cha]Đặt P là node cha của node N, và EN là entry của N trong P. Điểu chỉnh ENI để 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 ENN với ENNp trỏ đến NN và ENNI bao quanh tất cả hình chử nhật trong NN. Thêm ENN 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 ENN và 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 tố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 tố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 tố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 EN là entry ở trong P trỏ đến N. 24 - CT3 [loại trừ những node dưới full] Nếu N cĩ ít hơn m entries, xĩa EN từ P và thêm N vào tập Q. - CT4 [điều chỉnh hình chử nhật bao] Nếu N chưa bị loại, điều chỉnh ENI để bao sát tất cả các entries trong N. - CT5 [di chuyển lên] Đặt N=P và lặp lại từ bước CT2 - CT6 [chèn lại những entrie mồ cơi] chèn lại tất cả các entries của các node trong tập Q. Những entries từ những lá bị loại được chèn lại vào trong các lá như trong thuật tốn Insert, nhưng những entries từ các node cao hơn phải được đặt ở mức cao hơn của cây, để các lá của các cây con phụ thuộc của chúng sẽ ở cùng mức như các lá của cây chính. Phương pháp kết hợp các node under – full đưa ra ở trên là hiệu quả hơn cho CSDL khơng gian so với phương pháp sử dụng ở B-tree. Với phương pháp như ở B-tree (một under-full node cĩ thể được kết hợp với node anh em nào đĩ) sẽ làm cho diện tích hình chử nhật bao của nĩ tăng lên. Mặc dù cả 2 phương pháp đều cĩ thể gây ra phân chia node. Phương pháp đưa ra ở trên là hiệu quả hơn vì 2 lý do: thứ nhất, dễ hơn để triển khai vì đều là Insert và tính hiệu quả của việc Insert đệ quy là tốt hơn vì những trang cần trong quá trình chèn lại thường là giống với với những trang đã thăm trong lúc tìm kiếm trước kia nên thường thì chúng đã cĩ sẵn trong bộ nhớ. Lý do thứ hai là việc chèn lại này sẽ làm cấu trúc của cây trở nên tốt hơn, và ngăn ngừa sự hư hỏng dần dần cĩ thể xảy ra nếu mổi entry được đặt cố định dưới cùng node cha. 3.1.3. Cập nhật và các thao tác khác Nếu một tuple dữ liệu được cập nhật thì hình chử nhật bao của nĩ củng bị thay đổi, bản ghi index của nĩ cũng phải được xĩa, cập nhật, và sau đĩ chèn lại, do đĩ nĩ sẽ phải tìm một vị trí phù hợp của nĩ trên cây. Những loại tìm kiếm khác với tìm kiếm ở trên, ví dụ: để tìm tât cả các đối tượng dữ liệu chứa hồn tồn một diện tích tìm kiếm, hoặc tất cả các đối tượng chứa 1 vùng tìm kiếm, cĩ thể được thực hiện bởi sự biến đổi của các thuật tốn đã đưa ra. Tìm kiếm một entry cĩ ID đã biết được yêu cầu bởi thuật tốn xĩa và được thực hiện bởi thuật tốn FindLeaf. Những biến thể của xĩa miền, trong những index entries của tất cả các đối tượng dữ liệu trong 1 vùng đăc biệt được xĩa, cũng được hổ trợ bởi R-tree. Chia Node Để thêm 1 entry mới vào 1 node đã đầy chứa M entries, cần phải chia tập M+1 entries thành 2 node. Việc chia phải được thực hiện sao cho các tìm kiếm tiếp theo khả năng phải thăm cả 2 node càng thấp thì càng tốt. Vì một node cĩ được chọn để để thăm hay khơng phụ thuộc vào hình chử nhật nĩ bao phủ cĩ bao vùng tìm kiếm hay khơng, do đĩ để tối ưu, tổng diện tích của cả 2 hình hình chử nhật 25 bao phủ phải là nhỏ nhất. Hình 2 minh họa trường hợp này. Diện tích của hình chử nhật trong trường hợp “bad split” lớn hơn nhiều trong trường hợp “good split”. Hình 7 – Chia node Khi thực hiện thuật tốn ChooseLeaf cũng xảy ra vấn đề tương tự. Do đĩ thuật tốn để phân chia tập M+1 entries thành 2 nhĩm cĩ ảnh hưởng rất lớn đến hiệu năng của R-tree và cần được tối ưu. Một số thuật tốn phân chia: Thuật tốn tồn diện Cách dễ nhất để tìm một node bị chia cĩ diện tích nhỏ nhất là sinh ra tất cả các nhĩm cĩ thể và chọn nhĩm tốt nhất. Tuy nhiên, với cách này số lượng các nhĩm phải kiểm tra là 2M-1 mà trong R-tree giá trị hợp lý của M là 50, do đĩ số lượng cách phân chia cĩ thể là rất lớn. Thuật tốn Quadratic-Cost Thuật tốn này cố gắng tìm một phép phân chia tối ưu, nhưng khơng đảm bảo là tối ưu nhất. Chi phí của thuật tốn là dạng bậc 2 của M và tuyến tính theo số các chiều. Thuật tốn lấy 2 trong số M+1 entries làm 2 thành phần đầu tiên của 2 group mới, 2 entries sẽ được chọn sao cho nếu chúng cùng nằm trong một nhĩm thì sẽ gây nhiều lãng phí nhất đến diện tích hình chử nhật bao của chúng. Cĩ nghĩa là diện tích của hình chử nhật bao cả 2 entries, trừ đi diện tích của 2 entries, là lớn nhất. Những entries cịn lại sẽ được phân vào từng nhĩm từng cái một. Ở mỗi bước, việc thêm một entry vào một nhĩm được chọn sao cho diện tích mở rộng là nhỏ nhất. Thuật tốn Linear-Cost Thuật tốn này tuyến tính theo M và số chiều. Liner Split cũng giống như Quadratic Split nhưng phương pháp lựa chọn 2 entries đầu tiên và các entries thêm vào sau đĩ khác so với Quadratic. 26 R*- tree R*-tree là một biến thể của R-trees được sử dụng để đánh chỉ số các dữ liệu khơng gian. R*-tree cung cấp thuật tốn chèn hiệu quả hơn của R-tree. Nĩ sử dụng cơ chế forced reinsert để tổ chức lại cấu trúc của cây đánh chỉ số cho phù hợp. Cơ chế này cho phép cấu trúc cĩ thể thích nghi với việc xuất bản dữ liệu và khơng bị ảnh hưởng bởi các lần chèn trước. Các thử nghiệm cho thấy cấu trúc R*-tree cĩ hiệu năng cao hơn so với cấu trúc R-tree. R*- tree được đề xuất bởi Norbert Beckmann, Hans-Peetr Kriegel, Ralf Schneider, và Bernhard Seeger vào năm 1990. GiST GiST (Generalized Search Trees) indexes chia dữ liệu thành "things to one side", "things which overlap", "things which are inside" và cĩ thể được sử dụng trên một tập rộng các loại dữ liệu, bao gồm cả dữ liệu GIS. 3.2. Tìm hiểu một số thuật tốn xử lý truy vấn trong CSDL khơng gian Phần này đưa ra một số phương pháp xử lý truy vấn trong CSDL địa lý cĩ các chướng ngại vật. Hình 1 là một ví dụ của 1 truy vấn tìm điểm gần nhất cĩ sự ngăn cách của chướng ngại vật. Hình 8 – Truy vấn tìm hàng xĩm gần nhất Bài tốn đặt ra là phải tìm điểm gần nhất của q, nhưng phải tính đến sự tồn tại của các chướng ngại vật. Mặc dù theo khoảng cách O-clit thì điểm a là gần hơn so với điểm b, nhưng điểm gần nhất thực tế lại là điểm b. Trường hợp cụ thể của bài tốn là khi một khách hàng muốn tìm một nhà hàng gần nhất, ở đây, chướng ngại vật chính là các tịa nhà, hồ, hay những con đường mà khơng được đi, ... Đã cĩ rất nhiều nghiên cứu cĩ giá trị trong lĩnh vực tính tốn địa lý, để giải quyết những vấn đề về bộ nhớ, đường đi ngắn nhất giữa 2 điểm (cĩ tính đến các chướng ngại vật). Những thuật tốn này thường sử dụng cách tạo ra một đồ thị, với mỗi node tương ứng với 1 đỉnh của chướng ngại vật, và mỗi cạnh nối 2 đỉnh khơng cắt các chướng ngại vật. Những thuật tốn này đều giả sử là cĩ thể giử được đồ thị trong bộ nhớ chính. 27 Tuy nhiên, trong cơ sở dữ liệu khơng gian điều này là khơng khả thi vì yêu cầu bộ nhớ sẽ là cực lớn cho các tập dữ liệu khơng gian. Để giải quyết khĩ khăn đĩ, trong bộ nhớ chính chỉ lưu đồ thị của khu vực hiện thời và chỉ những chướng ngại cĩ thể ảnh hưởng đến kết quả của truy vấn. Với phương pháp đưa ra dưới đây, xem rằng cĩ 1 hoặc nhiều tập dữ liệu của các thực thể tạo nên các điểm ưa thích (nhà hàng, khách sạn,.. ) và 1 tập dữ liệu các vật cản. Các thực thể ưa thích và các vật cản cũng được đánh chỉ số bởi R-tree. 3.2.1. Xử lý truy vấn trong khơng gian O-clit R – tree trả lời truy vấn như được minh họa ở hình 9. Bắt đầu từ root, kiểm tra các entries trên node root, xem entries nào giao với vùng tìm kiếm, sau đĩ đệ quy tìm kiếm xuống các node trỏ đến bởi các entry này. Những entries khơng giao với vùng tìm kiếm bị bỏ qua. Kết quả của bước này sẽ được đi qua một bước lọc sau đĩ đưa ra kết quả chính xác. Một truy vấn tìm hàng xĩm gần nhất (nearest-neighbour query N-N) trả về k điểm dữ liệu (k>=1) gần nhất với điểm tìm kiếm. Thuật tốn R – tree NN (được đề xuất bởi Hjaltason và Samet 1999) : giữ một bảng băm chứa các entries của các node đã được thăm. Đầu tiên, bảng băm chứa các entries của root, sắp xếp theo thứ tự tăng dần khoảng cách đến q. Sau đĩ, entry với với khoảng cách gần nhất sẽ được loại khỏi bảng băm, và các entries của node con do nĩ trỏ đến được đưa vào bảng băm (đảm bảo thứ tự khoảng cách đến điểm tìm kiếm). Và cứ tiếp tục như thế cho đến khi tìm đến lá của cây. Hình 9 – Tìm kiếm trong R-tree Áp dụng thuật tốn với trường hợp trong hình 9, giá trị trong bảng băm lần lượt sẽ là : E2, E1
E1,E5,E6,E7
E3,E4,E5,E6,E7 và kết quả là điểm a, nằm trong E3. Truy vấn E-distance join tìm tất cả các cặp đối tượng (s, t) với s thuộc S, t thuộc T sao cho khoảng cách giữa chúng nhỏ hơn một số e cho trước. Nếu cả 2 tập dữ liệu S và T được đánh chỉ số bởi R – tree thì thuật tốn R-tree join (Brinkhoff 1993) sẽ duyệt đồng thời cả hai cây, đi theo những cặp entry mà khoảng cách của chúng ≤ e. 28 Thuật tốn intersection join, cĩ thể được dùng cho các đối tượng miền, trả về tất cả các cặp đối tượng giao nhau trong hai tập dữ liệu S và T. Nĩ cĩ thể được xem như là 1 trường hợp đặc biệt của e-distance join, với e=0. Truy vấn cặp gần nhất (closest-pairs query) đưa ra k (k ≥ 1) cặp điểm (s,t) với khoảng cách (O-clit) nhỏ nhất. Thuật tốn để xử lý những truy vấn này (Corral 2000) kết hợp những phép nối khơng gian với một phép tìm kiếm hàng xĩm gần nhất. 3.2.2. Xử lý truy vấn trong mạng khơng gian Papadias (2003) nghiên cứu những loại truy vấn trên cho cơ sở dữ liệu khơng gian. Trong cơ sở dữ liệu mạng khơng gian, mạng được mơ hình hĩa bởi 1 đồ thị và được biểu diễn dưới dạng các danh sách điểm kề. Các thực thể khơng gian được đánh chỉ số độc lập bởi R-trees và được ánh xạ vào cạnh gần nhất trong quá trình xử lý truy vấn. Khoảng cách của 2 điểm được định nghĩa là khoảng cách của đường dẫn gần nhất nối 2 điểm đĩ trong đồ thị. Cĩ hai frameworks được đề xuất để giảm bớt khơng gian tìm kiếm là khơng gian O-clit hạn chế và mạng mở rộng. Frameworks khơng gian O-clit hạn chế sử dụng thuộc tính đường bao thấp của khơng gian Ơ-clit. Với một truy vấn dãy tìm tất cả các đối tượng trong mạng cách q một khoảng e. Phương thức hạn chế O-clit đầu tiên thực hiện try vấn dãy thơng thường ở các tập dữ liệu thực thể và trả về mơt tập các đối tượng S’ cách q một khoảng e. Nhờ thuộc tính đường bao thấp, S’ sẽ chứa tất cả các điểm phù hợp. Sau đĩ, khoảng cách thực (khoảng các mạng – network distance) của tất cả các điểm trong S’ được tính, và những điểm khơng phù hợp được loại bỏ. Phương pháp tương tự cũng được sử dụng cho những loại truy vấn khác, kết hợp với 1 vài bước tối ưu để giảm số lượng của việc tính tốn khoảng cách mạng. Frameworks mở rộng mạng thực hiện xử lý truy vấn trực tiếp trên mạng mà khơng sử dụng thuộc tính bao thấp của khơng gian O-clit. Với ví dụ ở trên, đâu tiên mở rộng mạng xung quanh điểm truy vấn và tìm tất cả các cạnh nằm trong khoảng e từ q. Sau đĩ thực một phép giao để lấy những thực thể nằm trên những cạnh này. Các truy vấn hàng xĩm gần nhất, phép nối, và cặp gần nhất cũng được xử lý với phương pháp tương tự. 3.2.3. Tìm đường đi trong cĩ khơng gian cĩ chướng ngại vật Những vấn đề về tìm đường đi trong khơng gian cĩ các chướng ngại vật đã được nghiên cứu rộng rãi trong Computational Geometry (de Berg et al. 1997). Bài tốn đặt ra: Cho một tập O các chướng ngại vật khơng giao nhau (các đa giác) trong khơng gian 2D, 1 điểm bắt đầu pstart và 1 điểm đích pend, mục đích là tìm đường dẫn ngắn nhất từ pstart đến pend mà khơng cắt qua chướng ngại vật nào. Đồ thị G tương ứng như trong hình 3(b). Đồ thị được tạo bởi các đỉnh của các chướng ngại vật và 2 điểm pstart và pend. Hai node ni và nj trong G được nối với nhau bởi một cạnh nếu và chỉ nếu cạnh đĩ khơng cắt chướng ngại vật. Vì các cạnh của chướng ngại vật khơng cắt chính nĩ, do đĩ chúng cũng chứa trong G. 29 Hình 10 – Đồ thị G trong khơng gian cĩ chướng ngại vật Trong Lozano-Pérez and Wesley 1979, đã định nghĩa đường dẫn ngắn nhất là đường chỉ chứa những cạnh của đồ thị. Do đĩ, vấn đề được giải quyết bởi: (1) xây dựng đồ thị G và (2) tính tốn khoảng cách ngắn nhất giữa pstart và pend trong G. Việc tính tốn khoảng cách ngắn nhất giữa pstart và pend được thực hiện bằng cách sử dụng thuật tốn tìm đường đi ngắn nhất Dijkstra. Vì vậy, vấn đề chỉ cịn là xây dựng đồ thị G. Truy vấn cĩ chướng ngại vật Cho một tập các chướng ngại vật O, 1 tập các thực thể P, một điểm truy vấn q và khoảng cách là e, một truy vấn cĩ chướng ngại vật (obstacle range – OR) trả về tất cả các thực thể trong P cĩ khoảng cách thực với q là e. Thuật tốn OR xử lý truy vấn này như sau: (1) Xây dựng tập các ứng cử P’ cĩ khoảng cách O-clit đến q ≤ e; (2) Xây dựng tập O’ các chướng ngại liên quan đến truy vấn; (3) Xây dựng một đồ thị cục bộ G’, chứa các thành phần của P’ và O’; (4) Loại bỏ những đối tượng khơng đạt trong P’ bằng cách đánh giá khoảng cách thực của chúng cho mỗi ứng cử sử dụng đồ thị G’. Xem xét ví dụ trong hình 12(a) với e=6. Những vùng màu sẩm là các chướng ngại vật và các điểm là các thực thể. Tập P’ chứa các thực thể giao với hình trịn C tâm q với bán kính e. Để loại bỏ các thực thể khơng đúng, chúng ta cần cĩ được các chướng ngại vật thích hợp. Nhận xét rằng: những chướng ngại vật giao với hình trịn C là những chướng ngại vật cĩ thể liên quan đến kết quả của truy vấn. Theo thuộc tính đường bao thấp O-clit, bất kỳ đường dẫn nào bắt đầu ở q và kết thúc ở đỉnh bất kỳ của một chướng ngại vật nằm ở ngồi C thì sẽ cĩ độ dài lớn hơn e. Vì vậy, các chướng ngại vật này sẽ bị loại bỏ. Do đĩ tập O’ các chướng ngại thích hợp cĩ thể nhận được bởi 1 truy vấn dãy (tâm tại q với bán kính e) trên R-tree của O. Đồ thị cục bộ G’ được vẽ ở hình 12(b). Để xây dựng đồ thị ta sử dụng thuật tốn của (Sharir and Schorr 1984). 30 Hình 12 – Truy vấn cĩ chướng ngại vật Bước cuối cùng là đánh giá khoảng cách thực của q đến mỗi ứng cử. Để tối ưu việc tính tốn, OR mở rộng đồ thị xung quanh điểm truy vấn q chỉ một 1 lần cho tất cả các ứng cử sử dụng phương thức tree traversal tương tự như trong thuật tốn Dijkstra. Đặc biệt, OR chứa một hàng đợi ưu tiên Q. Q được khởi tạo chứa các hàng xĩm của q, sắp xếp theo khoảng cách thực của chúng đến q. Vì những hàng xĩm này nối trực tiếp đến q, khoảng cách thực của chúng dO(ni,q), với 1≤i≤4, bằng khoảng cách O-clit dE(ni,q). Node đầu tiên (n1) được đưa vào hàng đợi và chèn vào tập các node đã thăm V. Với mỗi hàng xĩm chưa được thăm nx của n1, dO(nx,q) được tính (sử dụng n1 như một node trung gian). Nếu dO(nx,q) ≤ e, nx được chèn vào Q. Truy vấn hàng xĩm gần nhất Cho một điểm truy vấn q, một tập chướng ngại vật O và một tập thực thể P, một truy vấn hàng xĩm gần nhất trong khơng gian cĩ chướng ngại vật (obstacle nearest neighbour - ONN) trả về k đối tượng trong P cĩ khoảng cách thực nhỏ nhất đến q. Ý tưởng chung của thuật tốn ONN như sau: đầu tiên, lấy ra hàng xĩm O-clit gần nhất của q (a) (sử dụng 1 thuật tốn tiền lời - e.g.Hjaltason and Sammet 1999), và dO(a,q) được tính. Do thuộc tính đường bao thấp O-clit, các đối tượng cĩ khoảng cách thực nhỏ hơn a sẻ nằm trong khoảng dEmax = dO(a,q). Sau đĩ, hàng xĩm O-clit (f) trong khoảng dEmax được lấy ra, và khoảng cách thực của nĩ (dO(f,q)) được tính. Vì dO(f,q) < dO(a,q), f trở thành NN hiện tại, và dEmax được cập nhật thành dO(f,q). 31 Hình 13 – Truy vấn hàng xĩm gần nhất trong khơng gian cĩ chương ngại vật Thuật tốn dừng khi khơng cịn hàng xĩm O-clit gần nhất nào của q trong khoảng dEmax. Phép nối e-distance Cho một tập các chướng ngại vật O, hai tập thực thể S, T và giá trị e. Một truy vấn nối e-distance (Ostacle e-distance join – ODJ) trả về tất cả các cặp thực thể (s,t) với sєS, tєT và dO(s,t) ≤ e. Dựa trên thuộc tính đường bao thấp Ơ-clit, thuật tốn ODJ được thực hiện như sau: (1) Thực hiện một phép nối O-clit e-distance trên các cây R- trees của S và T để nhận được các cặp thực thể (s,t) với dE(s,t) ≤ e; (2) Tính tốn cho dO(s,t) cho mỗi cặp ứng cử (s,t) và xĩa những cặp khơng phù hợp. 32 3.3. Tìm hiểu về PostGIS 3.3.1. Giới thiệu PostGIS là một phần mở rộng của cơ sở dữ liệu đối tượng quan hệ PostgreSQL cho phép các đối tượng GIS được lưu trữ trong CSDL. PostGIS được phát triển bởi Refractions Research Inc. PostGIS hổ trợ lưu trữ các đối tượng GIS cơ bản - như được định nghĩa bởi OpenGIS. PostGIS biểu diễn các đối tượng khơng gian theo hai dạng chuẩn: chuẩn định dạngWell-Know-Text (WKT) và định dạng Well-Know Binary (WKB). Ngồi ra khi lưu trữ các đối tượng khơng gian, OpenGIS yêu cầu trong dữ liệu lưu phải chứa một tham chiếu đến hệ thống nhận diện khơng gian (SRID). 3.3.2. Sử dụng các chuẩn OpenGIS OpenGIS định nghĩa các loại đối tượng GIS chuẩn, các chức năng để thao tác với chúng, và một tập các bảng meta-data. Trong PostGIS cĩ 2 bảng meta-data theo chuẩn của OpenGIS là: SPATIAL_REF_SYS và GEOMETRY_COLUMNS. Tạo một bảng với dữ liệu khơng gian, được thực hiện theo 2 bước: • Tạo một bảng non-spatial bình thường • Thêm cột khơng gian vào bảng sử dụng hàm “AddGeometryColumn” của OpenGIS Cú pháp là: AddGeometryColumn( , , , , , ) Hoặc: AddGeometryColumn( , , , , ) 3.3.3. Import dữ liệu GIS Cĩ hai cách để đưa dữ liệu vào một csdl PostGIS/PostgreSQL: sử dụng các câu lệnh dạng SQL hoặc sử dụng chương trình tải shapefile – sh2gpsql. 3.3.4. Xuất bản dữ liệu GIS Dữ liệu trong PostGIS/PostgreSQL cũng cĩ thể được xuất bản bằng câu lệnh SQL hoặc các trình loader/dumper shapefile. 33 3.3.5. Tạo indexs Đánh chỉ số cho phép các trình lên kế hoạch của một CSDL đưa ra những phương pháp xử lý truy vấn hiệu quả giúp giảm thời gian thực hiện, cũng như tài nguyên hệ thống. Với các CSDL thơng thường cấu trúc đánh chỉ số phổ biến là B- trees. Nhưng với CSDL khơng gian, phương pháp đánh chỉ số B-tree khơng cịn phù hợp. PostgreSQL mặc định hổ trợ 3 loại đánh chỉ số: B-Tree indexes, R-Tree indexes và GiST indexes. • B-Trees được sử dụng cho những dữ liệu cĩ thể sắp xếp theo 1 trục; ví dụ: số, ký tự, ngày tháng. Dữ liệu GIS khơng thể được sắp xếp một cách logic theo trục, do đĩ B-Tree indexes khơng phù hợp. • R-Trees chia dữ liệu thành những hình chử nhật, và những hình chử nhật con, và những hình chử nhật con, … R-Tree được sử dụng cho một số CSDL khơng gian để đánh chỉ số CSDL khơng gian, nhưng hiệu năng của R-tree trong PosstgreSQL khơng mạnh bằng GiST. • GiST (Generalized Search Trees) indexes chia dữ liệu thành "things to one side", "things which overlap", "things which are inside" và cĩ thể được sử dụng trên một tập rơng các loại dữ liệu, bao gồm cả dữ liệu GIS. PostGIS sử dụng 1 R-Tree index trên đỉnh của GiST để đánh chỉ số dữ liệu GIS. Cú pháp để xây dựng một GiST index trên một cột “geometry” là : CREATE INDEX [indexname] ON [tablename] USING GIST ( [geometryfield] ); 3.3.6. Một số truy vấn spatial SQL đơn giản Trong PostGIS cung cấp các hàm xử lý khơng gian, giúp cho việc truy vấn khơng gian đạt hiệu quả. Để sử dụng PostGIS hiệu quả yêu cầu phải biết về các hàm khơng gian đang cĩ, và sử dụng một cách hợp lý để cĩ thể đạt được hiệu năng truy vấn tốt. Các ví dụ dưới đấy sẽ sử dụng 2 bảng, 1 bảng các đường đường phố, và 1 bảng các đa giác đường biên đơ thị. Bảng các đường phố bc_roads: Column | Type | Description --------+-----------------+------------------------- gid |integer | Unique ID name |character varying| Road Name the_geom| geometry | Location Geometry (Linestring) 34 Bảng các đa giác đường biên đơ thị bc_municipality: Column | Type |Description --------+-----------------+------------------------ gid |integer |Unique ID code |integer |Unique ID name |character varying|City / Town Name the_geom| geometry |Location Geometry (Polygon) Tổng số chiều dài của các đường là bao nhiều (km) - sử dụng hàm ST_Length để tính độ dài đường? SELECT sum(ST_Length(the_geom))/1000 AS km_roads FROM bc_roads; Diện tích của thành phố Prince George là bao nhiêu (hectar) – sử dụng hàm ST_Area để tính diện tích một đa giác ? SELECT ST_Area(the_geom)/10000 AS hectares FROM bc_municipality WHERE name = ’PRINCE GEORGE’; Khu vực nào là rộng nhất trong tỉnh (theo diện tích) ? SELECT name,ST_Area(the_geom)/10000 AS hectares FROM bc_municipality ORDER BY hectares DESC LIMIT 1; Độ dài của đường đầy đủ chứa trong mỗi đơ thị là gì - hàm ST_Contains kiểm tra xem một đối tượng geometry cĩ được chứa trong một đối tượng geometry khác hay khơng? SELECT m.name,sum(ST_Length(r.the_geom))/1000 as roads_km FROM bc_roads AS r,bc_municipality AS m WHERE ST_Contains(m.the_geom,r.the_geom) 35 GROUP BY m.name ORDER BY roads_km; Kết quả trả về: name | roads_km ----------------+------------------------------ SURREY | 1539.47553551242 VANCOUVER | 1450.33093486576 LANGLEY DISTRICT| 833.793392535662 BURNABY | 773.769091404338 PRINCE GEORGE | 694.37554369147 Tạo một bảng lưu tất cả các đường trong thanh phố Prince George – hàm ST_Intersects trả về các đối tượng geometry giao nhau. CREATE TABLE pg_roads as SELECT ST_Intersection(r.the_geom, m.the_geom) AS intersection_geom, ST_Length(r.the_geom) AS rd_orig_length, r.* FROM bc_roads AS r,bc_municipality AS m WHERE m.name = ’PRINCE GEORGE’ AND ST_Intersects(r.the_geom, m.the_geom); 36 CHƯƠNG 4. XÂY DỰNG ỨNG DỤNG 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. 4.1. Một số ứng dụng dẫn đường phổ biến 4.1.1. Việt map Việt map cung cấp các ứng dụng cho các thiết bị di động tích hợp GPS (hoặc khơng) với các chức năng dẫn đường hồn thiện, giao diện thân thiện, và chi tiết cho các bản đồ tại Việt Nam. Các dịch vụ cơ bản mà một ứng dụng dẫn đường GPS của VietMap cung cấp: - Bản đồ điện tử 64 tỉnh thành Việt Nam với thơng tin số nhà, thơng tin giao thơng được cập nhật liên tục. - Thơng tin phong phú với các điểm du lịch, nhà hàng, khách sạn, ngân hàng, trạm xăng,... trên tồn quốc. - Định vị, tìm đường và hướng dẫn lộ trình bằng hệ thống định vị tồn cầu GPS. - Giao diện và giọng nĩi hướng dẫn lộ trình bằng tiếng Anh, tiếng Việt hoặc tiếng Hoa. - Chức năng lưu các điểm ưa thích cá nhân. Hình 14 – Vietmap navigator cho ơ tơ Tuy nhiên các ứng dụng này chỉ cung cấp dữ liệu bản đồ cho các vùng trong nước, do đĩ khơng thể sử dụng khi đi ra nước ngồi. Và các ứng dụng này là các ứng dụng mất phí. 37 4.1.2. Pguider Pguider cũng cung cấp các ứng dụng bản đồ khá hồn chỉnh cho các thiết bị di động cĩ GPS. Cung cấp giao diện thân thiện, dễ sử dụng và các chức năng hướng dẫn đường đi đầy đủ: - Hiển thị bản đồ, với CSDL bản đồ của 18 tĩnh thành trên cả nước - Chức năng tìm địa điểm, chức năng tìm đường phố. - Chức năng hiển thị thơng tin vị trí theo GPS - Chức năng dẫn đường - Chức năng quản lý các điểm ưa thích Hình 15 – Pguider trên windows mobile Pguider cung cấp các chức năng cũng như dữ liệu khơng tốt như của Vietmap, tuy nhiên đây là một ứng dụng miễn phí. 4.1.3. GoogleMaps cho mobile GoogleMaps for mobile, cung cấp khá đầy đủ các chức năng bản đồ cho các thiết bị di động. Nhất là các thiết bị chạy hệ điều hành Android. - Hiển thị bản đồ tồn thế giới. 38 - Hướng dẫn đi đường (Navigation) chỉ ở các máy Android - Tìm đường đi (cĩ cả tìm kiếm bằng dọng nĩi) - Cung cấp hiện trạng giao thơng (chỉ ở một số thành phố) - Xây dựng bản đồ cá nhân - Cung cấp chết độ streetview ở một số thành phố. Hình 16 – GoogleMaps for mobile Tuy nhiên các ứng dụng thực sự chỉ mới cĩ ở Android, Iphone, Nokia S60, Windows mobile. Các dịng thiết bị khác cĩ được là do truy cập vào trang map.google.com, do đĩ các thiết bị này phải cĩ một browser hiệu quả. 4.2. Các chức năng của chương trình Hiện nay với sự phát triển mạnh của cơng nghệ phần cứng, các thiết bị di động được trang bị các bộ vi xử lý cĩ hiệu năng cáo và đã cĩ thể xử lý những thao tác phức tap. Các thiết bị đã được cung cấp các chip wireless giúp cho việc kết nối Internet dễ dàng và hiệu quả. Ở Việt Nam hiện nay, đặc biệt là tại hà nội, các điểm truy nhập wireless xuất hiện nhiều và dịch vụ 3G cũng đã được phát triên giúp cho người sử dụng các thiết bị dễ dàng kết nối Internet mọi lúc mọi nơi. Các chức năng chi tiết mà ứng dụng cung cấp: - Được xây dựng để hoạt động trên các thiết bị mobile, cĩ tích hợp GPS hoặc khơng. - Hiển thị bản đồ, di chuyển ở các mức zoom level khác nhau 39 - Nếu thiết bị cĩ tích hợp GPS, xác định vị trí hiện tại của người dùng thơng qua GIS, hiển thị vị trí hiện tại của người dùng. - Cung cấp cơng cụ tìm đường, hiển thị đường đi. - Cup cấp thơng tin hưởng dẫn đi đường cho người dùng. Với các thiết bị cĩ hổ trợ GPS, cung cấp chức năng hướng dẫn theo thời gian thực. 4.3. Mơ hình đề xuất Tham khảo một số ứng dụng về bản đồ trên các thiết bị di động, tơi đưa ra một ý tưởng để xây dựng một ứng dụng trợ giúp tìm đường cho người dùng, sử dụng hệ quản trị CSDL PostgreSQL quản lý các dữ liệu địa lý, và thực hiện các truy vấn của người dùng sau đĩ trả về kết quả. Hình 17 - Mơ hình chương trình Nhưng do thời gian thực hiện cĩ hạn, do đĩ tơi đã sử dụng server của GoogleMaps để làm Server cung cấp các dữ liệu địa lý cũng như xử lý các truy vấn địa lý của mình. Tơi đã đưa ra hai ý tưởng: - Cài đặt một Server hổ trợ chạy Javascript, sau đĩ sẽ sử dụng thư viện GoogleAPI của Google thực hiện các truy vấn của client, và trả về kết quả cho client. - Sever nhận yêu cầu từ mobile client, sau đĩ thực truy vấn tương ứng lên server của Google, lấy về dữ liệu dạng KML, phân tích file KML và trả về cho client. Để đơn gian, tơi đã lựa chọn ý tưởng thứ 2, tạo một Script PHP ở server nhận request từ mobile client, sau đĩ gửi request tương ứng lên map server của Google lấy về kết quả ở dạng file kml, phân tích và gửi về kết quả cần thiết ở dạng XML cho mobile client. Ứng dụng trên Mobile Wireless network, 3G, GPRS Server Hiển thị HTTP XML Parser Webservice CSDL - PostgreSQL Result SQLRequest 40 Google tạo ra định dạng KLM để hiển thị các dữ liệu địa lý trên các ứng dụng client của mình, ví dụ như Google Earth, Google Maps. KML sử dụng cậu trúc tuân theo chuẩn XML. Hình 18 – File KML Cấu trúc của file KML được chia ra làm các phần như sau: • Phần mào đầu XML • Mơ tả khơng gian tên KML • Mơ tả placemark • Tên của placemark • Khung nhìn của placemark • Khung nhìn mặc định của placemark (trong trường hợp này nĩ được chuyển đổi bởi người dùng) • Định nghĩa Style cho placemark, chi tiết nơi mà hình ảnh được định vị và vị trí của nĩ. • Chuyển đổi nếu các place mark được lấy ra • Các loại tọa độ mà placemark cĩ thể sử dụng • Vị trí trên placemark trên bề mặt quả đất Để giảm bớt dử liệu truyền tải về client cũng như giảm độ phức tạp khi phân tích file KML được trả về. Việc phân tích file KML sẻ được thực hiện trên một server hổ trợ PHP – một ngơn ngử cung cấp xứ lý file XML dễ dàng, sau đĩ dữ liệu chọn lọc sẽ được gửi về cho mobile client dưới dạng file XML đơn giản hơn, loại bỏ các dữ liệu khơng cần thiết, cĩ dạng: ði từ ðai học Quốc gia đến đường Trường Chinh ði về hướng nam đường Xuân Thủy đi 3km Rẽ phải ở đường Láng đi 3km 41 Tiếp tục lên đường Trường Chinh đi 1km 0 4.4. Lựa chọn ngơn ngữ Hiện nay cĩ rất nhiều ngơn ngữ lập trình được sử dụng để lập trình ứng dụng cho các thiết bị di động, cho phép khai thác hầu hết các tính năng về đồ họa cũng như kết nối của thiết bị. Tuy nhiên để phát triển ứng dụng cĩ thể sử dụng được trên nhiều thiết bị, thì J2ME là một lựa chọn tối ưu. Kiến trúc của J2ME Hình 19 – Kiến trúc của J2ME Giới thiệu các thành phần trong nền tảng J2ME: KVM: Cơ chế thực thi của một ứng dụng Java là chạy trên một máy ảo java (java virtual machine). Máy ảo này cĩ chức năng chuyển các mã dạng bytecode sang mã máy. Với các thiết bị dạng CLDC, Sun cài đặt một phiên bản thu nhỏ hơn dành cho các thiết bị này đĩ là KML. Chính nhờ tầng này, mà các ứng dụng cĩ thể chạy trên các thiết bị khác nhau. Định nghĩa về Configuration (Cấu hình): là đặc tả định nghĩa một mơi trường phần mềm cho một dịng các thiết bị được phân loại bởi tập hợp các đặc tính, như: Kiểu và số lượng bộ nhớ, kiểu và tốc độ bộ vi xử lý, kiểu mạng kết nối. Hiện nay Sun đã đưa ra 2 dạng Configuration: - CLDC-Connected Limited Device Configuration (Cấu hình thiết bị kết nối giới hạn): được thiết kế để nhắm vào thị trường các thiết bị cấp thấp (low-end). - CDC- Connected Device Configuration (Cấu hình thiết bị kết nối): CDC được đưa ra nhắm đến các thiết bị cĩ tính năng mạnh hơn dịng thiết bị thuộc CLDC nhưng vẫn yếu hơn các hệ thống máy để bàn sử dụng J2SE. Cả 2 dạng Cấu hình kể trên đều chứa máy ảo Java (Java Virtual Machine) và tập hợp các lớp (class) Java cơ bản để cung cấp một mơi trường cho các ứng dụng J2ME. Tuy nhiên, Với các thiết bị cấp thấp, do hạn chế về tài nguyên như bộ nhớ và bộ xử lý nên khơng thể yêu cầu máy ảo hổ trợ tất cả các tính năng như với máy ảo 42 của J2SE. Định nghĩa về Profile: Profile mở rộng Configuration bằng cách thêm vào các class để bổ trợ các tính năng cho từng thiết bị chuyên biệt. Mộ số profile phổ biến hiện nay: - Mobile Information Device Profile (MIDP): profile này sẽ bổ sung các tính năng như hỗ trợ kết nối, các thành phần hỗ trợ giao diện người dùng … vào CLDC. Profile này được thiết kế chủ yếu để nhắm vào điện thọai di động với đặc tính là màn hình hiển thị hạn chế, dung lượng chứa cĩ hạn. Do đĩ MIDP sẽ cung cấp một giao diện người dùng đơn giản và các tính năng mạng đơn giản dựa trên HTTP. Cĩ thể nĩi MIDP là profile nổi tiếng nhất bởi vì nĩ là kiến thức cơ bản cho lập trình Java trên các máy di động (Wireless Java). - PDA Profile: tương tự MIDP, nhưng với thị trường là các máy PDA với màn hình và bộ nhớ lớn hơn. - Foundation Profile: cho phép mở rộng các tính năng của CDC với phần lớn các thư viện của bộ Core Java2 1.3. Ngồi ra cịn cĩ Personal Basis Profile, Personal Profile, RMI Profile, Game Profile. Hiện nay hầu hết các dịng điện thoại hổ trợ profile MIDP là phổ biến. Do đĩ tơi lựa chọn xây dựng ứng dụng cho các thiết bị hổ trợ profile MIDP. 4.5. Tìm hiểu cơ chế hoạt động của hệ thống GPS GPS, hệ thống định vị tồn cầu, được cấu thành như một chịm sao (cĩ nghĩa cấu tạo của một nhĩm hay một hệ thống) của quỹ đạo vệ tinh mà, kết hợp với thiết bị ở mặt đất, cho phép người sử dụng xác định vị trí chính xác của họ bất kỳ lúc nào trên bề mặt trái đất. Nguyên lý xác định toạ độ của hệ thống GPS và Glonass dựa trên cơng thức cơ bản: Quãng_đường = Vận_tốc × Thời_gian. Vệ tinh phát ra các tín hiệu bao gồm vị trí của chúng, thời điểm phát tín hiệu. Máy thu tính tốn được khoảng cách từ các vệ tinh, giao điểm của các mặt cầu cĩ tâm là các vệ tinh, bán kính (là thời gian tín hiệu đi từ vệ tinh đến máy thu nhân vận tốc sĩng điện từ) là toạ độ điểm cần định vị. Hệ thống NAVSTAR gồm 24 vệ tinh với 6 quỹ đạo bay. Các vệ tinh này hoạt động ở quỹ đạo cĩ độ cao 20.200km ở gĩc nghiêng 55 độ và với thời gian 12/quỹ đạo. 43 Hình 20 – Hệ thống vệ tinh GPS Hệ thống GLONASS gồm 24 vệ tinh, 8 vệ tinh cho một quỹ đạo bay gồm 3 quỹ đạo. Các vệ tinh hoạt động với quỹ đạo cĩ độ cao 19,100 km orbits ở gĩc nghiêng 64.8 độ và 11 giờ 15 phút/ quỹ đạo. 4.5.1. Đo khoảng cách từ máy thu đến các vệ tinh Máy thu cĩ thể tính tốn được khoảng cách dựa vào thời gian cần thiết để tín hiệu từ vệ tinh truyền đến được máy thu. Vào một thời điểm nào đĩ, một vệ tinh bắt đầu truyền một chuỗi tín hiệu dài, được gọi là mã ngẫu nhiên giả. Máy thu cũng bắt đầu tạo ra chuỗi mã giống hệt vào cùng thời điểm. Khi tín hiệu từ vệ tinh truỳên đến máy thu, chuỗi tín hiệu đĩ sẽ bị trễ một chút so với chuỗi do máy thu tạo ra. Chiều dài khoảng thời gian trễ này chính là thời gian truyền của tín hiệu từ vệ tinh. Máy thu nhân thời gian này với tốc đọ ámh sáng để xác định quãng đường truyền tín hiệu. Giả sử rằng tín hiệu truyền trên đường thẳng, đây chính là khoảng cách từ vệ tinh đến máy thu. Để thực hiện phép đo này, chúng ta phải chắc chắn là đồng hồ trên vệ tinh và trong máy thu phải đồng bộ với nhau. Một sai số 1 mili giây sẽ dẫn đến sai số là 300 ngàn mét, một sai số rất lớn. Do đĩ, độ chính các tối thiểu cho các máy thu phải là cỡ nano giây (10-9s). Để cĩ độ chính xác như vậy, phải trang bị đồng hồ nguyên tử cho khơng chỉ các vệ tinh mà cịn cho cả máy thu. Nhưng giá đồng hồ nguyên tử rất cao do đĩ phương pháp này thực sự khơng khả thi. Cĩ một phương pháp được đưa ra, đĩ là trên mỗi vệ tinh trang bị một đồng hồ nguyên tử, con trên thiết bị GPS vẫn trang bị đồng hồ bình thường. Trên lý thuyết thì 4 mặt cầu phải giao nhau tại 1 điểm. Nhưng do sai số đồng hồ bình thường, 4 mặt cầu đã khơng cho 1 giao điểm duy nhất. Vì thời gian sai số gây ra bởi đồng hồ trên máy thu là như nhau ∆t với tất cả các vệ tinh, máy thu cĩ thể dễ dàng loại trừ sai số này bằng cách tính tốn ra lượng hiệu chỉnh cần thiết để 4 mặt cầu giao nhau tại một điểm. Dựa vào đĩ, máy thu tự động điều chỉnh đồng hồ cho đồng bộ với đồng hồ nguyên tử trên vệ 44 tinh. Nhờ đĩ mà đồng hồ trên máy thu cĩ độ chính xác gần như tương đương với đồng hồ nguyên tử. 4.5.2. Xác định vị trí hiện tại của các vệ tinh Để xác định vị trị hiện tại của các vệ tinh trong bộ nhớ của mỗi máy thu đều cĩ chứa một bảng tra vị trí tính tốn của tất cả các vệ tinh vào bất kỳ thời điểm nào gọi là Almanac. Tuy nhiên lực hút của mặt trăng, mặt trời cĩ ảnh hưởng nhất định làm thay đổi quĩ đạo của các vệ tinh, do đĩ các vệ tinh liên tục được theo dõi để cĩ thể xách định vị trí chính xác, các thơng số hiệu chỉnh sẽ được truyên đến các máy thu thơng qua tín hiệu từ vệ tinh. Sau khi máy thu đã thu nhận và xử lý thơng tin, máy sẽ cho biết vĩ độ, kinh độ và cao độ của vị trí hiện thời. Để làm cho việc định vị thân thiện hơn, hầu hết các máy thu đều thể hiện các thơng tin này dưới dạng các điểm trên bản đồ được chứa sẵn trong máy. Trong J2ME thơng tin này cĩ thể lấy được bởi lớp LocationProvider. 4.6. Thử nghiệm ứng dụng 4.6.1. Các lớp chính của chương trình - Gmidlet – Là lớp chương trình chính, cung cấp đối tượng hiện thị. Tạo đối tượng GoogleSimpleCanvas để hiển thị bản đồ. - GoogleSimpleCanvas – Lớp quan trọng nhất: thừa kết từ lớp Canvas, thực hiện truy xuất đến server GoogleMaps lấy về bản đồ ở khu vực mong muốn dưới dạng ảnh .PNG. Thực hiện nắm bắt các tương tác người dùng và cung cấp kết quả: Yêu cầu zoom, move bản đồ, tìm đường. - Point – Là lớp lưu trữ tọa độ của các ngã rẻ khi thực hiện tìm đường - getDirections – Lớp thực hiện kết nối đến server, gửi yêu cầu tìm đường, và nhận về file Xml chứa kết quả. Phân tích file Xml lấy ra các điểm đi qua của đường, lưu vào vector Path, và hiển thị đường đi lên bản đồ. - Retriever: Thực hiện lấy thơng tin GPS của người dùng. 4.6.2. Screenshot của chương trình Khi khởi động chương trình, nếu máy tích hợp GPS và người dùng cho phép sử dụng GPS thì bản đồ sẻ được đặt trung tâm tại vị trí người dùng đang đứng. Nếu khơng vị trí trung tâm sẻ là trung tâm của Hà Nội 45 a - Cĩ GPS b - Khơng cĩ GPS Hình 21 – Giao diện chương trình ban đầu Điểm màu xanh hiển thị vị trí hiện tại của người dùng (nếu thiết bị cĩ hổ trợ GPS). 46 Hình 22 – Hướng dẫn sử dụng - 1. Bỏ đường đi: chương trình vẽ đường đi tìm thấy cho người dùng lên bản đồ, khi người dùng khơng muốn hiển thị đường đi này nữa, chức năng bỏ đường đi cho phép xĩa bỏ đường đi này. - 2. Hướng dẫn: khi đã tìm thấy đường đi cho người dùng, các thơng tin hướng dẫn đường đi sẽ được hiển thị ở Form hướng dẫn. - 3. Tìm đường: Hiển thị Form tìm đường để người dùng cĩ thể nhập thơng tin tìm đường - 4.Vị trí: cho phép xác định lại vị trí người dùng thơng qua GPS của máy. - Người dùng cĩ thể zoom, di chuyển bản đồ bằng phím 1, 3 và các phím mũi tên Khi người dùng chọn chức năng tìm đường, khung hiển thị cho phép người dùng nhập thơn tin tìm đường. Điểm bắt đầu cĩ thể là vị trí hiện tại của người dùng, hoặc là một điểm bất kì do người dùng lựa chọn. Hình 23 – Form tìm đường - Người dùng cĩ thể sử dụng vị trí hiện tại, hoặc nhập vào thơng tin vị trí ban đâu. - Chương trình cho phép người dùng lựa chọn 1 trong hai loại phương tiện đi bộ hoặc đi bằng ơ tơ. 47 Sau khi tìm đường thành cơng, giao diện trả lại đường đi, được vẽ trên bản đồ: Hình 24 – Form kết quả - Kết quả tìm đường đi từ ĐH QG Hà Nội đến ĐH BK Hà Nội, với phương tiện : đi bộ. - Đường đi được vẽ lên bản đồ. - Thơng tin về khoảng cách đường đi, thời gian đi được hiễn thị ở một ticker ở phía dưới màn hình. Người dùng xem chi tiết hướng dẫn đường đi tại Form hướng dẫn của chương trình. Hình 25 – Form hướng dẫn lộ trình - Hiễn thị hướng dẫn đi đường cho người dùng - Độ dài đường đi, chổ rẽ 48 Khi người dùng lựa chọn tìm đường từ vị trí hiện tại, chương trình sẻ sử dụng thơng tin của GPS để thực hiện tìm đường. Hiện tại chương trình chỉ cung cấp hướng dẫn ở ngơn ngữ tiếng anh với chức năng này. Hình 26 – Tìm đường dựa trên GPS Hướng dẫn đi đường cho khách hàng ở hai thời điểm, khi vị trí của người dùng thay đổi . Hình 27 – chỉ dẫn lộ trình với GPS - Mỗi 2 phút, chương trình sẽ cập nhật lại đường đi cho người dùng, và thơng báo về đướng sắp phải đi, cũng như độ dài quảng đường cịn lại. Thơng tin được hiện thị ở ticker, và alert thơng báo. 49 4.7. Nhận xét Như kết quả ở trên, ta thấy ứng dụng đã cung cấp khả đầy đủ thơng tin về bản đổ cũng như là chức năng tìm đường, hướng dẫn lộ trình cho người dùng. Các thơng tin về hướng dẫn lội trình được cung cấp khá chi tiêt, cho phép người dùng cĩ thể xác định đường đi dễ dàng. Với trường hợp tìm đường đi cĩ xác định điểm đầu và điểm cuối, thơng tin được hiển thị bởi đường đi được vẽ trên bản đồ, cho phép người dùng dễ hình dung về đường đi. Các thơng tin về đi bao nhiêu m hay km, rẽ ở đâu, về hướng nào đều được cung cấp đầy đủ bằng tiếng việt. Với trường hợp tìm đường đi sử dụng điểm đầu là vị trí hiện tại thì khoảng 2 phút, chương trình lại hiển thị hướng dẫn lộ trình cho người dùng. Tuy nhiên ngơn ngữ được sử dụng chỉ mới bằng tiếng anh. Vì sử dụng dữ liệu cung cấp từ GoogleMaps, do đĩ kết quả trả về khơng thực sự được tốt. 50 CHƯƠNG 5. KẾT LUẬN 5.1. Kết quả đạt được Tìm hiểu về hệ thống thơng tin địa lý, đã cho tơi một cái nhìn tổng quan khá chi tiết về một hệ thống GIS. Các phương pháp lưu trữ dữ liệu để phù hợp với các đối tượng địa lý, phục vụ hiệu quả cho việc quản lý CSDL địa lý. Những kiến thức này sẽ cho phép tơi hình thành nên một phương pháp nào đĩ khi tiếp cận với việc xây dựng CSDL cho một kiểu dữ liệu mới. Ứng dụng bản đồ trên thiết bị di động tích hợp đã phần nào cung cấp được các chức năng cho một ứng dụng hổ trợ GIS cơ bản: hiển thị thơng tin GIS, hướng dẫn đường đi cho người dùng. Ứng dụng đã sử dụng được thơng tin GIS cung cấp bởi một nhà cung cấp (trong trường hợp này là GoogleMaps) để hổ trợ người dụng trong việc tìm đường. 5.2. Hạn chế Ứng dụng chỉ sử dụng được cho các thiết bị cĩ kết nối đến Internet. Vì sử dụng dữ liệu từ server qua kết nối Internet nên tốc độ phản hồi của ứng dụng cịn chậm, chưa thực sự hiệu quả. Thơng tin được cung cấp bởi Google, do đĩ ngơn ngữ tiếng Việt sử dụng chưa được hồn hảo. Ứng dụng hổ trợ tìm đường dựa vào vị trí người dùng vẫn đang sử dụng giao diện tiếng Anh, do đĩ sẽ gây khĩ khăn cho những người dùng khơng cĩ kiến thức về tiếng Anh. Kết quả tìm đường chưa là tối ưu, do kết quả cung cấp của Google chưa được hồn hảo. Người dùng phải biết rõ điểm đầu và điểm cuối, kết quả mới cĩ hiệu quả. 5.3. Hướng phát triển Hướng phát triển đầu tiên của khĩa luận là hồn thiện ứng dụng cung cấp các chức năng tìm đường bằng cách nghiên cứu xây dựng một hệ thống thơng tin địa lý riêng dựa trên hệ quản trị CSDL PosstgreSQL. Ngồi ra việc tìm hiểu, đưa ra phương pháp caching để tăng tốc độ đáp ứng của chương trình khi di chuyển cũng là một hướng phát triển đáng quan tâm của khĩa luận. 51 TÀI LIỆU THAM KHẢO Tiếng Việt: [1] Lê Cơng Trung – Nghiên cứu mơ hình dịch vụ hướng vị trí trên hệ thống thơng tin địa lý. [2] Nguyễn Việt Hà – Tích hợp cơng nghệ GIS và GPS phục vụ cơng tác nghiệp vụ của CS 113 [3] Nguyễn Sơn Hải – Xây dựng hệ thống khai thác trực tuyến cơ sở dữ liệu địa lý. [4] Trần Anh Tú - Ứng dụng Mobile GIS trong xây dựng hệ thống quản lý điều hành mạng lưới BIDV Tiếng Anh: [5] Antonin Guttman – University of California Berkely: R-trees – a dynamic index structure for spatial searching [6] BECKER, B., KRIEGEL, H., SCHNEIDER, R. and SEEGER, B., 1990, The R*-tree: an efficient and robust access method. [7] DEBERG, M., VAN KREVELD, M., OVERMARS, M. and SCHWARZKOPF, O., 1997, Computa-tional Geometry, pp. 305 – 315 (Berlin: Springer). [8] Dimitris Papadias, Department of Computer Science HongKong University of Science and Technology – Query Processing in Spatial Network databases. [9] Hans-Peter Kriegel, Thomas Brinkhoff, Ralf Schneider – institute for Computer Science, University of Munich – Efficient Spatial Query Processing in Geographic Database Systems. [10] Hjaltason, G. and Samet, H., 1999 – Distance browsing in spatial databases. ACM Transactions on Databse Systems, 24, pp.265-318. [11] Jun Zhang, Dmitris papadias, Kyriakos mouratidis and zhu manli – School of Computer Engineering, Nayang Technological University, Nanyang Avenue, Singapore - Query processing in spatial databases containing obstacles [12] PostGIS manual [13] Sharir, M.and Schorr, A., 1984, On shortest paths in polyhedral spaces, In 16th Annual ACM Symposium on Theory of Computing.