Luận văn Xây dựng một ứng dụng bản đồ trên máy pocket pc 2002 (windows ce 3.0) cho phép hiển thị một bản đồ điện tử và cung cấp một số chức năng tìm kiếm thông tin

KH OA C NT T – Đ H KH TN TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP.HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM VÕ SỸ NAM – 9912616 ĐỖ LỆNH HÙNG SƠN – 9912064 XÂY DỰNG MỘT ỨNG DỤNG BẢN ĐỒ TRÊN MÁY POCKET PC 2002 (WINDOWS CE 3.0) CHO PHÉP HIỂN THỊ MỘT BẢN ĐỒ ĐIỆN TỬ VÀ CUNG CẤP MỘT SỐ CHỨC NĂNG TÌM KIẾM THÔNG TIN LUẬN VĂN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN TS. DƯƠNG ANH ĐỨC LÊ THỤY ANH TP. HCM, 2003 KH OA C NT T – Đ H KH TN KH OA C NT T – Đ H KH TN NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. KH OA C NT T – Đ H KH TN NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. .................................................................................................................................. KH OA C NT T – Đ H KH TN LỜI CÁM ƠN Luận văn của chúng em sẽ rất khó hoàn thành nếu không có sự truyền đạt kiến thức quí báu và sự hướng dẫn tận tình của Thầy Dương Anh Đức và thầy Lê Thụy Anh. Chúng em xin chân thành cám ơn sự chỉ bảo của các thầy. Chúng con xin gửi tất cả lòng biết ơn, sự kính trọng đến ông bà, cha mẹ, cùng toàn thể gia đình, những người đã nuôi dạy, đã cho chúng con niềm tin và nghị lực để vượt qua mọi khó khăn. Chúng em xin trân trọng cám ơn quý Thầy cô trong Khoa Công nghệ thông tin trường Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh đã tận tình giảng dạy, truyền đạt những kiến thức quý báu và tạo điều kiện cho chúng em được thực hiện luận văn này. Xin chân thành cám ơn sự giúp đỡ, động viên và chỉ bảo rất nhiệt tình của các anh chị đi trước và tất cả bạn bè. Các anh chị, các bạn luôn có mặt trong những thời điểm khó khăn nhất, tiếp thêm động lực và ý chí, giúp chúng tôi hoàn thành được luận văn. Mặc dù đã cố gắng nỗ lực hết sức mình, song chắc chắn luận văn không khỏi còn nhiều thiếu sót. Chúng em rất mong nhận được sự thông cảm và chỉ bảo tận tình của quý Thầy cô và các bạn. Tp.HCM, 7/2003 Nhóm sinh viên thực hiện Võ Sỹ Nam - Đỗ Lệnh Hùng Sơn KH OA C NT T – Đ H KH TN LỜI NÓI ĐẦU Ngày nay, trong tất cả các lãnh vực của đời sống kinh tế, xã hội, công nghệ thông tin được xem là một trong những ngành công nghệ mũi nhọn, đóng vai trò hết sức quan trọng, có thể tạo ra những bước đột phá mạnh mẽ. Công nghệ thông tin đang phát triển từng ngày, cả trong kĩ thuật phần cứng lẫn lĩnh vực phần mềm. Kích thước cũng như khả năng của các thiết bị ngày càng được cải thiện rất nhiều. Từ các máy tính có kích thước rất lớn như mainframe, hiện nay, trên thế giới đã xuất hiện các loại thiết bị hỗ trợ cá nhân di động, gọi là PDA (Personal Digital Assistant), hết sức nhỏ gọn và tiện lợi, đặc biệt đối với những người có nhu cầu di chuyển nhiều. Các thiết bị thông minh, không dây và thuận tiện này đang ngày càng khẳng định vị trí của mình với những đặc tính của nó. Pocket PC là một dạng thiết bị PDA rất phổ biến và đang được sử dụng rộng rãi trên thế giới với nhiều tiện lợi và các phần mềm hữu ích. Trên môi trường này, đã có rất nhiều ứng dụng được phát triển với mục đích hỗ trợ tối đa người sử dụng thường xuyên phải di chuyển nhiều, như sổ tay điện tử, xem phim, nghe nhạc, bản đồ du lịch điện tử... Tại thị trường Việt Nam, Pocket PC cũng đang ngày càng trở nên thông dụng hơn. Trong bối cảnh Việt Nam chuẩn bị đăng cai Đại hội Thể thao Đông Nam Á (SEA Games) lần thứ 22, chúng em nhận thấy việc cho ra đời một ứng dụng bản đồ điện tử trên Pocket PC là hết sức cần thiết, tại Việt Nam nói chung và Tp.Hồ Chí Minh nói riêng. Với ý tưởng trên, chúng em đã tập trung thực hiện đề tài “XÂY DỰNG MỘT ỨNG DỤNG BẢN ĐỒ TRÊN MÁY POCKET PC 2002 (WINDOWS CE 3.0) CHO PHÉP HIỂN THỊ MỘT BẢN ĐỒ ĐIỆN TỬ VÀ CUNG CẤP MỘT SỐ CHỨC NĂNG TÌM KIẾM THÔNG TIN” và đã xây dựng ứng dụng với dữ liệu là bản đồ Tp.Hồ Chí Minh. KH OA C NT T – Đ H KH TN Nội dung của luận văn được chia làm 7 chương: Chương 1: Mở đầu giới thiệu chung về đề tài, ý nghĩa và các mục tiêu của đề tài; trình bày các giải pháp và hướng nghiên cứu đã được thực hiện trong và ngoài nước. Chương 2: Tổng quan về Pocket PC và Windows CE 3.0 giới thiệu tổng quan về Pocket PC và Windows CE 3.0, môi trường sẽ sử dụng ứng dụng bản đồ. Chương này cũng giới thiệu về khả năng lập trình trên Pocket PC 2002 và Hệ điều hành nhúng Windows CE 3.0. Chương 3: Các vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC trình bày các vấn đề liên quan trực tiếp đến việc xây dựng một ứng dụng bản đồ điện tử trên Pocket PC 2002 (Windows CE 3.0) như hạn chế về tốc độ tính toán, hiển thị, vấn đề lưu trữ trên Pocket PC. Chương 4: Các giải pháp cho ứng dụng bản đồ trên Pocket PC giới thiệu và phân tích các giải pháp thực hiện đối với việc xây dựng ứng dụng bản đồ điện tử trên Pocket PC như hiển thị, tìm kiếm, giải pháp tiếng Việt. Chương 5: Tổ chức dữ liệu bản đồ trên Pocket PC trình bày về dữ liệu nguồn và các vấn đề liên quan tới phương diện tổ chức lưu trữ thông tin và dữ liệu Pocket PC. Các giải thuật để xây dựng và tổ chức lại dữ liệu từ dữ liệu nguồn cũng được giới thiệu trong chương này. Chương 6: Ứng dụng Pocket Map giới thiệu về ứng dụng bản đồ điện tử Tp.Hồ Chí Minh trên Pocket PC 2002, mô tả các khảo sát hiện trạng, đặc tả yêu cầu và các phân tích thiết kế cho một số chức năng chính của ứng dụng. Chương này cũng giới thiệu giao diện và cách sử dụng của một số chức năng chính của ứng dụng. Chương 7: Tổng kết tóm tắt lại các vấn đề đã được đặt ra trong luận văn, cách giải quyết, kết quả đạt được và đề ra một số hướng phát triển trong tương lai. KH OA C NT T – Đ H KH TN MỤC LỤC Danh sách hình................................................................................. i Danh sách bảng...............................................................................iii Một số khái niệm và thuật ngữ ........................................................v Chương 1 : Mở đầu........................................................................ 1 1.1 GIS, các ứng dụng và giải pháp về GIS ...........................................1 1.2 Ứng dụng GIS trên Pocket PC.........................................................2 1.3 Các giải thuật nghiên cứu về GIS....................................................3 1.4 Mục tiêu của đề tài ........................................................................3 Chương 2 : Tổng quan về Pocket PC và Windows CE 3.0.............. 5 2.1 Giới thiệu về các thiết bị PDA .........................................................5 2.2 Tổng quan về Windows CE.............................................................6 2.3 Tổng quan về Pocket PC ................................................................7 2.4 Khả năng lập trình trên Pocket PC và Windows CE 3.0......................8 Chương 3 : Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC .................................................................................. 20 3.1 Khả năng tính toán của Pocket PC ................................................20 3.2 Tốc độ và các hỗ trợ khả năng hiển thị .........................................21 3.3 Khả năng và hình thức lưu trữ ......................................................25 3.4 Cấp phát bộ nhớ .........................................................................28 3.5 Tương tác giữa người sử dụng và thiết bị ......................................29 Chương 4 : Các giải pháp cho ứng dụng bản đồ trên Pocket PC . 31 4.1 Yêu cầu chung ............................................................................31 4.2 Vấn đề tối ưu tốc độ hiển thị ........................................................31 4.3 Tìm đường đi ngắn nhất ..............................................................38 KH OA C NT T – Đ H KH TN 4.4 Tìm kiếm thông tin phi không gian................................................42 4.5 Giải pháp tiếng Việt trên môi trường Pocket PC..............................45 Chương 5 : Tổ chức dữ liệu bản đồ trên Pocket PC..................... 54 5.1 Dữ liệu nguồn .............................................................................54 5.2 Mối liên hệ giữa các file .MNT, .SHP và .DBF..................................60 5.3 Tổ chức lại dữ liệu.......................................................................61 5.4 Xây dựng dữ liệu Topology...........................................................72 Chương 6 : Ứng dụng PocketMap ............................................... 78 6.1 Khảo sát hiện trạng .....................................................................78 6.2 Phân tích và xác định yêu cầu ......................................................79 6.3 Đặc tả Use Case..........................................................................81 6.4 Sơ đồ lớp Class Diagram ..............................................................89 6.5 Mô tả các lớp ..............................................................................91 6.6 Các lưu đồ hoạt động ................................................................ 102 6.7 Thiết kế màn hình ..................................................................... 116 6.8 Cài đặt và thử nghiệm ............................................................... 123 6.9 Hướng dẫn sử dụng................................................................... 125 Chương 7 : Tổng kết.................................................................. 133 7.1 Kết luận.................................................................................... 133 7.2 Hướng phát triển....................................................................... 134 Tài liệu tham khảo....................................................................... 136 Phụ lục ....... ................................................................................ 139 KH OA C NT T – Đ H KH TN Danh sách hình Hình 2-1: Phân bố bộ nhớ trong Windows CE .........................................14 Hình 4-1: Đoạn thẳng giao vùng nhìn ....................................................33 Hình 4-2: Cung giao vùng nhìn..............................................................34 Hình 4-3: Lưu đồ vẽ đối tượng ..............................................................38 Hình 5-1: Liên hệ giữa cung và điểm .....................................................57 Hình 5-2: Liên hệ giữa đường và cung ...................................................57 Hình 5-3: Đường bao quận/huyện .........................................................64 Hình 6-1: UseCase tìm kiếm đường........................................................81 Hình 6-2: Usecase Tìm kiếm địa điểm ....................................................83 Hình 6-3: Tìm đường đi ngắn nhất.........................................................85 Hình 6-4: Usecase Tìm kiếm quận/huyện ...............................................87 Hình 6-5: Sơ đồ tổng quát ....................................................................89 Hình 6-6: Sơ đồ lớp dữ liệu ...................................................................89 Hình 6-7: Sơ đồ lớp vẽ..........................................................................90 Hình 6-8: Sơ đồ lớp sự kiện...................................................................90 Hình 6-9: Lớp dữ liệu đường .................................................................92 Hình 6-10: Lớp GraphData ....................................................................94 Hình 6-11: Lớp DistrictData...................................................................96 Hình 6-12: Lớp PlaceData .....................................................................97 Hình 6-13: Lớp RoadView .....................................................................98 Hình 6-14: Lớp DistrictView...................................................................99 Hình 6-15: Lớp PlaceView ................................................................... 100 Hình 6-16: Lớp DragEvent................................................................... 100 Hình 6-17: Lớp DetailEvent ................................................................. 101 Hình 6-18: Lớp ShortestPathEvent ....................................................... 101 Hình 6-19: Lớp ZoomEvent ................................................................. 102 i KH OA C NT T – Đ H KH TN Hình 6-20: Sequence Diagram: Hiển thị bản đồ .................................... 102 Hình 6-21: Collaboration Diagram: Hiển thị bản đồ ............................... 103 Hình 6-22: Sequence Diagram: Tìm các đường giao nhau...................... 104 Hình 6-23: Collaboration Diagram: Tìm các đường giao nhau................ 105 Hình 6-24: Sequence Diagram: Tìm giao lộ........................................... 106 Hình 6-25: Collaboration Diagram: Tìm giao lộ...................................... 107 Hình 6-26: Sequence Diagram: Tìm đường đi ngắn nhất ....................... 108 Hình 6-27: Collaboration Diagram: Tìm đường đi ngắn nhất .................. 109 Hình 6-28: Sequence Diagram: Tìm địa điểm........................................ 109 Hình 6-29: Collaboration Diagram: Tìm địa điểm................................... 110 Hình 6-30: Sequence Diagram: Tìm con đường..................................... 111 Hình 6-31: Collaboration Diagram: Tìm con đường................................ 112 Hình 6-32: Sequence Diagram: Dịch chuyển vùng nhìn.......................... 113 Hình 6-33: Collaboration Diagram: Dịch chuyển vùng nhìn..................... 114 Hình 6-34: Sequence Diagram: Tỉ lệ lại bản đồ ..................................... 115 Hình 6-35: Collaboration Diagram: Tỉ lệ lại bản đồ ................................ 115 Hình 6-36: Màn hình chính.................................................................. 116 Hình 6-37: Menu chính ....................................................................... 116 Hình 6-38: Nút bấm đặc biệt ............................................................... 117 Hình 6-39: Màn hình tìm thông tin ....................................................... 119 Hình 6-40: Màn hình tên thông tin ....................................................... 120 Hình 6-41: Màn hình thông tin chi tiết.................................................. 120 Hình 6-42: Màn hình tìm đường đi ngắn nhất ....................................... 121 Hình 6-43: Màn hình sử dụng chính ..................................................... 126 Hình 6-44: Màn hình tìm thông tin ....................................................... 127 Hình 6-45: Màn hình tìm đường đi ngắn nhất ....................................... 129 Hình 6-46: Màn hình tìm đường đi ngắn nhất ....................................... 130 Hình 6-47: Màn hình tìm đường đi ngắn nhất ....................................... 131 ii KH OA C NT T – Đ H KH TN Danh sách bảng Bảng 2-1: Sự hỗ trợ của Windows CE 3.0 đối với các hàm thư viện C- Runtime .......................................................................................12 Bảng 2-2: Các thư viện C-Runtime được hỗ trợ trên Windows CE 3.0 .......13 Bảng 3-1: Các tính năng GDI được hỗ trợ trên Windows CE 3.0 ...............23 Bảng 3-2: Các hàm thuộc CWnd không được hỗ trợ trên Windows CE ......24 Bảng 3-3: Các kiểu dữ liệu được hỗ trợ trên database của Windows CE ....27 Bảng 4-1: Quy ước ký hiệu trong thuật toán tìm dường đi ngắn nhất .......39 Bảng 4-2:Các khả năng khi sử dụng chuỗi hằng Unicode.........................53 Bảng 5-1: Header của file .MNT.............................................................55 Bảng 5-2: Header của file .DBF .............................................................58 Bảng 5-3: Header của file Shape ...........................................................59 Bảng 5-4: Các loại mẫu tin của file Shape ..............................................60 Bảng 5-5: Cấu trúc mẫu tin dạng Point ..................................................60 Bảng 5-6: Chỉ số trong file .MNT và thứ tự mẫu tin trong file DBF ............61 Bảng 5-7: Chỉ số trong file .SHP và thứ tự mẫu tin trong file DBF .............61 Bảng 5-8: Dữ liệu DBF quận/huyện........................................................63 Bảng 5-9: Cấu trúc file quận huyện........................................................67 Bảng 5-10: File dữ liệu đường dạngDBF .................................................67 Bảng 5-11: File dữ liệu đường ...............................................................69 Bảng 5-12: File dữ liệu địa điểm DBF .....................................................69 Bảng 5-13: File dữ liệu địa điểm............................................................70 Bảng 5-14: Giá trị đường một chiều.......................................................71 Bảng 6-1: Các chức năng chính .............................................................80 Bảng 6-2: Lớp MapData ........................................................................91 Bảng 6-3: Lớp MapView........................................................................91 Bảng 6-4: Lớp MapEvent.......................................................................91 iii KH OA C NT T – Đ H KH TN Bảng 6-5: Lớp RoadData.......................................................................93 Bảng 6-6: Lớp RoadPath .......................................................................93 Bảng 6-7: Lớp RoadArc.........................................................................94 Bảng 6-8: Lớp GraphData .....................................................................95 Bảng 6-9: Lớp Node .............................................................................95 Bảng 6-10: Lớp DistrictData ..................................................................96 Bảng 6-11: Lớp DistrictArea ..................................................................97 Bảng 6-12:Lớp PlaceData......................................................................98 Bảng 6-13: Lớp Place ...........................................................................98 Bảng 6-14: Lớp DistrictView ..................................................................99 Bảng 6-15: Lớp PlaceView................................................................... 100 Bảng 6-16: Các nút bấm trên menu chính ............................................ 117 Bảng 6-17: Bảng Menu ....................................................................... 119 Bảng 6-18: Menu tìm thông tin............................................................ 120 Bảng 6-19: Bảng các nút tìm đường đi ngắn nhất ................................. 122 Bảng 6-20: Kết qủa thử nghiệm trên máy ảo ........................................ 124 Bảng 6-21: Kết qủa thử nghiệm trên máy thật...................................... 125 Bảng 6-22: Các menu tìm đốI tượng.................................................... 128 Bảng 6-23: Các nút bấm tìm đường đi ngắn nhất.................................. 132 iv KH OA C NT T – Đ H KH TN Một số khái niệm và thuật ngữ Khái niệm Định nghĩa Ghi chú GIS (Geography Information System) Hệ thống thông tin địa lý. Sử dụng công nghệ này là một công nghệ dựa trên máy tính để xây dựng bản đồ, phân tích và xử lý các đối tượng tồn tại và các sự kiện xảy ra trên trái đất. Thông tin không gian Thông tin về những đặc điểm liên quan đến hình dạng, vị trí, quan hệ của các đối tượng địa lý. Bao gồm hai dạng: • Dạng hình học: mô tả các đặc điểm hình dạng, vị trí. Ví dụ như tọa độ của điểm, đường… • Dạng Topology: mô tả quan hệ giữa các đối tượng hình học. Ví dụ như những vùng nào kề với một vùng xác định. v KH OA C NT T – Đ H KH TN Thông tin phi không gian (thông tin thuộc tính) Thông tin về những đặc điểm liên quan đến thống kê, thông tin số, thông tin đặc trưng gán cho mỗi thuộc tính của đối tượng Ví dụ như tên đường phố, dân số… PDA (Personal Digital Assistant) Thiết bị điện tử hỗ trợ cá nhân, giúp người sử dụng lưu trữ các thông tin cá nhân, công việc cần thiết cũng như các phần mềm tối thiểu trên một thiết bị nhỏ gọn Pocket PC Khái niệm này có thể dùng để chỉ: • Hệ điều hành nhúng Pocket PC do Microsoft phát triển dựa trên nhân của Hệ điều hành Windows CE 3.0 • Các thiết bị PDA sử dụng hệ điều hành Pocket PC Palm-size Một dạng thiết bị cầm tay, sử dụng Windows CE 2.21 Đang có khuynh hướng bị Pocket PC thay thế do có nguồn điện và khả năng không tốt Handheld PC Một dạng thiết bị cầm tay, sử dụng Windows CE 2.21 Có kích thước lớn hơn Pocket PC Palm OS Hệ điều hành nhúng do Palm phát triển, sử dụng trên các thiết bị cầm tay Là một trong những hệ điều hành nhúng phổ biến nhất hiện nay, có khả năng chạy nhanh hơn hệ điều hành vi KH OA C NT T – Đ H KH TN Pocket PC của hãng Microsoft EPOC Hệ điều hành nhúng do Symbian phát triển Là một trong những hệ điều hành nhúng phổ biến nhất hiện nay Embedded Linux Hệ điều hành nhúng phát triển dựa trên nhân của Hệ điều hành Linux trên Desktop vii KH OA C NT T – Đ H KH TN Chương 1 :Mở đầu Chương 1 : Mở đầu 1.1 GIS, các ứng dụng và giải pháp về GIS GIS (Geography Information System ) là một công nghệ ra đời vào những năm 60 của thế kỉ 20. Công nghệ GIS cho phép đáp ứng các nhu cầu liên quan tới quản lý cũng như khai thác và sử dụng các thông tin, dữ liệu địa lý. Từ giai đoạn đầu, được sử dụng trên các hệ thống máy tính lớn ở Mỹ và Canada, đến nay, công nghệ GIS đã được áp dụng và triển khai hết sức rộng rãi trên phạm vi toàn thế giới, trên những hệ thống máy PC và thời gian gần đây là trên cả các thiết bị PDA. Một số ứng dụng GIS nổi tiếng trên thế giới hiện nay đang được ứng dụng rộng rãi như MapInfo, Arc/Info, Spatial Database Engine (SDE), ArcView GIS...: được sử dụng với mục đích quản lý, tích hợp, quy hoạch và khai thác các dữ liệu bản đồ. Tại Việt Nam, công nghệ GIS cũng đã được nghiên cứu và có được một số sản phẩm có kết quả đáng khích lệ. Thời gian gần đây, việc nghiên cứu công nghệ GIS đã cho ra hàng loạt ứng dụng áp dụng trong thực tế tại Tp.Hồ Chí Minh, như StreetFinder của DolSoft, hệ thống GIS trên website Ngân hàng bản đồ trực tuyến của VDC, DMC, Dolsoft (www.basao.com.vn), hệ thống chỉ dẫn giao thông của nhóm AMI Group - Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh. Các giải pháp về GIS thường được chia làm hai nhóm chính: • Giải quyết các bài toán phức tạp liên quan đến mạng giao thông Các bài toán như tìm kiếm đường đi tối ưu, điều phối lộ trình giao thông... thường được áp dụng trên các hệ thống máy tính lớn, có cấu hình mạnh. • Hiển thị và tìm kiếm các thông tin bản đồ. Đây là dạng ứng dụng bản đồ điện tử, cung cấp các khả năng cho phép người sử dụng xem bản đồ và tìm kiếm một số thông tin cần thiết, thường được áp dụng trên các máy tính thông thường và nhỏ. 1 KH OA C NT T – Đ H KH TN Chương 1 :Mở đầu 1.2 Ứng dụng GIS trên Pocket PC Sự phát triển mạnh mẽ của Internet, cũng như khả năng của công nghệ phần cứng, đã dẫn đến sự ra đời của các thiết bị ứng dụng Internet. Theo các nhà nghiên cứu thị trường, mặc dù PC vẫn giữ vai trò chủ yếu trong việc xử lý và hỗ trợ công việc, nhưng các thiết bị Internet hay thiết bị hỗ trợ cá nhân sẽ ngày càng khẳng định được vai trò của nó trên thị trường. Ra đời vào những năm 90 của thế kỉ 20, Pocket PC là một dạng thiết bị cầm tay PDA (Personal Digital Assistant) sử dụng hệ điều hành Pocket PC, một biến thể của Windows CE, một hệ điều hành nhúng được Microsoft phát triển cho các thiết bị không là PC (non-PC). Do đặc trưng nhỏ gọn, được thiết kế với mục đích giúp người sử dụng lưu trữ các thông tin cá nhân, công việc cần thiết cũng như các phần mềm tối thiểu trên một thiết bị nhỏ gọn, và sử dụng một hệ điều hành họ hàng Windows, Pocket PC đã được khá nhiều nhà sản xuất phần mềm quan tâm trong lĩnh vực phát triển ứng dụng, trong đó có các ứng dụng GIS. Tuy nhiên, Pocket PC chạy trên nền hệ điều hành nhúng Windows CE, hệ điều hành chỉ cung cấp bộ nhớ một cách giới hạn cho các ứng dụng phát triển trên nó. Vì vậy, các ứng dụng liên quan tới hệ thống GIS phát triển trên Pocket PC và hệ điều hành Windows CE gặp phải các vấn đề về tối ưu hoá bộ nhớ cũng như tốc độ và thường có tốc độ chậm hơn nhiều so với các ứng dụng trên PC thông thường. Ngoài ra, do khả năng lưu trữ có giới hạn, việc ứng dụng GIS trên môi trường này cũng gặp không ít khó khăn. Trên thị trường, một số sản phẩm GIS trên Pocket PC đã được phổ biến rộng rãi như Pocket Street của Microsoft, MapInPocket của Information Technologies India Ltd... 2 KH OA C NT T – Đ H KH TN Chương 1 :Mở đầu 1.3 Các giải thuật nghiên cứu về GIS Công nghệ GIS liên quan trực tiếp tới lý thuyết đồ thị cũng như trí tuệ nhân tạo trong việc đưa ra các giải thuật để giải quyết các bài toán liên quan. Đây là những lĩnh vực nghiên cứu được đầu tư rất nhiều với các cải tiến cũng như đã đưa ra được nhiều giải thuật tốt hoặc tối ưu (chẳng hạn như các giải thuật clipping, kiểm tra điểm trong/ngoài đa giác hay các giải thuật tìm kiếm trên cấu trúc dữ liệu hoặc tìm kiếm lộ trình tối ưu...) Các bài toán về GIS hiện nay vẫn đang được nghiên cứu và có những cải tiến rất tốt, kể cả trong các bài toán phức tạp. 1.4 Mục tiêu của đề tài Hiện nay, một ứng dụng bản đồ điện tử tại Việt Nam nói chung, và Tp.Hồ Chí Minh trên môi trường Pocket PC là rất cần thiết khi lượng khách du lịch từ nước ngoài đến tham quan Việt Nam ngày càng tăng, cũng như sự phổ biến ngày càng rộng rãi của Pocket PC tại Việt Nam. Với đặc tính nhỏ gọn và tiện lợi của nó, Pocket PC đặc biệt thích hợp với dạng ứng dụng bản đồ điện tử hỗ trợ người dùng xem bản đồ và tìm kiếm các thông tin cần thiết trong quá trình di chuyển. Do vậy, từ nhu cầu nói trên, chúng em đã đầu tư xây dựng đề tài ““Xây dựng một ứng dụng bản đồ trên Pocket PC 2002 (Windows CE 3.0) cho phép hiển thị một bản đồ điện tử và cung cấp một số chức năng tìm kiếm thông tin”. Đề tài phải giải quyết một số công việc chính: • Nghiên cứu về Pocket PC 2002 và Hệ điều hành nhúng Windows CE 3.0 để thấy được sự khác biệt về trong mô hình với Windows trên Desktop, cũng như làm rõ được khả năng lập trình trên môi trường này. • Dựa vào những hiểu biết này, xem xét việc xây dựng một ứng dụng bản đồ sẽ phải liên quan trực tiếp tới những vấn đề nào, sau đó, trình bày các giải pháp thực hiện để xây dựng một ứng dụng bản đồ trên Pocket PC 2002. • Triển khai vào một ứng dụng cụ thể là bản đồ Tp.Hồ Chí Minh. Ứng dụng cho phép xem bản đồ Thành phố một cách trực quan, tìm kiếm các thông tin 3 KH OA C NT T – Đ H KH TN Chương 1 :Mở đầu liên quan đến đường phố, địa điểm (như bệnh viện, trường học...) với tốc độ truy xuất, tìm kiếm thông tin có thể chấp nhận đối với người dùng. Ngoài ra, chúng em cũng đã hỗ trợ thêm chức năng tìm kiếm lộ trình ngắn nhất giữa hai vị trí trên bản đồ và một số biến thể của bài toán này là giải quyết việc tìm lộ trình ngắn nhất với ràng buộc phải qua một số giao lộ, con đường hoặc phải tránh một số giao lộ, con đường nào đó (vì nhiều lí do như kẹt xe, ngập lụt...) 4 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 Chương 2 : Tổng quan về Pocket PC và Windows CE 3.0 2.1 Giới thiệu về các thiết bị PDA Khoảng hai mươi năm trước, đã có một cuộc cách mạng về máy tính khi máy tính IBM PC ra đời. Máy tính trở nên thông dụng với mọi người do không còn mang kích thước quá lớn. Sau đó, máy tính xach tay (Laptop PC) xuất hiện, cho phép người sử dụng dùng máy tính của mình ở khắp nơi, từ nhà đến văn phòng. Các máy PC là những thiết bị tính toán với năng lực mạnh mẽ nhưng mềm dẻo, đã trở nên hết sức thông dụng trên thị trường thế giới. Tuy nhiên, đang tồn tại một cuộc cách mạng tiềm ẩn và hứa hẹn khác, đó là sự ra đời của các thiết bị tính toán, xử lý di động hay còn gọi là thiết bị hỗ trợ cá nhân (PDA-Personal Digital Assistant). Trong vài năm gần đây, các thiết bị dạng này đang ngày càng phổ biến. Tuy nhiên, vào thời điểm ban đầu, mỗi thiết bị sử dụng hệ điều hành của riêng nó (các phần mềm trên thiết bị có thể do các nhà cung cấp phần mềm độc lập, bán bản quyền cho nhà cung cấp thiết bị ). Việc này đã dẫn đến sự phân chia thị trường của các hệ điều hành cho thiết bị di động, hay còn gọi là hệ điều hành nhúng, ngăn cản khả năng phát triển các ứng dụng nhúng một cách đồng loạt. Hiện nay, thị trường cho các hệ điều hành nhúng đã bắt đầu có khuynh hướng thu hẹp lại với các hệ điều hành có thị phần cao: • Microsoft Windows CE, bao gồm cả biến thể Pocket PC của hệ điều hành này • Palm OS do Palm cung cấp • EPOC của Symbian • Embedded Linux, hệ điều hành ban đầu chỉ được phát triển cho máy chủ và máy desktop Trong đó, Pocket PC và Windows CE có ưu thế hơn do là một hệ điều hành họ Windows, khá quen thuộc với người sử dụng lẫn lập trình viên. 5 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 2.2 Tổng quan về Windows CE Windows CE là một hệ điều hành nhúng do Microsoft phát triển, được tích hợp vào các thiết bị giải trí, các máy subnotebook, máy tính cầm tay (handheld PC, palm-size PC…), các điện thoại di động, hoặc những hệ thống thông tin và giải trí trên xe hơi (AutoPC)… Windows CE là hệ điều hành họ Windows, song được thiết kế cho các thiết bị di động, nên có tính năng nhỏ gọn, đồng thời “có thể điều chỉnh” (modular) và dễ chuyên biệt hóa để có thể thích ứng trong việc điều khiển nhiều hệ thống nhúng khác nhau. Điều này có nghĩa là các kĩ sư có thể chọn lựa những phần nào của hệ điều hành cần sử dụng, ví dụ như một thiết bị có thể không cần bàn phím hoặc màn hình, nhưng có thể đòi hỏi sử dụng được mạng. Bằng cách chọn lựa những module mà thiết bị cần, kích thước và giá thành của thiết bị có thể được giảm xuống. Tuy nhiên, sự điều chỉnh này lại có thể là một khó khăn cho các nhà phát triển ứng dụng, vì có thể Windows CE hỗ trợ một tính năng nào đó, nhưng thiết bị nguồn được sử dụng lại không hỗ trợ. Hiện thời, có khá nhiều sự lẫn lộn quanh các phiên bản của Windows CE cũng như cách gọi tên. Sau đây là một vài phiên bản hiện thời của Windows CE: • Windows CE 3.0: Phiên bản này được thiết kế để cung cấp các đặc tính của một hệ điều hành thời gian thực và một số phát triển khác. Thiết bị Pocket PC sử dụng một dạng biến thể phiên bản này. • Windows CE 2.12: Được sử dụng chủ yếu bởi các nhà sản xuất thiết bị nhúng dùng Microsoft Platform Builder. Phiên bản này không nhắm tới các thiết bị cho người tiêu thụ cuối. • Windows CE 2.21: Phiên bản của Windows CE dùng cho các thiết bị Windows Handheld và Palm-size. 6 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 2.3 Tổng quan về Pocket PC Vào đầu năm 2000, Microsoft giới thiệu một phiên bản của hệ điều hành Windows cho các thiết bị di động gọi là Pocket PC. Hệ điều hành Pocket PC là một phiên bản của Windows CE 3.0, với các tính năng và giao diện được thiết kế riêng cho các thiết bị hỗ trợ cá nhân (PDA – Personal Digital Assistant) và máy tính cầm tay (handheld PC). Có thể hiểu Pocket PC là một phiên bản của Windows CE được cài đặt nhằm tối ưu cho các thiết bị này. Phiên bản hiện đang được sử dụng rộng rãi nhất là Pocket PC 2002. Pocket PC giải quyết được nhiều thiếu sót đã làm giảm thành công của Windows CE, như giao diện quá phức tạp, tốc độ chậm, khả năng lưu trữ kém, nguồn cung cấp năng lượng không tốt… Microsoft đã thêm các tính năng mới cho các thiết bị Pocket PC (Pocket PC – device, những thiết bị PDA sử dụng hệ điều hành Pocket PC) với hệ điều hành Pocket PC chứa phiên bản thu gọn của một số phần mềm như Internet Explorer, Word, Excel, Outlook, Microsoft Reader, Windows Media Player… Các thiết bị Pocket PC là một dạng thiết bị PDA, do nhiều hãng như Compag, HP, Casio sản xuất. PocketPC sử dụng các chuẩn cắm công nghiệp, có tính tương thích và mở rộng cao như có thể kết nối với máy tính để bàn, gắn thêm storage card, modem kết nối Internet... Ghi chú: Từ đây, trong luận văn, khi đề cập đến Pocket PC xin hiểu đây là thiết bị Pocket PC chạy trên phiên bản hệ điều hành Pocket PC 2002, được phát triển trên nhân hệ điều hành nhúng Windows CE 3.0. Ngoài ra, do là một biến thể của Windows CE 3.0, nên khi đề cập tới các vấn đề liên quan như khả năng lập trình, hạn chế về tốc độ, giải pháp của Windows CE… xin hiểu đó cũng là các vấn đề gặp phải với Pocket PC. 7 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 2.4 Khả năng lập trình trên Pocket PC và Windows CE 3.0 Trong phương diện lập trình, có nhiều điểm khác biệt từ lớn cho tới nhỏ giữa Windows CE và phiên bản Windows trên Desktop. Lý do gây ra sự khác biệt này là do Windows CE được xây dựng và thiết kế từ kiến trúc nền sao cho nó có thể ở mức nhỏ nhất có thể. Windows CE bảo đảm 2 điều: các hàm được chọn lọc lại để sử dụng hoặc không hỗ trợ các hàm này nữa (phụ thuộc vào yêu cầu xác định của thiết bị, như H/PC hay P/PC). Trong các hàm được khai báo và cài đặt trùng nhau giữa Win32 API và các thư viện runtime của ngôn ngữ lập trình (ví dụ: lstrlen/strlen, time/GetSystemTime…), WinCE sẽ chỉ cung cấp và hỗ trợ một hàm. Một thay đổi lớn về mặt cấu tạo là cách Win CE cung cấp các thư viện hệ thống. Win CE không còn cung cấp nhiều thư viện khác nhau như GDI, Kernel và User nữa, mà chỉ cung cấp duy nhất một thư viện coredll.lib. Thư viện này cung cấp tất cả các hàm API cũng như nhiều hàm nội (internal) không được cung cấp tài liệu. 2.4.1 Các hàm Win32 API Khoảng 3600 hàm Win32 API được hỗ trợ trong Windows NT và Windows 95/98, còn số hàm API mà Windows 2000 lớn hơn rất nhiều. Trong khi đó, phiên bản 1.0 của WinCE chỉ hỗ trợ 500 trong số các hàm này, trong phiên bản 2.0( được cấu hình cho H/PC và P/PC), số hàm này tăng gấp 3, khoảng 1500 hàm. Các hàm của Windows CE sử dụng mô hình khai báo hàm cho các phiên bản ANSI và UNICODE giống trên desktop. Dựa vào macro UNICODE, hệ điều hành sẽ chọn khai báo hàm tương ứng khi biên dịch chương trình. Tuy nhiên, thực chất, chỉ có phiên bản Unicode của các hàm API này được cài đặt, vì vậy, bất kì chương trình nào được xây dựng nhằm mục đích sử dụng trong môi trường Windows CE đều phải định nghĩa macro UNICODE. Trong môi trường Windows CE, các ứng dụng dạng Win32 console không được hỗ trợ. Mọi ứng dụng đều bắt buộc phải có hàm WinMain (thay cho main()), trong đó, tham số dòng lệnh lpCmdLine là một chuỗi Unicode. Tuy nhiên, ứng dụng không bắt buộc phải có vòng lặp xử lý thông điệp. Các ứng dụng 8 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 dialog-based hoặc không có giao diện để người dùng tương tác vẫn làm việc bình thường mà không cần vòng lặp này. Một đặc điểm nữa khi lập trình trong Windows cần chú ý là các cửa sổ chương trình trong Windows CE chỉ có thể ở một trong hai trạng thái: minimized hay maximized. Vì vậy, Windows CE không còn hỗ trợ cho việc định lại kích cỡ cửa sổ, có nghĩa là các thông điệp như WM_SIZING hay WM_WINDOWPOSCHANGING hoặc biểu tượng Restore trên menu hệ thống cũng không còn cần thiết Cấu hình hệ thống cho chương trình trên Windows CE toàn bộ sử dụng Registry như trên desktop, không sử dụng các biến môi trường hay các file INI. Mọi chương trình đều phải sử dụng Registry, có cơ chế gần như tương tự với Registry trên Windows- phiên bản desktop. Vì một hay nhiều nguyên nhân, một số phần cơ bản trong Win32 API cũng không được hỗ trợ. Các phần này bao gồm: • Hook • Generic, flat, and universal thunks • Services and the event log • Profiling (GetThreadTime và GetProcessTime) • Bảo mật (SACLs, DACLs, …) Từ phiên bản 2.1, Windows CE đã thêm vào một số hỗ trợ cho vấn đề mã hoá (gọi là Cryptography API) cũng như hỗ trợ cho COM (CompChỉ mộtnt Object Model) 2.4.2 Các hàm API và SDK phụ trợ Các hàm này không nằm trong tập hợp các hàm được xem là cơ bản của Win32. Trong khi Win32 hỗ trợ một số lượng khổng lồ các hàm SDK và API ngoại vi, thì Windows CE chỉ hỗ trợ rất ít các hàm này. Một số những tính năng quan trọng được Windows CE hỗ trợ như: 9 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 2.4.2.1 Truyền thông đa phương tiện (Multimedia) Bắt đầu từ Windows CE 2.0, hệ điều hành này đã hỗ trợ một số hàm sử dụng để chơi hoặc thu lại âm thanh. sndPlaySound và các hàm trong họ xử lý wave (waveInStart, waveOutClose...) cũng bắt đầu có thể sử dụng được trong việc tạo và dùng các tập tin WAV. 2.4.2.2 WinSock WinSock được hỗ trợ hạn chế trên Windows CE. Chỉ một vài chức năng cơ bản liên quan tới cơ sở dữ liệu (getservbyname...), các hàm không đồng bộ (WSAAsyceSelect...) và Secure Socket Layer (SSL) được hỗ trợ trên Windows CE. 2.4.2.3 Telephony API (TAPI) Một tập con của TAPI được cung cấp và cài đặt nhưng chỉ để hỗ trợ cho các cuộc gọi đi. Các hàm API này có thể được sử dụng với các thiết bị modem tích hợp sẵn (built-in) hay PCMCIA. 2.4.2.4 Mail API (MAPI) MAPI không được hỗ trợ trên Windows CE, mà thế vào đó là một bộ API riêng cho Windows CE được cung cấp nhằm giúp lập trình viên có thể tạo, gửi mail và sử dụng address book. 2.4.2.5 Active Data Objects (ADO) ADO là một phần mới được hỗ trợ trong Windows CEvới đầy đủ các chức năng cho Recordset và Field. 2.4.3 Các thư viện C-Runtime Windows CE chỉ hỗ trợ một phần các hàm thư viện C-runtime có trên môi trường Desktop. Hỗ trợ ít hàm hơn cho phép Windows CE có thể chạy trên các thiết bị với các tài nguyên hạn chế hơn rất nhiều so với phiên bản Desktop. Các thư viện này chứa khoảng vài trăm hàm nằm trong 15 thư viện 10 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 Loại hàm Hỗ trợ trên Windows CE Nhóm hàm liên quan đến chuỗi (ghép nối chuỗi, sao chép chuỗi, so sánh chuỗi, chiều dài chuỗi, tìm chuỗi, tìm kí tự, tìm token, gán kí tự cho chuỗi, đổi chuỗi thành chữ hoa/thường, đảo chuỗi) Một phần Thông báo lỗi chuỗi Không Các hàm xử lý chuỗi khác Không Phân loại kí tự Một phần Chuyển đổi (ép) kiểu dữ liệu Một phần Thao tác trên vùng đệm (buffer) Có Tách byte đối với các chuỗi multibyte Không Truy xuất tham số Không Thiết lập, thông báo về thời gian, định dạng thời gian Không Các hàm toán học lượng giác, log, exponent, power, trị tuyệt đối... Có Ép kiểu dấu chấm động Một phần Random giá trị Có Các hàm toán học và xử lý dấm chấm động khác Một phần Execute, Exit, Spawn Không Điều khiển tiến trình, điều khiển môi trường Một phần Cấp phát bộ nhớ Một phần Heap Không Memory handler hông Các lệnh gọi hệ thống Không Nhóm hàm liên quan đến stream (đóng/mở stream, định vị stream-pointer, đọc nhiều byte từ stream, đọc kí tự từ stream, ghi nhiều byte ra stream, ghi kí tự ra Một phần 11 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 stream, flushing và buffer) Thông báo lỗi stream Có Các dạng file I/O khác Không Nhóm hàm liên quan đến file (Đóng/mở/tạo file, Đọc/ghi file, Định vị con trỏ file) Không Console và các cổng I/O Không Điều khiển thư mục Không Xử lý file dựa trên file handle Chỉ một Xử lý file dựa trên đường dẫn và tên file Không Lỗi handling Một phần Lỗi Exception handling Không Bảng 2-1: Sự hỗ trợ của Windows CE 3.0 đối với các hàm thư viện C- Runtime File tiêu đề Hỗ trợ trên Windows CE Không Có Không Có Có Không Có Có Không Có Không Không Có 12 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 Có Không Bảng 2-2: Các thư viện C-Runtime được hỗ trợ trên Windows CE 3.0 Một trong những thư viện bị thiếu quan trọng nhất là thư viện stdio. Lý do dễ dàng nhận thấy là vì Windows CE không hỗ trợ ứng dụng dạng console, nên người dùng không có cách tương tác với chương trình thông qua dòng lệnh, và vì vậy, các hàm thư viện stdio được thay thế (ví dụ, hàm printf được thay bằng một hộp thoại - dialog box) Tuy nhiên, có một điều thú vị là trong khi tài liệu về Windows CE thường nói về vấn đề thiếu các hàm này, thì khi áp dụng lập trình thực tế, có một số vẫn có thể sử dụng được. Có lẽ, trong các phiên bản sau, các hàm hoặc cơ chế này sẽ được hỗ trợ. 2.4.4 Các thư viện chuẩn C++ So sánh với các thư viện C-RTL (C-Runtime Library), số lượng các hàm C++ còn bị thiếu hơn rất nhiều. Mặc dù các tính năng quan trong như template, con trỏ hàm... vẫn được cung cấp, song khá nhiều hỗ trợ khác đã bị bỏ qua, như các xử lý ngoại lệ (exception), thông tin kiểu runtime (runtime-type information), và toàn bộ STL (Standard Template Library) (do dựa trên các xử lý exception) 2.4.5 Tiến trình và tiểu trình 2.4.5.1 Hạn chế Trên hệ điều hành Win 32, không có hạn chế nào về số lượng tiến trình có thể chạy đồng thời, và mỗi tiến trình sở hữu 4GB không gian bộ nhớ ảo của riêng nó. Windows CE đã thay đổi nhiều kiến trúc này, chỉ cho phép 32 tiến trình được phép chạy đồng thời. Mỗi tiến trình này được coi là một slot, hỗ trợ 32MB không gian bộ nhớ ảo trong tổng số 1GB bộ nhớ có thể định vị được. Các module cung cấp các chức năng của hệ điều hành, như driver thiết bị, đồ hoạ và các hệ sự kiện con 13 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 (event subsystem) giữ một vài slot đầu tiên khi thiết bị khởi động. Thông thường, một thiết bị đang chạy với phần shell và các dịch vụ thông tin liên lạc có khoảng 24 slots trống cho các ứng dụng của người dùng. Tuy nhiên, mặt khác, Windows CE không giới hạn số tiểu trình trong một tiến trình. Mỗi tiểu trình có quyền truy xuất hoàn toàn lên phần không gian 32MB của tiến trình. Hình 2-1: Phân bố bộ nhớ trong Windows CE Không giống Windows NT hay 95, không gian stack dành cho một tiểu trình không được cấp phát động, mà có cùng kích thước cố định đối với tất cả các tiểu trình trong một tiến trình. Phiên bản trước 2.1 có phần stack cố định là 58KB, và người dùng không thể thay đổi phần stack này. Từ phiên bản 2.1, kích thước mặc định được thiết lập bởi việc sử dụng khai báo /stack trong trình linker. Nếu không có khai báo này, chương trình sẽ tự động sử dụng giá trị 58KB. Một lưu ý quan trọng là kích thước stack của tiểu trình thứ 2 không thể thay đổi trong quá trình chạy bằng cách chỉ ra giá trị dwStackSize trong hàm API CreateThread hay beginthreadex. Tham số này bị bỏ qua và chương 14 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 trình luôn sử dụng giá trị được xác định qua khai báo /stack hoặc qua giá trị mặc định của hệ điều hành. Sự sắp xếp độ ưu tiên của tiểu trình trên Windows CE cũng khác trên Win32. Không giống trên WindowsNT, Windows CE không có lớp ưu tiên và các tiểu trình không được điều phối dựa trên độ ưu tiên của tiến trình chứa nó; Thay vào đó, tất cả các tiến trình đều được xem là ngang nhau, và việc điều phối dựa trên một tiêu chí duy nhất, đó là độ ưu tiên của tiểu trình. Windows CE hỗ trợ 8 mức độ ưu tiên của tiểu trình: • THREAD_PRIORITY_TIME_CRITICAL trên độ ưu tiên bình thường 2 cấp • THREAD_PRIORITY_HIGHEST trên độ ưu tiên bình thường 1 cấp • THREAD_PRIORITY_ABOVE_NORMAL trên độ ưu tiên bình thường 1 cấp • THREAD_PRIORITY_NORMAL chỉ độ ưu tiên bình thường. Đây là mức ưu tiên mặc định cho tất cả các tiểu trình • THREAD_PRIORITY_BELOW_NORMAL dưới độ ưu tiên bình thường 1 cấp • THREAD_PRIORITY_LOWEST dưới độ ưu tiên bình thường 2 cấp • THREAD_PRIORITY_ABOVE_IDLE dưới độ ưu tiên bình thường 3 cấp • THREAD_PRIORITY_IDLE dưới độ ưu tiên bình thường 4 cấp Việc điều phối hoạt động theo chiến lược Round-Robin dựa trên độ ưu tiên, nghĩa là tất cả các tiểu trình có độ ưu tiên cao hơn sẽ hoạt động trước các tiểu trình có độ ưu tiên thấp hơn. Có 2 ngoại lệ trong chiến lược Round-Robin khi điều phối các tiểu trình trên WindowsCE. Bất kỳ tiểu trình nào có được độ ưu tiên THREAD_PRIORITY_CRITICAL đều sẽ không bị ngắt trong khi đang hoạt động, 15 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 ngay cả bởi 1 luồng THREAD_PRIORITY_CRITICAL khác. Nó sẽ hoạt động đến khi hoàn thành hoặc khi hết khối xử lý. Các tiểu trình có độ ưu tiên này thường dành riêng cho việc phục vụ các ngắt trong driver thiết bị và các phần của hệ điều hành. Không nên sử dụng độ ưu tiên này trong ứng dụng. Ngoại lệ thứ hai xuất hiện khi tiểu trình có độ ưu tiên thấp hơn sở hữu một tài nguyên mà một tiểu trình có độ ưu tiên cao hơn phải sử dụng. Trong trường hợp này, tiểu trình có độ ưu tiên thấp sẽ tạm thời được cấp quyền ưu tiên của tiểu trình đang chờ nó để tài nguyên được giải phóng và tiểu trình có độ ưu tiên cao sẽ tiếp tục chạy. Sau khi tài nguyên được giải phóng, độ ưu tiên của tiểu trình sẽ được thiết lập trở lại trạng thái ban đầu 2.4.5.2 Đồng bộ hoá tiểu trình Đồng bộ hoá tiểu trình trên WindowsCE được phân chia thành 3 phần chính • Miền găng • Các interlocked API • Các đối tượng hạt nhân (kernel object) Sử dụng miền găng cũng tương tự như trên Windows32, dùng để bảo đảm không có quá một tiểu trình tại một thời điểm thi hành một khối mã lệnh nào đó. Có 4 thao tác chính trên miền găng: initialize, delete, enter và leave, và các hoạt động của chúng cũng tương tự như trên Windows 98 và NT Các hàm interlock được cung cấp nhằm bảo vệ các thao tác đơn mà không cần dùng miền găng hay mutex. Các hàm này gồm • InterlockedCompareExchange • InterlockedTestExchange • InterlockedIncrement • InterlockedDecrement • InterlockedExchange • InterlockedExchangeAdd 16 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 Các hàm interlock rất tốt trong các trường hợp thao tác trên các biến đếm trong ứng dụng đa tiểu trình (thông qua InterlockedIncerment và InterlockedDecrement), nhưng trong các vấn đề phức tạp hơn, nên sử dụng miền găng hoặc mutex. Các đối tượng hạt nhân là các tài nguyên của hệ điều hành có thể được tham chiếu đến, như handle, từ bất kì tiến trình nào. Các ví dụ của đối tượng hạt nhân là mutex, tiểu trình, và tiến trình Win32 cung cấp 4 đối tượng hạt nhân cho việc đồng bộ hoá • Mutex cung cấp chức năng tương tự miền găng • Event cho phép thông báo tới các tiểu trình khác khi điều kiện được thoả • Semaphore cung cấp khả năng hạn chế số tối đa người dùng thao tác tới tài nguyên • Waitable Time cho phép thông báo tới các tiểu trình khác theo một khoảng thời gian xác định Tuy nhiên, trong Windows CE 3.0, chỉ có mutex, event và semaphore được hỗ trợ. Giống như miền găng, mutex cung cấp các chức năng để hạn chế việc truy xuất vào một khối mã nguồn trong một tiểu trình vào một khoảng thời gian. Để giành mutex, ta sử dụng WaitForSingleObject và giải phóng nó bằng cách gọi hàm ReleaseMutex. Lợi thế lớn nhất của mutex so với miền găng là ở chỗ mutex là một đối tượng hạt nhân, vì vậy nhó có thể được dùng trong nhiều tiến trình. Nếu ta không cần đồng bộ hoá nhiều tiến trình, thì nên sử dụng miền găng bởi độ nhanh trong xử lý của nó trên thiết bị sử dụng WinCE (xin tham khảo [ 6]) Event có tính năng mềm dẻo hơn nhiều so với mutex và cung cấp khả năng thông báo tới các tiểu trình khác nếu một điều kiện ràng buộc nào đó được thoả. Event trên WindowsCE tương tự như trên Windows98 và WindowsNT với việc sử dụng hai hàm SetEvent và PulseEvent 17 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 Semaphore là một đối tượng đồng bộ hoá liên tiến trình có thể có giá trị giữa 0 và một giá trị cực đại nào đó. Trạng thái của đối tượng sẽ được thiết lập thành giá trị “bật” nếu số đếm của nó lớn hơn 0 và ngược lại. Ta có thể sử dụng các hàm CreateSemaphore hay ReleaseSemaphore để tạo hoặc giải phóng một đối tượng Semaphore (Windows CE không hỗ trợ OpenSemaphore). Đối tượng này có thể dùng trong nhiều tiến trình hoặc trong duy nhất một tiến trình. 2.4.6 Vấn đề Unicode Ở mức độ hệ thống, Windows CE sử dụng duy nhất chuẩn Unicode cho tất cả các chuỗi và kí tự, do đó, các ứng dụng trên Windows CE đều phải hỗ trợ Unicode. Đây cũng là một điều thuận tiện nhằm giúp các ứng dụng có khả năng phát triển đa ngôn ngữ, hướng tới thị trường toàn cầu hơn. Tuy nhiên, đây đôi khi lại là khó khăn với các lập trình viên thường gặp khi lập trình với Windows CE. Tất cả các hàm API của Windows CE đều dùng chuỗi Unicode thay thế cho các chuỗi 1 byte (single byte string) hay nhiều byte (multi- byte string) Khi lập trình trên môi trường Windows CE, có một số điểm cần lưu ý: Quyết định xem mã nguồn này sẽ chỉ được sử dụng trên WinCE hay đôi khi cũng được sử dụng trong các hệ đìều hành họ Windows khác (tính khả chuyển). Nếu muốn duy trì sự khả chuyển này, nên sử dụng riêng từng phần xử lý Unicode bằng các macro #ifdef _WIN32_WCE và UNICODE. Nếu muốn duy trì tính khả chuyển, nên sử dụng các chuỗi ở dạng TCHAR. Có thể dùng WCHAR nếu tính khả chuyển này không quan trọng lắm, còn CHAR được sử dụng đối với các chuỗi được đọc/ghi từ các tập tin văn bản ASCII hay các thiết bị phần cứng (như modem…) Nếu ta xây dựng phiên bản Unicode của ứng dụng (ví dụ ta định nghĩa _DUNICODE khi dịch chương trình), TCHAR sẽ được chuyển thành WCHAR. Còn nếu ta xây dựng phiên bản non-Unicode, TCHAR sẽ được chuyển thành 18 KH OA C NT T – Đ H KH TN Chương 2 :Tổng quan về Pocket PC và Windows CE 3.0 CHAR. Một số hàm sử dụng các chuỗi TCHAR thông dụng như _tcscpy, _tcslen, _tcsstr, _tcscat… Các nhóm hàm thường sử dụng mẫu đặt tên theo kiểu strfunction, wcsfunction, mbsfunction. Dựa trên đây, ta có thể biết hàm nào sử dụng cho tập kí tự nào. strfunction là phiên bản xử lý chuỗi truyền thống, wcsfunction là phiên bản xử lý cho các chuỗi wide-character (như Unicode), mbsfuction là phiên bản xử lý cho các chuỗi dạng multibyte-character. tương tự như vậy, cho các mẫu hàm function, wfunction (wfunction thường là phiên bản wide-character của hàm) Nếu dùng các biến WCHAR, ta nên sử dụng các hàm xử lý chuỗi riêng cho UNICODE (như wcscpy, wcslen, wcsstr, wcscat…). Nếu ta cần phải hỗ trợ các chuỗi kí tự ASCII, có thể sử dụng các hàm mbstowcs, wcstombs để chuyển chuỗi qua lại UNICODE. 19 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC Chương 3 : Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC 3.1 Khả năng tính toán của Pocket PC Pocket PC sử dụng một loại CPU khác với CPU thông thường. Máy Pocket PC 2002 sử dụng CPU StrongARM hoặc XScale của Intel. Các CPU này được gọi là các bộ xử lý RISC (Reduced Instruction Set Computer) vì nó chỉ thực hiện một lệnh trong một chu kì CPU. (Mỗi chu kì CPU trong một giây gọi là 1 Hertz hay 1 Hz). Máy PC thông thường của chúng ta sử dụng bộ xử lý CISC (Complex Instruction Set Computer), đòi hỏi nhiều chu kì CPU để xử lý một lệnh xác định. Do đó, các bộ xử lý RISC như StrongARM theo lý thuyết, có thể tính toán lên tới 206 triệu lệnh một giây nếu nó xử lý ở tốc độ 206 Mhz. Các bộ xử lý StrongARM và XScale cũng xử lý các lệnh 32bit, giống như PC thông thường. Tuy nhiên, lại có một khác biệt lớn trong việc xử lý kích thước lệnh. Bộ xử lý CISC cho phép lệnh có thể có chiều dài biến đổi, vì vậy, nó phải tính toán kích thước của dữ liệu cần đọc khi xử lý lệnh. Trong kiến trúc RISC, mỗi lệnh 32bit sẽ có 32 dữ liệu đi kèm. Vì vậy, bộ xử lý luôn biết được phải đọc bao nhiêu dữ liệu., đây là một điểm mạnh của kiến trúc này. Độ rộng của bus cùng với tốc độ bus cũng có một ảnh hướng lớn đến tốc độ xử lý và tính toán của máy tính. Độ rộng của bus chỉ ra số lượng bit (hay byte) dữ liệu có thể đọc từ / ghi lên RAM vào bộ vi xử lý. Còn tốc độ bus chỉ ra dữ liệu có thể được đọc từ RAM vào bộ vi xử lý với độ nhanh như thế nào. Ta có thể hình dung, độ rộng bus như số làn giao thông trên xa lộ, còn tốc độ bus như giới hạn về tốc độ khi lưu thông. Hiện này, StrongARM và XScale sử dụng bus tốc độ 100Mhz và thiết kế hiện nay của Pocket PC cho phép dùng bus 16bit. Điều này có nghĩa là tốc độ bus tối đa là 200MB/giây. 20 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC Vấn đề đặt ra ở đây là như vậy, bộ vi xử lý có thể đạt được tốc độ xử lý bao nhiêu. Do chúng ta cần đọc 8bytes dữ liệu trước khi xử lý một lệnh, nên giả sử chúng ta có được tốc độ bus tối đa là 200MB/giây, thì thực sử, bộ xử lý chỉ thi hành được 25 triệu lệnh. Ngoài ra, lại có một vấn đề khác, đó là cache. Cache là một loại RAM đặc biệt được chứa bên trong CPU và xử lý với cùng tốc độ của CPU. Cache trong bộ xử lý StrongARM là 16K cho mã chương trình và 8K cho dữ liệu, cache trong XScale là 32K cho mã chương trình và 32K cho dữ liệu. Nếu dữ liệu và mã chương trình cần xử lý được chứa trọn trong cache, hệ thống sẽ có thể thi hành với tốc độ thật của CPU. Như vậy, tốc độ của ứng dụng có thể được thi hành sẽ có thể tăng từ 25 lên 206 triệu lệnh một giây, tuỳ theo chương trình và dữ liệu có vừa với kích thước cache không. Tốc độ của hệ thống cũng phụ thuộc vào nguồn cung cấp năng lượng, do đó, khi sử dụng Pocket PC, ta có thể nhận thấy sự khác biệt về tốc độ khi thực thi chương trình. Bây giờ, sử dụng các để so sánh về hiệu suất hoạt động giữa máy DesktopPC và Pocket PC. Các hệ thống Desktop PC hiện tại thường sử dụng bus 100-133 Mhz. Pentium IV có thể sử dụng DDR RAM hoặc RAM BUS (RD RAM) có tốc độ từ 200-800Mhz. Vì vậy, chỉ xét trên phuơng diện RAM, nếu sử dụng RAM 133Mhz, hiệu suất Desktop PC đã tăng 1/3 lần (25 lên 33 triệu lệnh một giây). Tốc độ CPU của Desktop cũng lớn hơn rất nhiều khi hiện tại đã đạt tới tốc độ trên 3Ghz dẫn đến hiệu suất toàn hệ thống cao hơn. Khi lập trình ứng dụng bản đồ trên Pocket PC, đặc điểm về bộ xử lý cũng như tốc độ của Pocket PC ảnh hưởng rất lớn đến tốc độ hiển thị, xử lý cũng như tìm kiếm thông tin GIS. Để giải quyết vấn đề này, ta cần có những giải pháp phù hợp để tăng hiệu năng của ứng dụng, giúp người sử dụng có thể sử dụng được chương trình với tốc độ chấp nhận được. 3.2 Tốc độ và các hỗ trợ khả năng hiển thị Đối với các ứng dụng bản đồ, một trong những vấn đề quan trọng nhất cần phải quan tâm, đó là hỗ trợ hiển thị của môi trường. 21 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC Tương tự trên môi trường Windows – phiên bản desktop, các đối tượng trực quan như văn bản, đồ hoạ được GDI (Graphics Device Interface) điều khiển. Với các hàm GDI này, ứng dụng có thể vẽ hoặc hiển thị đường thẳng, đường cong, các đường khép kín, văn bản và các bitmap. Màu và kiểu của các đối tượng này dựa trên các đối tượng đồ hoạ mà lập trình viên tạo ra và sử dụng. GDI trên Windows CE cũng sử dụng một ngữ cảnh thiết bị (device context ) để lưu trữ dữ liệu cần được hiển thị trên thiết bị. Các đối tượng đồ hoạ được lưu trữ trong device context ở môi trường Windows CE bao gồm một bút vẽ (pen) để vẽ nét, chổi vẽ (brush) để tô màu, font chữ để hiển thị chữ, bitmap phục vụ cho việc sao chép hoặc kéo, bảng màu (palette) để chỉ định màu vẽ, và vùng clipping. Windows CE hỗ trợ ngữ cảnh thiết bị máy in (printer device context) của máy in để vẽ lên máy in, ngữ cảnh thiết bị hiển thị (display device context) để vẽ lên thiết bị video, ngữ cảnh bộ nhớ (memory device context ) để vẽ lên bộ nhớ. Khi xây dựng ứng dụng bản đồ trên Pocket PC, cần chú ý tới việc chỉ được sử dụng các tính năng GDI được hỗ trợ trên môi trường này. Danh sách các tính năng được hỗ trợ được liệt kê trong bảng sau. Tính năng GDI Mô tả Font Raster và TrueType Các font True Type có thể kéo giãn hoặc quay được. Hỗ trợ sẵn 7 font Raster trong ROM. Windows CE chỉ hỗ trợ một loại font, cả raster lẫn TrueType trên 1 loại thiết bị xác định Bảng màu Hỗ trợ các độ sâu màu 1, 2, 4, 8, 16, 24, và 32 bits per pixel (bpp). Một bpp depth of 2 is unique to Windows CE. Các hàm dịch khối bit và thao tác theo vạch Cho phép quay, định cỡ và nối các bitmap Enables you to transform and combine bitmaps Pen và brush Hỗ trợ các loại dashed, wide, và solid pen, patterned 22 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC brush In Hỗ trợ in ấn đồ hoạ (graphics printing) Con trỏ Hỗ trợ đầy đủ về con trỏ, bao gồm cả con trỏ do người dùng định nghĩa. Các thao tác vẽ hình (Shape drawing) Hỗ trợ vẽ ellipse, polygon, rectangle, và round rectangle Bảng 3-1: Các tính năng GDI được hỗ trợ trên Windows CE 3.0 Ta nhận thấy, do cần phải thu gọn kiến trúc cũng như các hỗ trợ nhằm mục đích tối ưu tốc độ cho các thiết bị nhúng có tài nguyên giới hạn, Windows CE đã chỉ cung cấp một cách giới hạn các tính năng của GDI. Windows CE GDI không hỗ trợ các đặc tính: • Thay đổi toạ độ không gian, như SetMapMode, GetMapMode, SetViewportExt, và SetWindowExt. Tọa độ không gian sẽ tương ứng với không gian của thiết bị. • Các hàm World Transform API • Các hàm MoveTo và LineTo • Con trỏ có màu sắc, con trỏ động (animated) Và điều này cũng là một trong những lí do dẫn đến các thư viện đồ hoạ của MFC cũng không hỗ trợ rất nhiều hàm liên quan tới vấn đề hiển thị. Thử nhìn qua các hàm không được hỗ trợ hoặc hỗ trợ nhưng có thay đổi của CWnd, lớp đối tượng hiển thị chuẩn của MFC, trên môi trường Windows CE 3.0, ta đã thấy rất nhiều tính năng quan trọng cần phải sử dụng trong ứng dụng bản đồ không được hỗ trợ. Điều này sẽ gây khó khăn trong quá trình xây dựng chương trình. 23 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC ArrangeIconicWindows OnDeviceChange OnNcRButtonDown CancelToolTips OnDevModeChange OnNcRButtonUp ChangeClipboardChain OnDrawClipboard OnPaintClipboard CreateCaret OnDropFiles OnPaletteIsChanging CreateGrayCaret OnDSCNotify OnParentNotify DlgDirList OnEndSession OnQueryDragIcon DlgDirListComboBox OnEnterIdle OnQueryEndSession DlgDirSelect OnEnterMenuLoop OnQueryNewPalette DlgDirSelectComboBox OnExitMenuLoop OnQueryOpen DragAcceptFiles OnGetMinMaxInfo OnRButtonDblClk DrawMenuBar OnHScrollClipboard OnRButtonDown EnableScrollBar OnIconEraseBkgnd OnRButtonUp EnableToolTips OnInitMenu OnRegisteredMouseWheel FilterToolTipMessage OnMButtonDblClk OnSetCursor FlashWindow OnMButtonDown OnSizeClipboard GetClipboardViewer OnMButtonUp OnSizing GetDCEx OnMDIActivate OnSpoolerStatus GetDSCCursor OnMenuSelect OnStyleChanging GetLastActivePopup OnMouseActivate OnSysColorChange GetSystemMenu OnMouseWheel OnTimeChange GetUpdateRgn OnMoving OnToolHitTest GetWindowContextHelpIdOnNcActivate OnVScrollClipboard GetWindowPlacement OnNcCalcSize OnWindowPosChanging GetWindowRgn OnNcCreate SetClipboardViewer HiliteMenuItem OnNcHitTest SetMenu InvalidateRgn OnNcLButtonDblClk SetWindowContextHelpId IsZoomed OnNcLButtonDown SetWindowPlacement LockWindowUpdate OnNcLButtonUp SetWindowRgn OnActivateApp OnNcMButtonDblClkShowOwnedPopups OnAskCbFormatName OnNcMButtonDown ShowScrollBar OnChangeCbChain OnNcMButtonUp UnockWindowUpdate OnChildActivate OnNcMouseMove ValidateRgn OnCompacting OnNcPaint OnContextMenu OnNcRButtonDblClk Bảng 3-2: Các hàm thuộc CWnd không được hỗ trợ trên Windows CE 24 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC 3.3 Khả năng và hình thức lưu trữ Các Pocket PC thông thường có ROM ít nhất là 8MB, RAM ít nhất là 8MB. Các Pocket PC chuyên dụng có ROM ít nhất là 12MB, RAM ít nhất là 16MB. Tuy nhiên, yêu cầu về dung lượng của RAM và ROM tuỳ thuộc vào loại CPU sử dụng, những thành phần mà nhà sản xuất hỗ trợ trên Pocket PC và tuỳ thuộc vào loại Pocket PC. Do hạn chế về nguồn năng lượng pin và kích thước của thiết bị, Pocket PC không sử dụng các thiết bị lưu trữ như đĩa cứng hay đĩa mềm mà nó sử dụng một cơ chế gọi là Bộ lưu trữ đối tượng (Object store). Object store là một vùng RAM được người dùng định nghĩa, dùng để lưu trữ các tập tin, các thông tin registry và các database (gọi là Object Store dạng Storage). Vùng RAM còn lại dùng làm bộ nhớ cho các chương trình được thực thi (gọi là Object Store dạng Program). Object store vẫn lưu giữ được thông tin của các ứng dụng và dữ liệu ngay cả khi năng lượng cung cấp chính bị mất nhờ nguồn pin dự trữ. Có thể xem object store như là đĩa cứng trên thiết bị dùng Windows CE vì các end-user không biết về object store do Microsoft đã cung cấp trình WinCE Explorer để đọc nội dung của nó (tương tự như Microsoft Windows Expoler để đọc nội dung của đĩa cứng trên máy desktop PC) 3.3.1 Tập tin trên Windows CE Windows CE cung cấp một tập các hàm API cho phép lập trình viên truy xuất các tập tin cả trên ROM lẫn trên RAM. Điểm khác biệt chủ yếu đầu tiên mà ta cần lưu ý là object store trên Windows CE là việc thiếu các kí tự ổ đĩa. Windows CE sử dụng các thư mục dưới thư mục gốc cho việc cài đặt các thiết bị của người dùng. Ví dụ, nếu người dùng gắn một flash card vào máy, Windows CE sẽ tạo ra một thư mục /Storage Card 1. Cứ mỗi flash card được gắn vào, con số này sẽ tăng lên (/Storage Card 2,…) Đường dẫn tới tập tin được giới hạn bởi MAX_PATH (có thể dài tối đa 260 kí tự, giống như trên Windows) Tuy nhiên, trên Windows CE không có khái niệm thư mục hiện hành, ta phải truy xuất các tập tin bằng các đường dẫn dầy đủ của nó. 25 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC Trên Windows CE 2.0, các tập tin có kích thước tối đa là 4MB và số lượng tối đa trong object store là 65535. Trên Windows CE 3.0, kích thước tối đa cho một tập tin là 32MB, số lượng tối đa đối tượng lưu trữ trong object store là gần 4.000.000. Vì các tập tin có thể được lưu trữ trong cả RAM lẫn ROM, nên Windows CE cũng đã hỗ trợ một số thuộc tính tập tin như: FILE_ATTRIBUTE_NORMAL là thuộc tính mặc định của tập tin FILE_ATTRIBUTE_READONLY thiết lập thuộc tính chỉ đọc cho tập tin FILE_ATTRIBUTE_ARCHIVE thiết lập thuộc tính lưu trữ cho tập tin FILE_ATTRIBUTE_SYSTEM thiết lập thuộc tính hệ thống cho tập tin FILE_ATTRIBUTE_HIDDEN thiết lập thuộc tính ẩn cho tập tin FILE_ATTRIBUTE_INROM chỉ ra tập tin được lưu trữ trong ROM FILE_ATTRIBUTE_DIRECTORY chỉ ra tập tin là một thư mục FILE_ATTRIBUTE_TEMPORARY chỉ ra tập tin nằm trên một thiết bị do người dùng cài đặt như một PC card… 3.3.2 Cơ sở dữ liệu trên Windows CE Có thể xem Database trên Windows CE như một dạng tập tin đặc biệt, có tổ chức và cung cấp sẵn các thao tác. Giống như các cơ sở dữ liệu khác, Windows CE Database API giúp cho việc lưu trữ và tổ chức dữ liệu trở nên đơn giản hơn. Các ứng dụng internal như Contacts, Tasks… trên Windows CE là các ứng dụng sử dụng Database API để lưu trữ thông tin. Mỗi database là một tập các record chứa một hay nhiều thuộc tính thông tin và giá trị của nó. Database tạo bằng Database API có một số giới hạn: • Số thứ tự sắp xếp tối đa là 4 • Kích thước tối đa của thuộc tính là 64KB • Kích thước tối đa của record là 128KB • Database của Windows CE chỉ có một cấp 26 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC • Không hỗ trợ khoá (locking) database, chỉ cung cấp notification khi thay đổi xảy ra • Các record không được chứa các record khác hay chia xẻ giữa các database với nhau Các database phức tạp có quan hệ cũng không được hỗ trợ trên Pocket PC và Windows CE 3.0. Thay vào đó, Database API nên được dùng để lưu trữ các thông tin quan hệ đơn giản như danh sách mua hàng, hay thông tin liên lạc cá nhân… Mỗi thuộc tính của database được định nghĩa với một kiểu dữ liệu xác định. Các kiểu dữ liệu được hỗ trợ trên database của Windows CE gồm Thuộc tính Mô tả CEVT_BLOB Một khối nhớ, lưu trữ theo cấu trúc CEBLOB CEVT_FILETIME Cấu trúc FILETIME CEVT_I2 Số nguyên 16-bit có dấu CEVT_I4 Số nguyên 32-bit có dấu CEVT_LPWSTR Một chuỗi null-terminated CEVT_U12 Số nguyên 16-bit không dấu CEVT_U14 Số nguyên 32-bit không dấu CEVT_BOOL Giá trị luận lý (có từ Windows CE 2.1) CEVT_R8 Số thực double 64-bit có dấu (có từ Windows CE 2.1) Bảng 3-3: Các kiểu dữ liệu được hỗ trợ trên database của Windows CE Bắt đầu từ Windows CE 2.1, database có thể nằm trên các thiết bị ngoài như flash card. Người sử dụng có thể mount database để sử dụng trên thiết bị, Database trên windows CE hỗ trợ các thao tác: Tạo database, mở database, sắp xếp trên database, đọc dữ liệu từ database, ghi xuống database, tìm kiếm trên database. Sử dụng tập tin hay database là một vấn đề cần được xem xét khi tổ chức lưu trữ dữ liệu GIS trên Pocket PC. 27 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC 3.4 Cấp phát bộ nhớ Đối với ứng dụng bản đồ, một vấn đề thường gặp là phải cấp phát bộ nhớ nhiều lần. Việc sử dụng dư thừa hay sai sót trong cấp phát, giải phóng bộ nhớ có thể để lại hậu quả rất nghiêm trọng, đặc biệt là khi số lượng đỉnh của đồ thị là rất lớn. Trên môi trường Pocket PC, việc để lại những vùng nhớ dư thừa sẽ làm chậm toàn bộ hệ thống, đồng thời xảy ra những lỗi rất nghiêm trọng, do dung lượng bộ nhớ không nhiều. Windows CE sử dụng các hàm API liên quan tới bộ nhớ ảo để cấp phát bộ nhớ cho vùng heap và stack. Điểm lợi của sử dụng bộ nhớ ảo là bộ nhớ ảo không phân mảnh: Windows CE luôn cấp phát một số nguyên các trang. Vì Windows CE quản lý bộ nhớ ảo theo các khối 64KB, do đó khi chương trình không sử dụng hết vùng nhớ 64KB thì nên dùng một vùng nhớ heap để tránh lãng phí. 3.4.1 Các cơ chế sử dụng bộ nhớ • Local Heap Heap là một vùng không gian bộ nhớ ảo dự trữ mà Windows CE quản lý để cấp phát cho chương trình. Kích thước của heap khoảng 4bytes hay 8bytes, tùy thuộc loại CPU • Separate Heap Thay vì tăng thêm kích thước heap cục bộ, ta nên tạo một vài vùng heap nhỏ nhằm tăng tính hiệu quả. • Stack Stack là một vùng nhớ lưu trữ cho các biến được tham chiếu trong một hàm. Windows CE cấp phát bộ nhớ cho một biến từ stack và thu hồi bộ nhớ sau khi hàm hoàn tất. Khi một tiến trình hay tiểu trình bắt đầu, Windows CE cấp phát một trang bộ nhớ stack cho tiểu trình đó. Mỗi tiểu trình có một stack và mỗi stack có một vùng 2KB cuối cùng để điều khiển tràn stack. • Static data block Khổi dữ liệu tĩnh (Static data block) là một khối nhớ mà Windows CE dành cho chương trình. Khối này chứa chuỗi, buffer, và các giá trị tĩnh khác mà chương 28 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC trình sử dụng trong suốt quá trình thực thi. Ta có thể giảm kích thước của các khối dữ liệu bằng cách khai báo dữ liệu trong phần read/write với khai báo const. 3.4.2 Nhận biết tình trạng thiếu bộ nhớ Cho dù cấp phát bộ nhớ hiệu quả thế nào và chương trình có sử dụng bộ nhớ RAM hiệu quả thế nào, thiết bị Pocket PC vẫn có thể bị thiếu bộ nhớ. Ở mức độ lập trình, ta có thể biết được tình trạng thiếu bộ nhớ theo những cách sau: • Hàm Virtual Alloc trả về 0, cho biết cấp phát không thành công • LocalAlloc hoặc HeapAlloc trả về 0, cho biết việc tăng kích thước vùng heap không thành công • Windows CE trả về một lỗi stack cho chương trình, cho biết cấp phát stack không thành công. • Khi một chương trình có yêu cầu cấp phát bộ nhớ, Windows CE kiểm tra và lọc yêu cầu, nhằm tránh việc sử dụng tất cả bộ nhớ có sẵn cho một cấp phát lớn. Khi Windows CE bước vào tình trạng thiếu bộ nhớ, nó sẽ giảm giới hạn bộ nhớ tối đa cho chương trình • Windows CE gửi thông điệp WM_HIBERNATION tới các ứng dụng nhằm thông báo tình trạng thiếu bộ nhớ. 3.5 Tương tác giữa người sử dụng và thiết bị Người sử dụng tương tác với thiết bị thông qua một màn hình touch-screen LCD (màn hình cảm nhận). Không sử dụng bàn phím (keyboard) và chuột (mouse) thông thường, Pocket PC hỗ trợ nhập liệu thông qua một bàn phím logic, gọi là SIP (Soft Input Panel). Bàn phím logic này thực chất là một khung cửa sổ luôn tồn tại trên màn hình, mô tả và sắp xếp các phím tương tự trên máy PC thông thường. Người dùng sẽ giao tiếp với SIP thông qua ngón tay hoặc stylus (một cây viết vật lý, cho phép nhập liệu bằng cách viết trực tiếp lên màn hình) 29 KH OA C NT T – Đ H KH TN Chương 3 :Một số vấn đề khi xây dựng ứng dụng bản đồ trên Pocket PC Thay thế cho việc nhấn Enter hay nhấn đúp chuột, Pocket PC sử dụng cơ chế single-tapping (nhấn đơn) lên touch screen. Người dùng chỉ cần nhấn một lần lên một đối tượng hoặc liên kết, hệ điều hành sẽ mở đối tượng/liên kết tương ứng. Ngoài ra, để giao tiếp với ứng dụng, người dùng có thể nhấn-và-giữ (tap-and- hold). Đây là cơ chế có tác dụng tương tự như việc sử dụng context-menu bằng cách nhấn phải chuột trên PC. Khi người dùng nhấn-và-giữ trên một đối tượng, có thể một menu hoặc một tooltip sẽ hiện ra, tuỳ theo đối tượng đó xử lý như thế nào. Trong ứng dụng bản đồ, ta nhận thấy việc nghiên cứu và xử lý các cách tương tác trên là rất cần thiết, bởi trong dạng ứng dụng này, việc di chuyển, phóng to, thu nhỏ, tra cứu bản đồ là những hành động rất thường xuyên xảy ra. Bên cạnh đó, phải định nghĩa lại trong ứng dụng các hardware keys (phím vật lý) nhằm tận dụng các phím di chuyển sẵn có của thiết bị Pocket PC nhằm tăng tốc độ tương tác cho người dùng khi xem bản đồ. 30 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC Chương 4 : Các giải pháp cho ứng dụng bản đồ trên Pocket PC 4.1 Yêu cầu chung Các ứng dụng liên quan tới hệ thống thông tin địa lý (Geography Information System – GIS) phát triển trên Pocket PC và hệ điều hành Windows CE gặp phải các vấn đề về tối ưu hoá bộ nhớ cũng như tốc độ ứng dụng do những vấn đề đã trình bày ở phần trên. Khi đưa ra các giải pháp cho ứng dụng bản đồ trên Pocket PC, cần phải • Bảo đảm việc tổ chức lưu trữ thông tin và dữ liệu tối ưu trên Object Store dạng Program • Bảo đảm lưu trữ ít nhất thông tin có thể trên Object Store dạng Storage • Bảo đảm được tốc độ khi xử lý tính toán để hiển thị và tìm kiếm, tra cứu thông tin. 4.2 Vấn đề tối ưu tốc độ hiển thị 4.2.1 Cơ chế xác định vùng vẽ Để hiển thị bản đồ cho người dùng quan sát, bất cứ một chương trình bản đồ nào cũng phải vẽ lên màn hình. Và phần hiển thị lên màn hình sẽ là phần mà người dùng đang muốn xem xét để có thông tin. Người dùng cũng có thể thay đổi vùng nhìn của bản đồ và sự thay đổi vùng nhìn của người dùng này sẽ kéo theo các thao tác vẽ lại bản đồ. Khi vẽ lại bản đồ nếu mọi thứ đều được vẽ thì có nghĩa là tất cả các đường, các tên đường, các địa điểm... nằm trên vùng nhìn thấy hoặc không nằm trên vùng nhìn thấy đều được vẽ lại. Điều này có thể không gây ra vấn đề kĩ thuật nào trên các máy tính để bàn Desktop nếu như kích thước bản đồ nằm trong kích thước cho phép của thiết bị (toạ độ từ -32768 đến 32767). Lý do giúp ta có thể vẽ lại toàn bộ bản đồ 31 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC mà vẫn làm người sử dụng chấp nhận được là nhờ vào tốc độ tính toán và hiển thị rất nhanh của các thế hệ máy tính để bản hiện nay. Tuy nhiên như đã đề cập ở trên, kích thước hiển thị nằm trong vùng giới hạn từ -32768 đến 32767, nên nếu một bản đồ có toạ độ nằm ngoài vùng giới hạn trên thì khi vẽ sẽ bị sai thông tin vì tràn số. Do lý do trên, ta cần áp dụng giải pháp nhằm tính toán lại các vùng cần vẽ. Giải pháp này giúp chương trình chỉ vẽ những đối tượng nào nằm trong vùng nhìn thấy, còn các đối tượng nằm ngoài vùng nhìn thấy sẽ được bỏ qua. Tuy nhiên với cách tiếp cận này cũng còn điểm hạn chế. Nếu một đối tượng nằm trong vùng nhìn thấy thì đối tượng đó sẽ được vẽ. Điều đó có nghĩa là đối tượng có một phần nằm trong vùng nhìn thấy và một phần nằm ngoài vùng nhìn thấy sẽ được vẽ. Đối tượng nằm hoàn toàn trong vùng nhìn thấy cũng sẽ được vẽ. Với đối tượng nằm hoàn toàn trong vùng nhìn thấy thì việc vẽ hoàn toàn đối tượng là hợp lý. Nhưng đối với đối tượng chỉ có một phần nằm trong vùng nhìn thấy thì việc vẽ toàn bộ đối tượng cần phải được cân nhắc. Trên máy tính để bản việc vẽ hoàn toàn một đối tượng chỉ có một phần nằm trong vùng nhìn thấy không ảnh hưởng gì nhiều đối với tốc độ vẽ và tốc độ tính toán. Nhưng đối với chương trình chạy trên PocketPC sẽ là một vấn đề đáng quan tâm. Có thể kiểm tra tốc độ hỗ trợ về việc vẽ đối tượng của Windows CE 3.0 bằng việc vẽ một số đối tượng cơ bản như đường thẳng, hình chữ nhật, hình đa giác. Thực hiện các phép tịnh tiến để thay đối vùng nhìn ta có thể cảm nhận được tốc độ của việc vẽ đối tượng rất rõ rệt. Chính vì hạn chế tốc độ vẽ trên Windows CE 3.0 cho nên việc vẽ một đối tượng cần được cân nhắc rất kĩ lưỡng. Với đối tượng chỉ có một phần nằm trong vùng nhìn thấy thì chỉ nên vẽ phần nhìn thấy của đối tượng, phần khuất của đối tượng không cần vẽ. Từ các phân tích trên ta có các vấn đề cần giải quyết như sau: Các đối tượng nào có thể nhìn thấy (nhìn thấy một phần hoặc toàn bộ) Đối với các đối tượng nhìn thấy một phần thì phải xác định phần nhìn thấy của đối tượng 32 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC Có một số biện pháp để giải quyết vấn đề 4.2.1.1 Các đối tượng nào có thể nhìn thấy Việc trước tiên trong quá trình cải tiến tốc độ vẽ đó là xác định xem đối tượng nào có thể nhìn thấy. Ta xem xét vấn đề sau: Cho một điểm hỏi có thể nhìn thấy điểm này hay không ? Đối với các đối tượng là điểm thì chỉ cần các định xem điểm đó có nằm trong vùng nhìn thấy hay không. Cho một đường thẳng hỏi đường thẳng này có thể nhìn thấy hay không? Câu trả lời cho vấn đề này rất đơn giản. Ta chỉ việc xem đường thẳng trên có giao với vùng nhìn hay không. Nếu như đường thẳng có giao với vùng nhìn thì đường thẳng được xem là đối tượng có thể nhìn thấy. Ngược lại đường thẳng không thể nhìn thấy Hình 4-1: Đoạn thẳng giao vùng nhìn Một câu hỏi khác lại đặt ra, cho một cung gồm nhiều đoạn thẳng nối với nhau hỏi cung này có thể nhìn thấy hay không. Nhận xét: Cung có thể nhìn thấy nều như ta nhìn thấy toàn bộ cung hoặc một phần của cung. Nhìn thấy toàn bộ cung có nghĩa là tất cả các đoạn thẳng của cung đều nằm hoàn toàn trong vùng nhìn thấy. Nhìn thấy một phần của cung có nghĩa là nhìn thấy ít nhất một đoạn thẳng hoặc một phần đoạn thẳng của cung. 33 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC Vì vậy để xác định xem cung có thể nhìn thấy hay không ta chỉ việc xác định kiểm tra tất cả các đoạn thẳng của cung. Nếu có đoạn thẳng nhìn thấy thì có nghĩa là cung nhìn thấy được. Nếu không nhìn thấy tất cả các đoạn thẳng của cung có nghĩa là cung không nhìn thấy được Hình 4-2: Cung giao vùng nhìn Đối với các đối tượng là các đường khép kín thì cũng tương tự như là một cung có điểm đầu trùng với điểm cuối. Như vậy ta có thể xác định được các đối tượng nhìn thấy theo cách phân tích trên. Tuy nhiên với cách này thì để xác định một cung có thể nhìn thấy hay không ta phải duyệt tất cả các đoạn thẳng của cung. Một phí tổn rất lớn nếu như ta duyệt nhiều cung. Do đó một cải tiến Heuristic được đưa ra là sử dụng hình chữ nhật bao. Nhận xét: Mỗi cung đều có một hình chữ nhật bao có góc trên trái (xmin,ymin) và góc dưới phải (xmax,ymax). xmin=min( tất cả các x của các đường của cung) ymin=min( tất cả các y của các đường của cung) xmax=max(tất cả các x của các đường của cung) 34 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC ymax=max(tất cả các y của các đường của cung) • Nếu hình chữ nhật bao này không giao với vùng nhìn thấy thì chắc chắn cung không nhìn thấy được. • Nếu như hình chữ nhật bao này giao với vùng nhìn thấy thì có thể xảy ra các trường hợp sau: o Có thể cung nhìn thấy được o Có thể cung không nhìn thấy được Như vậy, phạm vi các cung cần duyệt đã được thu hẹp. Chỉ các cung có hình chữ nhật bao giao với vùng nhìn thấy mới được xem xét nhằm vẽ lại trên màn hình. 4.2.1.2 Phân vùng cho các đối tượng. Bản đồ sẽ được chia ra thành nhiều phần bằng nhau. Mỗi phần là một hình chữ nhật. Trong mỗi hình chữ nhật ta sẽ xác định các đối tượng giao với hình chữ nhật đó. Khi cập nhật lại vùng vẽ ta chỉ cần xác định xem những hình chữ nhật nào giao với vùng vẽ. Sau đó vẽ các đối tượng của các hình chữ nhật. Với ý tưởng trên ta chỉ làm phép duyệt trên một số ít hình chữ nhật là ta có thể biết ngay các đối tượng cần vẽ, không phải duyệt các đối tượng. Do đó cải tiến tốc độ duyệt. Tuy nhiên việc cải tiến tốc độ này không nâng lên đáng kể. Khi ta chia bản đồ thành nhiều hình chữ nhật thì một đối tượng có thể thuộc nhiều hình chữ nhật khác nhau. Do đó khi duyệt có thể xảy ra hiện tượng trùng lắp. 4.2.1.3 Đánh giá Để xác định các hình chữ nhật và các đối tượng giao với nhìn chữ nhật thì cần có một chi phí nhất định ban đầu để tính xem đối tượng nào giao với hình chữ nhật nào. Để lưu trữ thông tin về các đối tượng của hình chữ nhật thì cần chi phí bộ nhớ. Chi phí này có thể không đáng kể trên các ứng dụng chạy trên các máy để bàn. Nhưng là rất đáng kể đối với các ứng dụng chạy trên PocketPC. Vì vậy ta có thể sử dụng giải pháp ban đầu là xác định vùng bao các cung mà không dùng giải pháp chia bản đồ. Điều này không làm giảm tốc độ vẽ. Hơn nữa với giải pháp xác định vùng bao các cung ta còn có thể cải tiến để tăng tốc độ duyệt. 35 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC Nhận xét rằng: mỗi cung chỉ thuộc một con đường, mỗi con đường bao gồm nhiều cung. Như vậy thay vì duyệt tất cả các cung để so sánh vùng bao thì ta có thể duyệt tất cả các con đường. Sau đó ta mới duyệt tất cả các cung của con đường giao với vùng bao. Rõ ràng cách làm này tương tự như cách làm chia bản đồ ra làm nhiều phần bằng nhau. Vì các cung đều được đánh dấu vào một hình chữ nhật nào đó. Ở giải pháp chia bản đồ ra làm nhiều phần thì hình chữ nhật chia là bằng nhau đối với tất cả các phần. Ở giải pháp vẽ theo con đường thì các hình chữ nhật có thể thay đối kích thước tùy thuộc vào con đường. Điều này sẽ làm cho phép chia trở nên linh động hơn, đồng thời cũng tránh được sự trùng lắp thông tin. Tóm lại mô hình để xác định các đối tượng nhìn thấy như sau: Gọi MBR(o) là hình chữ nhật bao của đối tượng o P= { p các con đường \ MBR(p) ∩ MBR(vùng nhìn) } A={ a các cung ∈ P \ MBR(a) ∩ MBR(vùng nhìn) } L={ l các đoạn ∈ A \ l ∩ MBR(vùng nhìn) } 4.2.1.4 Xác định phần nhìn thấy của đối tượng Theo phân tích phần trên ta đã xác định được các đối tượng có thể nhìn thấy. Bây giờ ta tiến hành xem xét chi tiết đối tượng nào thực sự được nhìn thấy. Dựa vào mô hình trên ta có như sau P= { p các con đường \ MBR(p) ∩ MBR(vùng nhìn) } A={ a các cung ∈ P \ MBR(a) ∩ MBR(vùng nhìn) } L={ l các đoạn ∈ A \ l ∩ MBR(vùng nhìn) } Bây giờ ta xác định L bằng cách xây dựng một thuật toán để xác định phần giao của l với vùng nhìn. Ta có thể sử dụng thuật toán LiangBarsky cho việc xén đoạn thẳng trong một hình chữ nhật (tham khảo [ 1] ) Với các đối tượng là các đa giác ta sử dụng thuật toán xén đa giác Sutherland-Hodgeman (tham khảo [ 1] ) 36 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC 4.2.2 Cơ chế sử dụng bộ đệm Việc vẽ một đối tượng lên màn hình bao gồm các thao tác. • Điều chỉnh đối tượng theo tỉ lệ (zoom) • Tịnh tiến đối tượng từ vùng vẽ lên vùng hiển thị • Vẽ đối tượng Như vậy ta thấy việc chỉnh tỉ lệ sẽ được thực hiện lại mỗi khi thay đổi vùng vẽ, điều này sẽ làm mất một khoảng thời gian cho việc tính toán tỉ lệ (phải sử dụng phép chia). Giải pháp đưa ra là: Nếu như là lần đầu tiên vẽ thì ta thực hiện phép toán tỉ lệ trên đối tượng và đưa vào vùng nhớ tạm Đến lần thực hiện tiếp theo, vì đã thực hiện việc tỉ lệ (zoom) ở bước vẽ trước đó cho nên không cần thực hiện lại thao tác này. Ta chỉ cần truy xuất đến vùng nhớ đệm chứa thông tin đối tượng đã được tỉ lệ. Thông tin đó là các toạ độ hiển thị đã được thực hiện tỉ lệ (zoom). Điều này tiết kiệm được nhiều phép tính toán trên đối tượng, dẫn đến tiết kiệm được tổng thời gian tính toán nhằm hiển thị bản đồ. Sau cùng ta chỉ phải thực hiện việc tính tiến đối tượng từ vùng vẽ đến vùng hiển thị và vẽ đối tượng 37 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC Đối tượng cần vẽ Đúng SaiVẽ lần đầu tiên ? Thực hiện thao tác tỉ lệ (zoom) Lấy thông tin đã tỉ lệ (zoom) từ vùng đệm Tịnh tiến đối tượng đến vùng vẽ Lưu vào vùng đệm Vẽ đối tượng Hình 4-3: Lưu đồ vẽ đối tượng 4.3 Tìm đường đi ngắn nhất 4.3.1 Các thuật toán tìm kiếm 4.3.1.1 Đặt vấn đề Đối với các ứng dụng GIS, một trong những vấn đề cơ bản cần được giải quyết là tìm đường đi giữa hai điểm trên bản đồ và các bài toán liên quan (tìm đường đi ngắn nhất, tìm đường đi với các ràng buộc có ghé qua hoặc phải tránh một số điểm, các bài toán phân phối như điều phối giao thông, giao hàng...). Các nghiên cứu về Trí tuệ nhân tạo và Lý thuyết đồ thị đã đặt những nền tảng hết sức vững chắc cho việc biểu diễn và giải quyết các bài toán như trên với nhiều thuật toán tìm kiếm khác nhau. Trong khuôn khổ luận văn, chúng em xin trình bày một số vấn đề liên quan đến 2 thuật toán tìm kiếm trên đồ thị phổ biến và thường được sử dụng trong các ứng dụng GIS là Dijkstra Moore (tìm đường cho các đồ thị đơn có trọng số của 38 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC các cung không âm) và A* (tìm đường heuristic trên đồ thị tổng quát) đối với môi trường Pocket PC và Windows CE 3.0. Trước khi xem xét hai thuật giải tìm đường này, ta có một số quy ước đối với bài toán tìm kiếm đường đi ngắn nhất trên đồ thị G: Kí hiệu Mô tả u0 Đỉnh xuất phát goal Đỉnh kết thúc close Tập các đỉnh đóng (các đỉnh đã được xem xét và được xác định chính xác đường đi ngắn nhất open Tập các đỉnh mở (các đỉnh còn lại) l[i,j] Trọng số của cung (i,j) d[i] Khoảng cách min từ i đến u0 v[i] Khoảng cách min được ước lượng từ i đến goal Bảng 4-1: Quy ước ký hiệu trong thuật toán tìm dường đi ngắn nhất Như vậy, nhiệm vụ của các thuật toán tìm đường là xác định được giá trị d[goal] – giá trị thể hiện đường đi ngắn nhất giữa hai đỉnh xuất phát và kết thúc trên đồ thị. 4.3.1.2 Tìm đường đi ngắn nhất bằng Dijkstra Moore Thuật toán Dijkstra Moore được trình bày như sau: d[i]= +∝ ∀i∈[1..n] close=[u0] open=[1..n]-[u0] k=u0 repeat {sửa đổi ước lượng min} ∀i∈open 39 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC d[i]=min {d[i],d[k]+l[k,i]} {mở rộng tập close} chọn k ∈ open sao cho ∀i∈open thoả điều kiện d[k] ≤ d[i] open=open-[k] close=close+[k] until goal ∈ close 4.3.1.3 Tìm đường đi ngắn nhất bằng A* Các thuật toán cổ điển như Dijkstra được xây dựng trên các mô hình thuần tuý lí thuyết, trong đó đồ thị được coi là tập hợp các đỉnh và cung nối giữa các đỉnh đó, ngoài ra, không có bất kì một thông tin bổ sung nào cho bài toán. Chúng chỉ tìm lời giải dựa trên việc duyệt lần lượt từ đỉnh này sang đỉnh khác mà không sử dụng “khả năng phán đoán học được” (heuristic). Thông tin heuristic, dù không chính xác và đảm bảo, nó làm tăng các cơ hội để việc tìm kiếm tiến tới đích nhanh hơn, tối ưu hoặc cả hai. tóm lại nó làm tăng tốc độ và tỉ lệ thành công. (Tham khảo [ 3] ) Đối với các bài toán tìm đường trên thực tế, đồ thị thường có số đỉnh lớn đến rất lớn, song các đồ thị này luôn cung cấp thêm các thông tin phụ giúp chúng ta định hướng tốt hơn trong quá trình tìm lời giải. Thuật giải A* áp dụng trong tìm đường là thuật giải dựa trên Dijkstra, với tư tưởng tìm đường dựa trên chiến lược tìm kiếm theo chiều rộng. d[i]= +∝ ∀i∈[1..n] close=[u0] open=[1..n]-[u0] k=u0 repeat {sửa đổi ước lượng min} ∀i∈open 40 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC d[i]=min {d[i],d[k]+l[k,i]} {mở rộng tập close} chọn k ∈ open sao cho ∀i∈open thoả điều kiện (d[k]+v[k]) ≤ (d[i]+v[i]) open=open-[k] close=close+[k] until goal ∈ close Theo chứng minh lý thuyết, nếu các trọng số của đồ thị G đều là dương (l[i,j]>0 ∀i, j) và v[i] đều là lượng giá dương thấp hơn đường đi ngắn nhất từ đỉnh i đến u0 (0<v[i]<d[i] ∀i), thì thuật toán A* luôn cho kết quả đúng và không bao giờ yêu cầu nhiều thời gian hơn thuật toán Dijkstra. Như vậy, ta nhận thấy, thứ nhất, thuật toán Dijkstra có thể được xem là trường hợp “suy biến” của A* trong trường hợp v[i]=0; thứ hai, nếu v[i] là ước lượng đúng thi thuật toán A* có độ phức tạp thời gian là tuyến tính. (Tham khảo [ 5] ) 4.3.2 Áp dụng Xây dựng hàm ước lượng trong thuật toán A* ứng dụng trong việc tìm kiếm lời giải của các bài toán là vấn đề rất đa dạng và được sử dụng tuỳ thuộc vào các bài toán khác nhau. Từ các nhận định và trình bày trên, do đặc điểm của môi trường cài đặt và áp dụng là Pocket PC và Windows CE 3.0, cũng như ứng dụng là một ứng dụng GIS, chúng em quyết định sử dụng thuật toán A* với hàm ước lượng được xây dựng dựa trên khoảng cách Euclide giữa hai điểm trên mặt phẳng. Thông tin heuristic này được sử dụng với mục đích cho rằng khoảng cách từ điểm đang xét tới đích càng gần thì điểm đang xét càng có nhiều khả năng được chọn là điểm kế tiếp. 41 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC 4.4 Tìm kiếm thông tin phi không gian Tìm kiếm thông tin về các con đường, quận huyện, địa danh, cơ quan, xí nghiệp... nhằm mục đích tra cứu, biết chi tiết các thông tin về đối tượng là một trong những yêu cầu cơ bản của một ứng dụng GIS. Có nhiều cách lưu trữ thông tin, thể hiện và cơ chế phục vụ người sử dụng tìm kiếm thông tin khác nhau. 4.4.1 Lưu trữ và biểu diễn thông tin Tìm kiếm thông tin phi không gian liên quan trực tiếp tới việc sử dụng các cấu trúc dữ liệu thích hợp để lưu trữ và biểu diễn các thông tin cần thiết. Nếu so sánh, thì có thể nói việc tìm kiếm thông tin này tương đối giống với việc tra cứu nghĩa của một từ trong từ điển. Tuy nhiên, khác với từ điển, đối với một ứng dụng GIS, một số thông tin cần tìm kiếm, hoặc có thể đã được lưu trữ sẵn, hoặc cũng có thể được phát sinh tại thời điểm tra cứu. Điều này dẫn đến việc phải tính toán nên chọn lựa hình thức cung cấp thông tin nào (lưu trữ trước hoặc phát sinh tại thời điểm tra cứu). Sau đó, dựa vào hình thức này mới quyết định cấu trúc dữ liệu thích hợp để biểu diễn trong ứng dụng. Việc chọn lựa này đặc biệt quan trọng trong môi trường Windows CE, với tài nguyên và tốc độ xử lý chậm. Xem xét trên một số thông tin phụ tiêu biểu ở đây, liên quan đến đường, bao gồm: tổng chiều dài con đường, đường này giao với những đường nào, đường này thuộc quận nào... 4.4.1.1 Lưu trữ thông tin trên Object Store Các thông tin phụ có thể được lưu trữ trong Object Store trước khi thực thi ứng dụng. Theo đó, để giải quyết vấn đề, sẽ phải qua các bước sau: • Nhận thông tin tra cứu từ người sử dụng • Tra cứu để tìm vị trí thông tin tương ứng dựa trên một ID duy nhất • Truy xuất Object Store để cung cấp cho người sử dụng Do Object Store là cơ chế sử dụng bộ nhớ RAM, nên việc tra cứu này nếu dựa trên các đối tượng file hoặc database có cấu trúc rõ ràng và dễ tra cứu thì chi phí thời gian bỏ ra không đáng kể so với cơ chế tìm kiếm trên bộ nhớ ngoài trên 42 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC môi truờng Windows desktop. Tuy nhiên, ta sẽ phải tốn thêm một vùng nhớ Object Store cho các thông tin cần được lưu trữ sẵn, trong khi khả năng lưu trữ của Pocket PC bị hạn chế. 4.4.1.2 Tính toán tại thời điểm tra cứu Các thông tin cần tra cứu sẽ được tính toán, kết xuất từ các thông tin khác liên quan đã được lưu trữ trước đó. Ví dụ, chiều dài con đường sẽ bằng tổng chiều dài của các cung và cung con thuộc con đường ấy. Để tính toán được giá trị cần thiết, phải sử dụng các phép toán so sánh đối với tất cả các cung tồn tại trong đồ thị để tìm các cung thuộc con đường tra cứu, sau đó là phép cộng số thực để ra được chiều dài. Có hai vấn đề ở đây: thứ nhất, nếu tính chiều dài cho tất cả các con đường, số phép tính là rất lớn. Tuy nhiên, ở đây, chỉ cần thiết tính chiều dài của một con đường đang được tra cứu, vì vậy có thể chấp nhận được; thứ hai, các thông tin liên quan đến quá trình tra cứu đã được tạo lập trước trong quá trình nạp dữ liệu hiển thị cho bản đồ từ các dữ liệu cần thiết. Nói cách khác, các thông tin này đã được biểu diễn trước đó theo một cấu trúc định sẵn trong bộ nhớ, có nghĩa là không cần tốn thêm không gian Object Store để lưu trữ. 4.4.2 Thể hiện và cơ chế tìm kiếm 4.4.2.1 Các hướng tiếp cận • Phương pháp tiếp cận thứ nhất: Hiển thị tất cả các đối tượng cần tìm kiếm(đường, quận huyện, địa danh, bệnh viện, công ty...) hoặc tra cứu trong một danh sách. Khi người dùng nhập vào tên một đối tượng, ứng dụng sẽ tìm kiếm gần đúng trong danh sách, tất cả các đối tượng liên quan (theo tên, tính chất) và làm tươi lại (refresh) danh sách với các đối tượng tìm thấy này. • Phương pháp tiếp cận thứ hai: Hiển thị tất cả các đối tượng cần tìm kiếm (đường, quận huyện, địa danh, bệnh viện, công ty...) hoặc tra cứu trong một danh sách. Khi người dùng nhập 43 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC vào tên một đối tượng, ứng dụng sẽ tìm kiếm đối tượng gần đúng nhất (theo tên) và đánh dấu chọn đối tượng này. Nếu chưa vừa ý, người dùng tiếp tục nhập thêm thông tin, và ứng dụng phản hồi theo cơ chế tương tự. 4.4.2.2 Đánh giá Phương pháp tiếp cận thứ nhất: Giải pháp kĩ thuật: • Xét trên khía cạnh gần đúng về tên, ứng dụng sẽ phải duyệt hết toàn bộ tên các đối tượng. Với mỗi tên này, phải duyệt để xem tên đối tượng tra cứu có phải là chuỗi con của tên đối tượng hiện thời không. Nếu đúng, cập nhật vào danh sách. • Xét trên khía cạnh gần đúng về tính chất, dựa trên tên được tra cứu để xác định tính chất của đối tượng (đường phố, bệnh viện...). Duyệt qua tất cả đối tượng, cập nhật các đối tượng có tính chất thích hợp vào danh sách. Ưu điểm: • Tìm kiếm được tất cả đối tượng liên quan Khuyết điểm: • Do phải tìm tất cả các đối tượng liên quan, nên tốc độ xử lý chậm, đặc biệt là đối với môi trường Windows CE. Phương pháp tiếp cận thứ hai: Giải pháp kĩ thuật: • Biểu diễn các thông tin tìm kiếm bằng các cấu trúc dữ liệu thích hợp. Với các thông tin do người dùng nhập vào, sử dụng các phép duyệt, tra cứu trên cấu trúc dữ liệu này để tìm ra đối tượng gần đúng nhất Ưu điểm: • Nhanh, sử dụng các phương pháp tìm kiếm trên các cấu trúc dữ liệu đã được nghiên cứu Khuyết điểm: • Cài đặt phức tạp hơn 44 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC • Không bảo đảm tìm được tất cả các đối tượng đúng tính chất của đối tượng cần tra cứu 4.5 Giải pháp tiếng Việt trên môi trường Pocket PC 4.5.1 Tiếng Việt Unicode Đầu thập niên 90, Tổ chức tiêu chuẩn quốc tế ISO đưa ra dự án thống nhất bảng mã trên toàn thế giới và gọi đó là dự án ISO-10646. Cùng lúc đó, Unicode - Hiệp hội các nhà phát triển phần mềm, được thành lập vào năm 1991 như 1 tổ chức phi lợi nhuận nhằm phát triển chuẩn Unicode, các thành viên của Unicode bao gồm các công ty hàng đầu của thế giới trong lĩnh vực phần mềm như Microsoft, Adobe, Aldus, Borland, Digital, GO, IBM, HP, Lotus, Metaphor, NeXT, Novell, Sun, Symantec, Taligent, Unisys, and WordPerfect... cũng đưa ra dự án Unicode với với tham vọng trên. Rất may mắn là sau đó, cả 2 tổ chức đã nhận ra không cần thiết phải đưa ra 2 dự án khác nhau và đã hợp sức để hoàn thành. Tuy nhiên, ISO vẫn gọi là ISO- 10646, còn Unicode thì vẫn gọi là Unicode. Unicode sử dụng 4 byte để biểu diễn 1 kí tự và có khả năng biễu diễn 231(khoảng 2 tỷ) kí tự. Unicode được chia ra thành nhiều mặt phẳng (plane) biểu diễn, mỗi mặt phẳng gồm 65536 kí tự, được đánh số từ 0. Unicode mới tìm được khoảng 1 triệu kí tự được sử dụng trong tất cả các ngôn ngữ trên thế giới, trong đó, có 65534 kí tự thông dụng nhất. Như vậy, để biểu diễn các kí tự này, chỉ cần mặt phẳng đầu tiên trong bảng mã Unicode là đủ biểu diễn. Mặt phẳng này gọi là BMP0 (Basic Multilingual Plane) Với 65.536 ký tự của BMP0, Unicode hầu như có thể mã hoá tất cả các ngôn ngữ trên thế giới. Ngoài ra với cơ chế mở rộng UTF-16 Unicode và chuẩn ISO 10646 còn cho phép mã hoá hơn 1 triệu ký tự mà không cần phải dùng đến mã điều khiển Escape. 45 KH OA C NT T – Đ H KH TN Chương 4 :Các giải pháp cho ứng dụng bản đồ trên Pocket PC Phiên bản mới nhất hiện nay là Unicode 2.0 (Bản 3.0 đang chuẩn bị phát hành) bao gồm các ngôn ngữ thuộc họ la-tinh, và Greek, Cyrillic, Armenian, Hebrew, Arabic, Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, Malayalam, Thai, Lào, Georgian, Tibetan, Japanese Kana, toàn bộ tập kí tự Korean Hangul hiện đại, tập kí tự thống nhất tiếng Trung Quốc/ Nhật Bản/ Hàn Quốc (Chinese/Japanese/Korean-CJK). * Một số đặc điểm của Unicode: -Unicode về cơ bản không quy định việc bố trí các ký tự theo quy định sắp xếp của các ngôn ngữ, điều này cũng là hệ quả của việc tránh định nghĩa các ký tự dư thừa do phải tận dùng các ký tự dùng chung nên không thể bố trí các ký tự theo từng vùng riêng cho từng ngôn ngữ. Hơn nữa thực tế với nhiều ngôn ngữ người ta phải dùng những thuật toán riêng để sắp xếp chứ không thể sắp xếp theo thứ tự của chúng trong bảng chữ cái (tiếng Việt là 1 điển hình). Chính vì vậy bảng mã tiếng Việt trong Unicode có các ký tự Việt nằm rải rác ở nhiều nơi và không theo 1 trình tự sắp xếp nào. - Mỗi ký tự trong bảng mã Unicode đều có độ dài cố định là 16 bits, nhờ đó việc xử lý các xâu ký tự Unicode rất đơn giản không phức tạp như các giải pháp dùng chuỗi ký tự điều khiển, phải có những thuật toán tương đối phức tạp để nhận diện ký tự trong 1 chuỗi các Byte. Trong khi đó với Unicode mỗi ký tự có độ dài đúng 2 bytes nên có thể định vị rất dễ dàng các vị trí của ký tự trong chuỗi Byte cho trước. -Unicode t