intTypePromotion=3

Tóm tắt luận văn Thạc sĩ: Nghiên cứu một số thuật toán phân tích không gian trong hệ thông tin Địa lý

Chia sẻ: Nguyễn Thị Thu Trang | Ngày: | Loại File: PDF | Số trang:25

0
185
lượt xem
44
download

Tóm tắt luận văn Thạc sĩ: Nghiên cứu một số thuật toán phân tích không gian trong hệ thông tin Địa lý

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài luận văn thạc sĩ nghiên cứu một số thuật toán phân tích không gian trong hệ thông tin địa lý, nhằm khắc phục những hạn chế và đáp ứng các yêu cầu trên. Mời các bạn tham khảo!

Chủ đề:
Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ: Nghiên cứu một số thuật toán phân tích không gian trong hệ thông tin Địa lý

  1. HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- BÙI THANH HUYỀN NGHIÊN CỨU MỘT SỐ THUẬT TOÁN PHÂN TÍCH KHÔNG GIAN TRONG HỆ THÔNG TIN ĐỊA LÝ CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60.48.01 Người hướng dẫn khoa học: PGS. TS. Đặng Văn Đức TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2012
  2. -1- MỞ ĐẦU Hệ thống thông tin địa lý GIS (Geographical Information System) đã được khá nhiều người quan tâm muốn tìm hiểu và ngày càng nhiều tổ chức kinh tế xã hội ứng dụng trong công tác nghiên cứu khoa học và sản xuất. Công nghệ GIS đã và đang thâm nhập như một nhu cầu tất yếu vào hầu hết các ngành. Thông tin GIS cung cấp cho người sử dụng hướng thay đổi của dữ liệu trong một lãnh thổ theo thời gian, đồng thời xác định những gì có thể xẩy ra khi có sự thay đổi dữ liệu đó. Nói cách khác GIS cung cấp cho người sử dụng những mô hình khác nhau của sự thay đổi. Dữ liệu bản đồ là thành phần chính trong cơ sở dữ liệu của GIS. Các bản đồ gắn chặt với thế giới thực và luôn được bổ sung những thông tin mới. Nền tảng của thông tin hình học trong GIS là bản đồ đã được số hóa ở dạng nào đó để thực hiện từ những phép tính đơn giản như: đo đạc diện tích, chu vi, chiều dài, vị trí … đến những phép tính phức tạp như: mở rộng diện tích, xác định giao của nhiều vùng diện tích … là những bài toán khá phổ biến trong quản lý và nghiên cứu khoa học. Không giống như các CSDL thông thường, GIS rất trực quan, thuận tiện và cùng một lúc cung cấp cho người sử dụng nhiều thông tin một cách tổng hợp. Nhận thấy những tiện ích của GIS, em lựa chọn và thực hiện đề tài “Nghiên cứu một số thuật toán phân tích không gian trong hệ thông tin địa lý” nhằm khắc phục những hạn chế và đáp ứng các yêu cầu trên. Dữ liệu không gian, các phép toán phân tích không gian và ứng dụng của chúng.
  3. -2- CHƯƠNG 1 – KHÁI QUÁT VỀ HỆ THỐNG THÔNG TIN ĐỊA LÝ GIS 1.1. Định nghĩa GIS Hệ thông tin địa lý (GIS - Geographical Information System), là một hệ thống thông tin có khả năng thu thập, cập nhập, quản trị và phân tích, biểu đồ dữ liệu địa lý phục vụ giải quyết các bài toán ứng dụng có liên quan tới vị trí địa lý trên bề mặt trái đất hoặc được định nghĩa như làm một hệ thông tin với khả năng truy nhập, tìm kiếm, xử lý, phân tích và truy xuất dữ liệu địa lý nhằm hỗ trợ cho công tác quản lý, quy hoạch và quản lý tài nguyên thiên nhiên, môi trường và y tế. Mục tiêu của GIS là cung cấp cấu trúc một cách hệ thống để quản lý các thông tin địa lý khác nhau và phức tạp, đồng thời cung cấp các công cụ, các thao tác hiển thị, truy vấn, mô phỏng… Cái GIS cung cấp là cách thức suy nghĩ mới về không gian. Phân tích không gian chỉ là truy cập mà còn cho phép khai thác các quan hệ và tiến trình biến đổi của chúng. Công nghệ GIS tích hợp giữa các thao tác trên cơ sở dữ liệu như: đưa ra các câu hỏi truy vấn (query), phân tích thống kê (statistcal analysis) với việc thể hiện và các phép phân tích địa lý. Những khả năng đó của hệ thống GIS đã phân biệt GIS với các hệ thống thông tin khác và tạo cho nó một giá trị đến khu vực công cộng và các nhân để giải thích các sự kiện, và lên kế hoạch chiến lược. 1.2. Các thành phần của GIS Hệ thống GIS có 5 thành phần cơ bản bao gồm con người, phương pháp, phần cứng tin học, phần mềm tin học và dữ liệu. Tầm quan trong mỗi thành phần và các mối quan hệ giữa chúng: 1.2.1. Con người (People) Công nghệ GIS sẽ bị hạn chế nếu không có con người tham gia
  4. -3- quản lý hệ thống và phát triển những ứng dụng GIS trong thực tế. Người sử dụng GIS có thể là những chuyên gia kỹ thuật, người thiết kế và duy trì hệ thống, hoặc những người dùng GIS để giải quyết các vấn đề công việc. 1.2.2. Dữ liệu (Data) Dữ liệu được sử dụng trong GIS không chỉ là số liệu địa lý mà còn phải được thiết kế trong một cơ sở dữ liệu. Những thông tin là sẽ bao gồm các dữ kiện về vị trí địa lý, thuộc tính của thông tin, mối liên hệ không gian của các thông tin, và thời gian. 1.2.3. Phần cứng (Hardware) Phần cứng là hệ thống các máy tính điện tử trên đó hệ GIS hoạt động. Ngày nay, phần mềm GIS chạy trên rất nhiều dạng phần cứng, từ máy chủ trung tâm đến các máy trạm hoạt động độc lập hoặc liên kết mạng. 1.2.4. Phần mềm (Software) Là tập hợp các câu lệnh, chỉ thị nhằm điều khiển phần cứng của máy tính thực hiện một nhiệm vụ xác định, phần mềm hệ thống thông tin địa lý có thể là một hoặc tổ hợp các phần mềm máy tính. Phần mềm GIS cung cấp các chức năng và các công cụ cần thiết để lưu trữ, phân tích và hiển thị thông tin địa lý. 1.2.5. Phương pháp (Methods) Đây là hợp nhất rất quan trọng để đảm bảo khả năng hoạt động của hệ thống, là yếu tố quyết định sự thành công của việc phát triển công nghệ GIS. Hệ thống GIS cần được điều hành bởi một số bộ phận quản lý, bộ phận này phải được bổ nhiệm để tổ chức hoạt động hệ thống GIS một cách có hiệu quả để phục vụ người sử dụng thông tin. 1.3. Cấu trúc dữ liệu trong GIS 1.3.1. Dữ liệu không gian Dữ liệu không gian là dữ liệu về đối tượng mà vị trí của nó được xác định trên bề mặt Trái đất. Dữ liệu không gian sử dụng
  5. -4- trong hệ thống địa lý luôn được xây dựng trên một hệ thống tọa độ. Mô hình dữ liệu quyết định cách thức mà dữ liệu được cấu trúc, lưu trữ, xử lý và phân tích trong một hệ thông tin địa lý. Mô hình dữ liệu raster sử dụng lưới để thể hiện đặc trưng không gian. Mô hình dữ liệu Vector sử dụng các điểm và tọa độ của chúng để xây dựng các đặc trưng không gian như điểm, đường và vùng. Các đặc trưng dựa trên mô hình dữ liệu véctơ được coi như các đối tượng riêng biệt trong không gian. Nhiều hệ thông tin địa lý sử dụng cả hai mô hình dữ liệu vector và raster Mô hình dữ liệu dạng raster phản ánh toàn bộ vùng nghiên cứu dưới dạng một lưới các ô vuông hay điểm ảnh (pixel). Mô hình raster có các đặc điểm: Các điểm được xếp liên tiếp từ trái qua phải và từ trên xuống dưới. Mỗi một điểm ảnh (pixel) chứa một giá trị. Một tập các ma trận điểm và các giá trị tương ứng tạo thành một lớp (layer). Trong cơ sở dữ liệu có thể có nhiều lớp. Mô hình dữ liệu raster là mô hình dữ liệu GIS được dùng tương đối phổ biến trong các bài toán về môi trường, quản lý tài nguyên thiên nhiên. Mô hình raster chủ yếu dùng để phản ánh các đối tượng dạng vùng là ứng dụng cho các bài toán tiến hành trên các loại đối tượng dạng vùng: phân loại, chồng xếp. Các nguồn dữ liệu raster có thể bao gồm: Quét ảnh Ảnh máy bay, ảnh viễn thám Chuyển từ dữ liệu Vector sang Lưu trữ dữ liệu dạng raster. Nén theo hàng (Run lengh coding). Nén theo ngữ cảnh (Fractal). Nén theo chia nhỏ thành từng phần (Quadtree).
  6. -5- .Mô hình dữ liệu Vector xem các sự vật, hiện tượng là tập các thực thể không gian cơ sở và tổ hợp của chúng. Trong mô hình 2D thì các thực thể cơ sở bao gồm: điểm (point), đường (line), vùng (polygon). Các thực thể sơ đẳng được hình thành trên cơ sở vector hay tọa độ của các điểm trong một hệ trục tọa độ nào đó. Loại thực thể cơ sở được sử dụng phụ thuộc vào tỷ lệ quan sát hay mức độ khái quát. Với bản đồ có tỷ lệ nhỏ thì thành phố được biểu diễn bằng điểm (point), đường đi, sông ngòi được biểu diễn bằng đường (line). Khi tỷ lệ thay đổi kéo theo sự thay đổi về thực thể biểu diễn. Thành phố lúc này sẽ được biểu diễn bởi vùng có đường ranh giới. Khi tỷ lệ lớn hơn, thành phố có thể được biểu diễn bởi tập các thực thể tạo nên các đối tượng nhà cửa, đường sá, các trình tiện ích,… 1.3.2. Dữ liệu phi không gian Là những mô tả về đặc tính, đặc điểm và các hiện tượng xẩy ra tại vị trí địa lý xác định mà chúng khó hoặc không thể biểu thị trên bản đồ được. Hệ thống thông tin địa lý sử dụng phương pháp chung để kết hai loại dữ liệu đó thông qua bộ xác định, lưu trữ đồng thời trong các thành phần đô thị và phi đô thị. Các bộ xác định có thể đơn giản là một số duy nhất liên tục, ngẫu nhiên hoặc là các chỉ báo địa lý hay dữ liệu vị trí lưu trữ. Bộ xác định cho một thực thể có thể chứa tọa độ phân bố của nó, số hiệu mảnh bản đồ, mô tả khu vực hoặc là một con trỏ đến vị trí lưu trữ của dữ liệu liên quan. 1.4. Chức năng của hệ GIS Sức mạnh của các chức năng của hệ thống GIS khác nhau là khác nhau. Kỹ thuật xây dựng các chức năng cũng rất khác nhau. Chức năng của một hệ thống thông tin địa lý được phân chia thành năm loại như sau: Thu thập dữ liệu, thao tác dữ liệu, quản lý dữ liệu, hỏi đáp và phân tích, và hiển thị.
  7. -6- Nhập dữ liệu là quá trình mã hóa dữ liệu thành dạng có thể dùng trên máy tính và ghi dữ/ liệu vào cơ sở dữ liệu GIS. Nhập dữ liệu là một công việc đòi hỏi thời gian và công sức và kinh phí (giá thành xây dựng CSDL ban đầu thường là 5 -10 lần giá thành phần cứng và phần mềm). Có những trường hợp các dạng dữ liệu luôn đòi hỏi được chuyển dạng và thao tác theo một số cách để có thể tương thích với một hệ thống nhất định. Công nghệ GIS cung cấp nhiều công cụ cho các thao tác trên dữ liệu không gian và cho loại bỏ dữ liệu không cần thiết.
  8. -7- CHƯƠNG 2 – NGHIÊN CỨU MỘT SỐ THUẬT TOÁN PHÂN TÍCH DỮ LIỆU KHÔNG GIAN 2.1. Các thuật toán xếp chồng bản đồ Xếp chồng bản đồ là phần cốt lõi của hoạt động phân tích GIS. Nó kết hợp một số tính năng không gian để tạo ra yếu tố mới không gian. Mặt khác, xếp chồng bản đồ có thể được định nghĩa là một hoạt động không gian, kết hợp các lớp địa lý khác nhau để tạo ra lớp thông tin. Xếp chồng bản đồ được thực hiện bằng cách sử dụng số học, logic, các toán tử quan hệ và được thực hiện trong cả hai loại dữ liệu Vector và Raster. Quá trình thực hiện Overlay bản đồ qua 2 bước: Xác định tọa độ các giao điểm và tiến hành chồng khít 2 lớp bản đồ tại giao điểm này. Kết hợp dữ liệu không gian và thuộc tính của hai lớp bản đồ. 2.1.1. Các phương pháp trong xếp chồng bản đồ Phương pháp vector Overlay Trong Vector Overlay, các tính năng và thuộc tính của bản đồ được tich hợp để cho ra một bản đồ mới.Vector Overlay có thể được thực hiện trên các kiểu chức năng của bản đồ như: Điểm và đường (Point in Line), đoạn và đa giác (Line in Polygon), đa giac và đa giác (Polygon in Polygon). Phương pháp Raster Overlay Phương pháp Raster Overlay sử dụng số học và các toán tử Boolean để kết hợp các điểm ảnh hoặc giá trị tế bào trong mỗi bản đồ tạo ra một giá trị mới trong bản đồ kết hợp 2.1.2. Phép toán trong Overlay Các phép toán trong overlay bao phủ: Phép hợp (Union), phép giao (Insertect) và phép đồng nhất (Indentity). Phép hợp (Union): phép hợp hoạt động như toán tử Or. Đầu vào là hai lớp bản đồ là kiểu đa giác (polygon), đầu ra là một lớp bản đồ mới bằng cách xếp chồng hai miền dữ liệu đầu vào
  9. -8- và dữ liệu thuộc tính của chúng. Điều kiện: miền dữ liệu phải là polygon. Phép giao (Intersect): Phép giao hoạt động như toán tử And. Tạo ra một vùng bao mới bằng cách xếp chồng hai tập dữ liệu đầu. Kết quả đầu ra bao gồm phần dữ liệu thuộc vào cả hai tập dữ liệu đầu vào. Phép đồng nhất (Indentity): Tạo ra một vùng bao phủ mới bằng cách xếp chồng hai tập dữ liệu đầu vào. Kết quả đầu ra bao gồm toàn bộ phần dữ liệu của lớp đầu tiên và chỉ những phần nào của lớp thứ hai được chồng khít. 2.1.3. Thuật toán Bentley – Ottmann Trong hình học tính toán thuật toán Bentley – Ottmann (BO) là một thuật toán quét dòng để liệt kê tất cả các đoạn thẳng giao nhau trong mặt phẳng. Tương tự như các thuật toán khác để kiểm tra có hay không các đoạn thẳng giao nhau, với đầu vào là n đoạn thẳng và k điểm cắt nhau BO có độ phức tạp là O(n+k)logn. 2.1.4. Thuật toán giao của hai đa giác Đã có nhiều thuật toán tìm giao của hai đa giác được công bố [RIG] [JOS]. Phần lớn các thuật toán này xuất phát từ tìm giao của hai đa giác lồi. Do vậy, nếu vùng nghiên cứu đa giác bất kỳ thì chúng phải được tách ra thành đa giác lồi trước khi thực hiện thuật toán. Phát biểu bài toán: Hãy tìm phần giao của hai đa giác phẳng không tự cắt A và B. Cho biết A = a1a2…an và B = b1b2 … bm. Chi tiết thuật toán Phần giao của A và B có thể là tập rỗng hay là tập các đa giác không giao nhau. Để đơn giản ta gọi phần giao của A bà B là tập đa giác giao, và gọi một cạnh là cạnh của tập đa giác giao với ý nghĩa nó là cạch của một đa giác trong tập đa giác giao. Với P là một đa giác thì ta gọi I(P) và O(P) lần lượt là miền trong và miền ngoài của P. Tư tưởng của thuật toán là tìm tất cả các cạnh của tập đa giác
  10. -9- giao, nếu tập cạnh này khác rỗng thì bằng cách ghép chúng lại sẽ được tập các đa giác là giao của A và B. Thuật toán bao gồm hai bước chính như sau: Bước 1: Trường hợp hai đa giác không có cặp cạnh nào song song và giao nhau Với mỗi cạnh v = aiai+1  A (i-1, 2,…, n), ta tìm mọi giao điểm của v với tất cả các cạnh u = bkbk+1  B (k =1, 2,…, m), trong đó an+1 và bm+1 tương ứng được gán là a1 và b1. Đặt Xx = { x| x là giao điểm của cạnh v với các cạnh u  b}  {aiai+1} (nếu trong Xx có nhiều điểm trùng nhau thì chỉ giữ lại một điểm trong số các điểm trùng nhau đó). Sắp xếp các điểm trong Xx theo chiều tằng dần về khoảng cách từ mỗi điểm đến ai, ta được Xx = {x1 = ai, x2,…,xlv = ai+1}, với |Xx|= lv. Khi đó, cạnh xixi+1 (i = 1, 2,..lv-1) là một cạnh của tập đa giác giao nếu trung điểm của nó thuộc I(B). Xử lý tương tự cho các cạnh của đa giác B. Bước 2: Trường hợp hai đa giác có cặp cạnh song song và giao nhau Trước hết, ta chèn thêm những điểm mới vào các đa giác để nếu có trường hợp tồn tại cặp cạnh song song và giao nhau thì tạo ra cặp cạnh trùng nhau. Giả sử cạnh aiai+1 và cạnh bkbk+1 song song và giao nhau (nhưng không trùng nhau). Ta xử ly như sau: Nếu ai bkbk+1 (ai nằm trong đoạn bkbk+1), thì chèn ai vào giữa bk và bk+1, tức là coi bkai và aibk+1 là hai cạnh mới của đa giác B. Xử lý tương tự cho ba đỉnh: ai+1, bk, bk+1. Sau đó, xét mỗi cặp cạnh trùng nhau v=aiai+1  A và u = bkbk+1  B (giả sử ai = bk và ai+1 = bk+1), thực hiện thao tác tìm giao điểm và sắp xếp như bước 1 ở trên với hai cạnh ai+1ai+2 và bk+1bk+2 ta được hai tập hợp: Xv = { x1 = ai+1, x2,…,xlv-1, xlv = ai+2}, Yu = { y1 = bk+1, y2,…, ylu-1, ylu = bk+2}.
  11. - 10 - Để kiểm tra xem cạng aiai+1 (hoặc bkbk+1) có là một cạnh của tập đa giác giao hay không, ta dựa vào tính chất sau: Gọi n và m lần lượt là trung điểm các cạnh x1x2 và y1y2. Khi đó, cạnh aiai+1 (hoặc bkbk+1) là một cạnh của tập đa giác giao nếu một trong hai điều kiện sau thỏa mãn: N I(B) và MO(A). NO(B) và MI(A). Chứng minh tính chất: Để chứng minh tính chất trên ta sử dụng hai kết quả sau: 1. Nếu đi theo chiều thuận (chiều ngược với chiều kim đồng hồ) theo các cạnh của đa giác p thì I(P) và O(P) tương ứng nằm về phía bên trái và phía bên phải dọc theo hướng đi. 2. Nếu biết trước một điểm MI(P) (O(P)), thì I(P) (O(P)) sẽ nằm cùng phía so với M và O(P) (I(P)) sẽ nằm khác phía so với M, theo một hướng đi trên một cạnh nào đó thuộc đa giác P. Xét về vị trí tương đối của M với đa giác A và của N với đa giác B ta thấy chỉ có bốn trường hợp sau: 1. NI(B) và MO(A). 2. NO(B) và MI(A). 3. NI(B) và MI(A). 4. NO(B) và MO(A). Xét trường hợp 1: Vì N I(B) chiều thuận của đa giác B là chiều đi từ bk đến bk+1 (1) Vì MO(A) Chiều thuận của đa giác A là chiều đi từ ai đến ai+1 (2). Từ (1), (2) và giả thiết aiai+1 bkbk+1 =>  một đa giác là giao của A và B nhận aiai+1 là cạnh với chiều thuận là chiều từ ai tới ai+1. Chứng minh tương tự cho trường hợp 2, ta thua được kết quả:  một đa giác là giao của A và b nhận aiai+1 là cạnh với chiều thuận là chiều từ ai+1 tới ai. Tóm lại, trong cả hai trường hợp thì aiai+1 là một cạnh của tập đa
  12. - 11 - giác giao. Bằng cách chứng minh tương tự cho hai trường hợp còn lại ( trường hợp 3 và 4) ta đều thu được kết quả: aiai+1 không phải là cạnh của tập đa giác giao. Các thuật toán liên quan. Thuật toán trình bày trên có sử dụng hai thuật toán khác nhau để cài đặt, đó là kiểm tra điểm trong đa giác và tìm giao của hai đoạn thẳng. Để kiểm tra một điểm có nằm trong đa giác hay không ta có thể sử dụng thuật toán sau: Đầu vào: Cho trước đa giác P và điểm p. Đầu ra: p nằm trong hay ngoài P. Begin if (p nằm trong cạnh P), p trong P else đếm =0 l = tia song song trục X vẽ từ p for (i=1 to n) begin if (nếu cạnh (i) cắt l) and not cạng (i) không trùng với l) then begin if (một đầu cuối của cạnh (i) nằm phía trên tia l) đếm= đếm +1 end end for if (đếm là lẻ ), p nằm trong P endif end Để tìm giao của hai đoạn thẳng ta sử dụng thuật toán biểu diễn đoạn thẳng bằng phương pháp tham số như sau: Phương trình đoạn thẳng là cạnh đa giác được xác định từ hai tọa độ đỉnh liên tiếp. Giả sử ta có tham số t thay đổi từ 0 đến 1 cho phần đoạn thẳng AB giữa hai đỉnh đa giác và có giá trị 0 tại một đầu,
  13. - 12 - giá trị 1 tại đầu kia. Vậy vố 0  t 1, ta có: x = xA + t(xB – xA) y = yA +t(yB – yA) Tương tự, cạnh CD của đa giác thứ hai sẽ được biểu diễn bởi tham số s(và phươngy C  y D )  ( xC  x A )( y C  y A ) xC  x A )( trình sau: t x– x + s(x – x ) ( x BC x A )( yC  y D )  ( xC  x D )( y B  y A ) D C y– yC + s(yD – yC) (2) ( x B  x A )( y C  y A )  ( xC  x A )( y B  y A ) s (3) ( x B  x A )( yC  y D )  ( xC  x D )( y B  y A ) Từ các công thức sau đây ta tính đượ giá trị của t và s. Trong đó, nếu 0 t  1 và 0 s  1 khi hai đoạn thẳng cất nhau tại một điểm và giao điểm này được tính từ (1) và (2). Phân tích và cài đặt thuật toán Trình bày tóm tắt các bước chính cài đặt chức năng xếp chồng các bản đồ trong hệ thống GIS vector. Giả sử ta phải thực hiện tính toán bao phủ của vùng địa lý được biểu diễn bởi đa giác P trong chủ đề T1 với các vùng của chủ đề T2. Bước 1. Xác định xem đa giác P của chủ đề T1 giao với các đa giác nào của chủ đề T2. Một bản đồ chủ đề chứa vô số đa giác (bản đồ hành chính Việt nam), đa giác biểu diễn xã lại có vô số cạnh. Để tăng tốc độ xử lý của máy tính ta sẽ không so sánh đa giác P của T1 với mọi đa giác của T2. Cấu trúc cơ sở dữ liệu địa lý thường lưu trữ chữ nhật bao của các đa giác. Trước khi kiểm tra hai đa giác có giao nhau hay không thì cần kiểm tra chữ nhật bao của chúng có giao nhau hay không vì hai đa giác giao nhau chỉ khi hai chữ nhật bao của chúng giao nhau. Giải pháp này làm giảm đáng kể số lần tính toán. Việc xác định chính xác hai đa giác P, Q có giao nhau hay không được thực hiện theo thuật toán sau: Đầu vào: Đa giác P, Q Đầu ra: P và Q có giao nhau? begin if (không có cạnh nào của p cắt cạnh nào đó của Q) do
  14. - 13 - begin p = điểm bất kỳ nào trên biên của P if (p nằm trong Q) P Q else begin q = điểm bất kỳ trên biên của Q if (q nằm trong Q) Q P else P và Q không giao nhau end if end if else P giao với Q end Độ phức tạp của thuật toán tìm giao các cạnh hai đa giac sẽ là O(nlogn). Bước 2. Phân lớp các đỉnh đa giác p và Q. Mỗi đỉnh đa giác được gán bởi giá trị I (trong), O (ngoài) hay B (biên) so với đa giác kia. Các giá trị này được thực hiện nhờ thuật toán điểm trong đa giác trình bày trên. Các giá trị của đỉnh được lưu vào danh sách PV cho đa giác P và QV cho đa giác Q như sau: PV = QV = Trong đó, n là tổng số đỉnh của đa giác P, m là tổng số đỉnh của đa giác Q. Bước 3. Tìm giao điểm của các cạnh đa giác P và Q. Giao của các cạnh đa giác được tính theo công thức (3) ở trên. Phải xét lần lượt các cạnh của P có cắt các cạnh của Q hau không. Nếu cí điểm cắt thì xen chúng vào danh sách PV và QV với giá trị B (biên). Kết quả cho lại các cạnh của đa giác được chia thành đoạn nhỏ. Mỗi đoạn của đa giác này sẽ nằm toàn bộ trong hay toàn bộ ngoài đa giác kia. Ta có thể sử dụng tính chất mô tả ở phần trên để xác định
  15. - 14 - các đoạn thẳng nằm trong hay ngoài đa giác: nếu điểm giữa đoạn thẳng nằm trong hay nằm ngoài đa giác thì đoạn thẳng đó sẽ nằm trong hay nằm ngoài đa giác. Bước 4. Lập các đa giác kết quả. Từ danh sách PV và QV ta lọc ra các đoạn thẳng có giá trị I hay B để lập các đa giác mới. Quan sát các bước của thuật toán trên thì bước có độ phức tạp lớn nhất. Nó đòi hỏi tìm giao điểm của mọi cạnh hai đa giác cho nên có độ phức tạp O(n2), việc xem giá trị giao điểm vào danh sách sẽ có độ phức tạp O(k3), trong đó k là số phần tử trong danh sách. Trường hợp xấu nhất sẽ là k = n3. Do vậy, độ phức tạp của bước này sẽ là O(n2). Thuật toán tìm giao của hai đa giác là nền tảng của việc xây dựng chức năng xếp chồng của hệ thống GIS vector. 2.2. Thuật toán vùng đệm không gian 2.2.1. Khái niệm Định nghĩa vùng đệm (buffering): Vùng đệm các đối tượng bản đồ là vùng được tạo với chiều rộng cụ thể xung quanh một điểm, một đường, một vùng. Các quan hệ này thông thường nói lên vị trí tương đối của đối tượng này với đối tượng kia. Phương pháp Buffer được chia làm nhiều loại (phép toán) khác nhau, nhưng cách thức xử lý thì luôn tuân theo các bước cơ bản sau đây: Chọn ra một hay nhiều đối tượng trên bản đồ, gọi là các đối tượng gốc. Áp dụng một quan hệ không gian để tìm ra các đối tượng khác mà có quan hệ đặc biệt với các đối tượng gốc. Hiển thị tập đối tượng tìm thấy cả trên dữ liệu không gian và thuộc tính. Kết quả của buffer là một vùng mới, vùng mới này có thể được sử dụng trong những truy vấn để xác định thực thể xảy ra hoặc bên trong hoặc bên ngoài vùng đệm được định nghĩa.
  16. - 15 - 2.2.2. Phân loại Có 2 loại vùng đệm đối tượng bản đồ phụ thuộc vào độ rộng của vùng đệm Độ rộng vùng đệm là hằng số. Độ rộng vùng đệm là biến số. Cả hai vùng đệm có thể được tạo ra một tập đối tượng bao phủ dựa trên giá trị thuộc tính của mỗi đối tượng. 2.2.3. Một số phép toán buffer thông dụng Tìm kiếm đối tượng nằm bên trong đối tượng khác: Phép toán này xác định quan hệ “bao kín” giữa các đối tượng không gian. Đường thẳng bao gồm nhiều điểm, một đa giác (polygon) có thể bao gồm nhiều đường thẳng hoặc các đa giác con khác. Tìm kiếm các đối tượng cắt các đối tượng khác: Phép toán này xác định các đối tượng có giao điểm hay nằm chồng nên các đối tượng khác. Hai đa giác giao nhau nếu chúng có một miền chung. Hai đường thẳng cắt nhau nếu chúng có một điểm chung. Một đường thẳng giao nhau với một đa giác khi nó nằm một phần hay toàn bộ trong đa giác. Tìm kiếm các đối tượng liền kề với đối tượng khác: Đây là kiểu tìm kiếm trong đó các đối tượng có chung đường bao (biên). Quan hệ này chỉ áp dụng cho đường thẳng hoặc đa giác. Tìm các đối tượng liền kề các đối tượng khác. Đây là kiểu tìm kiếm trong đó các đối tượng có chung đường bao (biên). Quan hệ này chỉ áp dụng cho đường thẳng hoặc đa giác. Tìm các đối tượng nằm bên trong hay bên ngoài một khung cách xác định: Kiểu tìm kiếm này được sử dụng trong việc xác định đối tượng xung quanh một hay nhiều các điểm mốc. Quá trình thực hiện bao gồm việc tạo ra một vùng đệm các điểm mốc này và sau đó xác định các đối tượng căn cứ vào vị trí của chúng so với vùng đệm tạo ra. 2.2.4. Xử lý trong buffer
  17. - 16 - Buffer hay còn gọi là truy vấn không gian trên cơ sở các quan hệ không gian giữa các đối tượng. Các quan hệ này thông thường nói lên vị trí tương đối của đối tượng này với đối tượng kia. Phương pháp buffer được chia làm nhiều loại khác nhau, nhưng cách xử lý thì luôn tuân theo các bước cơ bản sau: Chọn một hay nhiều đối tượng trên bản đồ, gọi là các đối tượng gốc. Hiển thị tập các đối tượng tìm thấy cả trên dữ liệu không gian và thuộc tính. Áp dụng một quan hệ không gian để tìm ra các đối tượng khác mà có quan hệ đặc biệt với các đối tượng gốc. 2.2.5. Thuật toán hỗ trợ xây dựng thao tác Buffering Trong GIS ta có thể phân loại thao tác buffering thành 3 loại bao gồm: Thao tác buffering cho điểm, buffering cho đường và buffering cho vùng. Thao tác buffering cho điểm tạo ra một vùng tròn xung quanh một điểm. Bán kính vùng tròn được gọi là khoảng cách vùng đệm Thao tác buffering cho đường phức tạp hơn cho điểm, khi một đường được tạo từ nhiều đoạn. Thuật toán về thao tác buffering cho đa giác phần lớn là giống với thuật toán về thao tác buffering cho đường. Chỉ có sự khác biệt duy nhất là vùng đệm đa giác chỉ được tạo ra một phía của đường được xác định trong đa giác. 2.2.6. Thuật toán xác định đường cách đều Một trong các thao tác phân tích dữ liệu không gian cơ bản và rất quan trọng trong Hệ thống thông tin địa lý là xác định đường ranh giới phân cách giữa các vùng theo một vài tiêu chuẩn nhất định. Trong các tiêu chuẩn xác định đường ranh giới thì đường ranh giới cách đều là tiêu chuẩn rất quan trọng và phổ biến, bài toán phân chia hải giới là một ví dụ thực tiễn. Trước đây, các đường hải giới cách đều vẫn được xây dựng một cách thủ công rất tốn kém thời gian và
  18. - 17 - công sức mà kết quả đem lại cũng không đảm bảo chính xác. Ngày nay với sự phát triển của các Hệ thống thông tin địa lý đã giúp con người giảm bớt được rất nhiều chi phí trong quản lý và phân tích dữ liệu địa lý. Thuật toán dựa trên cơ sở toán học chặt chẽ, có độ chính xác cao và đã được cài đặt thành một chương trình máy tính với mô hình dữ liệu vector. Bài toán phân chia hải giới theo phương pháp đường cách đều Phân tích bài toán: Theo thông lệ quốc tế khu vực kinh tế độc quyền (Exclusivi Economic Zone – EEZ) kéo dài từ bờ biển của một quốc gia và lãnh thổ trong đất liền đến 200 dặm ngoài biển (hoặc 200 dặm đối với đất liền và 12 dặm đối với các đảo – Mỗi dặm tương đương 1,6Km). Như vậy, để qui trình tự động hóa xác định đường cách đều được tổ chức một cách chặt chẽ và đúng với thực tiễn, ta chỉ xét đường ranh giới cách đều đối với những quốc gia đối diện nhau mà có khoảng cách nhỏ nhất giữa hai đường biển không được lớn quá 400 dặm. Ngoài ra qui trình xác định hoàn toàn dựa trên căn cứ toán học, hình học, không xét đến các yếu tố ngoại lệ, các đảo được xét đến với mức ưu tiên tương tự như đường biên thuộc phần đất liền. Trên thực tế có 3 dạng cấu hình bờ biển giữa hai quốc gia là: dạng kết thúc mở, dạng đóng và dạng nửa đóng. Ta có thể hiểu các thuật ngữ này một cách đơn giản như sau: - Dạng kết thúc mở là dạng cấu hình của vùng biển mà bao gồm hai đường bờ biển đối diện nhau và không có điểm chung. - Dạng đóng là trường hợp một vùng nước biển được giới hạn bởi hai quốc gia gần kề và đối diện nhau tạo thành hồ khép kín. - Dạng nửa đóng là dạng vùng biển mà tạo bởi hai quốc gia kề sát nhau. Ta có điểm khởi đầu để xác định đường cách đều chính là điểm mà biên giới trên đất liền gặp bờ biển còn điểm kết thúc chưa xác định. Đối với mỗi trường hợp kết thúc đóng, mở và nửa đóng thì có điều kiện khởi đầu và két thúc qui trình xác định đường cách đều
  19. - 18 - khác nhau. 2.3. Một số thuật toán tìm đường đi tối ưu ứng dụng trong GIS 2.3.1. Phát biểu bài toán Các thuật toán đồ thị nổi tiếng xác định đường đi “ngắn nhất ” giữa hai điểm A và B trên mạng lưới đường phố mà tiêu chuẩn “ngắn nhất” có thể được dựa trên khoảng cách, thời gian đi hoặc một số ràng buộc khác do người sử dụng tự đặt ra. Giả sử cho đồ thị G trong đó có khung (x, y) gắn với trọng số của khung a(x, y). Trong một số ứng dụng, chiều dài có thể là chi phí hoặc giá trị khác nào đó. Chiều dài của đường đi được xác định bằng tổng chiều dài của các cung đơn trong đường đi. Với hai đỉnh bất kỳ, s và t trong G, có thể tồn tại nhiều đường đi từ s đến t. Bài toán đường đi ngắn nhất bao gồm tìm đường đi từ s đến t sao cho chiều dài nhỏ nhất có thể. Bài toán này có thể chia làm hai loại như sau:  Tìm đường đi ngắn nhất từ một đỉnh nguồn đến các đỉnh còn lại của đồ thị.  Tìm đường đi ngắn nhất giữa một cặp đỉnh của đồ thị. Với hai loại bài toán này ta có thể phát biểu chung bài toán như sau: Đầu vào: Cho một đồ thị có hướng có trọng số G = (V, E) với V : tập đỉnh, E: tập cạnh), một hàm trọng số w:E [ 0, ∞). Đầu ra: Hãy tìm đường đi ngắn nhất giữa hai đỉnh (chẳng hạn (s, t)) trong đồ thị G. 2.3.2. Thuật toán Dijkstra Thuật toán này do nhà khoa học Hà Lan – ông Edsger Dijkstra đưa ra vào năm 1959 cung cấp nền tảng cơ bản cho thuật toán hữu hiệu nhất để giải quyết bài toán này. Thuật toán Dijkstra được thiết kế dựa trên kỹ thuật tham ăn để giải quyết bài toán tìm đường đi ngắn nhất từ một đỉnh nguồn trong đồ thị có hướng với trọng số
  20. - 19 - không âm. Thuật tián Dijkstra hoạt động dựa trên việc gán nhãn cho các đỉnh. Phát biểu bài toán Đầu vào: Cho một đồ thị có hướng G = (V, E) (với V: tập đỉnh, E: tập cạnh), một hàm trọng số w: E [0,∞) và một đỉnh nguồn s Đầu ra: Hãy tìm đường đi ngắn nhất từ tập nguồn s đến mỗi đỉnh trong đồ thị. 2.3.3. Thuật toán Bellman-Ford Ban đầu, giả sử rằng tất cả chiều dài của các cung là không âm. Nếu một số chiều dài cung là âm thì điều gì sẽ xảy ra? Ví dụ, xét đồ thị trong hình 2.2. Đường đi ngắn nhất từ đỉnh s đến đỉnh t là (s, 1), (1, t), chiều dài của nó là +2 – 2 = 0. Có thể dễ dàng nhận thấy rằng nếu thuật toán tìm đường đi ngắn nhất Dijkstra được áp dụng trong đồ thị này thì đường đi (s, t) được chọn nhầm là đường đi ngắn nhất từ đỉnh s đến đỉnh t. Vì vậy, không đảm bảo rằng thuật toán tìm đường đi ngắn nhất Dijkstra sẽ sinh ra đường đi ngắn nhất khi chiều dài cung được cho phép là âm. 2.3.4. Thuật toán A* Thuật toán A* được mô tả lần đầu vào năm 1968 bởi Peter Hart, Nils Nilsson, và Bertram Raphael. Trong bài báo của họ, thuật toán được gọi là thuật toán A; khi sử dụng thuật toán này với một đánh giá heuristic thích hợp sẽ thu được hoạt động tối ưu, do đó mà có tên A*. Thuật toán A* (đọc là A sao) là một thuật toán tìm kiếm trong đồ thị. Thuật toán này tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước (hoặc tới một nút thỏa mãn một điều kiện đích). Thuật toán này sử dụng một "đánh giá heuristic" để xếp loại từng nút theo ước lượng về tuyến đường tốt nhất đi qua nút đó. Thuật toán này duyệt các nút theo thứ tự của đánh giá heuristic này. Do đó, thuật toán A* là một ví dụ của tìm kiếm theo lựa chọn tốt nhất (best-first search).

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản