Một cách tiếp cận mới trong việc giải quyết bài toán chồng phủ vùng sử dụng cấu trúc dữ liệu danh sách cạnh liên kết kép

Nội dung text: Một cách tiếp cận mới trong việc giải quyết bài toán chồng phủ vùng sử dụng cấu trúc dữ liệu danh sách cạnh liên kết kép

1. T¹p chÝ KHKT Má - §Þa chÊt, sè 46, 4-2014, tr.73-76 TRẮC ĐỊA – ĐỊA CHÍNH – BẢN ĐỒ (trang 73-89) MỘT CÁCH TIẾP CẬN MỚI TRONG VIỆC GIẢI QUYẾT BÀI TOÁN CHỒNG PHỦ VÙNG SỬ DỤNG CẤU TRÚC DỮ LIỆU DANH SÁCH CẠNH LIÊN KẾT KÉP TRẦN THÙY DƯƠNG, PHẠM THẾ HUYNH Trường Đại học Mỏ - Địa chất Tóm tắt: Khi giải quyết các bài toán chồng phủ bản đồ, việc khoanh vùng chồng phủ và xác định thuộc tính tổ hợp của hai bản đồ các vùng chuyên đề thường được tiến hành đồng thời khi xác định các giao điểm các cạnh của các bản đồ này. Trong bài báo đã đề xuất một phương pháp khoanh vùng và gán thuộc tính theo một cách tiếp cận khác, được thực hiện sau khi đã có các giao điểm của các cạnh. Để giải quyết vấn đề tác giả đã sử dụng cấu trúc dữ liệu danh sách cạnh liên kết kép để phân tích và xây dựng thuật toán. Các thuật toán và giải pháp được các tác giả xây dựng là không những là một giải pháp để giải quyết bài toán chồng phủ mà còn là cơ sở để xây dựng các chức năng biên tập vùng để hoàn thiện quy trình thành lập bản đồ địa chính trong giai đoạn hiện nay ở Việt Nam. 1. Mở đầu 2. Giải quyết vấn đề Bài toán chồng phủ vùng của hai hay nhiều Bài toán chồng phủ vùng liên quan đến vấn tờ bản đồ là bài toán có nhiều ứng dụng trong đề phân tích các vùng tại giao điểm khi các các hệ thống GIS/LIS. Bài toán chồng phủ đã vùng giao nhau, khi đó cần xem xét đến vấn đề được trình bày trong [2], trong đó đã sử dụng chia cạnh và xác định thuộc tính của các vùng thuật toán quét (plane sweep) giải quyết đồng bị phân chia do chồng phủ (lát kín một vùng), thời bài toán xác định các giao điểm các cạnh từ đó xây dựng nên thuật toán chồng phủ hai tờ và bài toán xác định vùng chồng phủ với các bản đồ sử dụng cấu trúc dữ liệu DCEL. thuộc tính tổ hợp. Cách giải quyết này có ưu 2.1. Chia cạnh điểm là nhanh (có độ phức tạp nlogn) và giải Giả sử ta có hai nửa cạnh ei và ej của hai quyết đồng loạt cho tất cả các vùng của hai tờ vùng bất kỳ giao nhau, trong đó ei thuộc vùng bản đồ. Các thuật toán xác định giao điểm cũng a1 (theo quy ước luôn nằm bên phải của ei), ej được mô tả trong tài liệu [1]. thuộc vùng b1 (hình 1). Tuy nhiên, trong quá trình chồng phủ các vùng ngoài việc xác định các vùng sau khi v2 chồng phủ thì cần phải xác định thuộc tính của v3 a2 chúng. Để giải quyết vấn đề này, có một cách a1 ei giải quyết bài toán này theo một cách tiếp cận e' khác trên cơ sở phân tích các vùng tại giao điểm v i và dùng các vùng bản đồ thứ hai lần lượt lát kín 5 từng vùng của tờ bản đồ thứ nhất. Việc lát vùng sẽ đồng thời cập nhật các thuộc tính của các nửa ej cạnh trong danh sách DCEL. Phương pháp này e'j b2 không những xử lý vấn đề chồng phủ hai bản đồ v b1 v4 mà còn là cơ sở để xây dựng một trong những 1 chức năng biên tập vùng sao cho bảo toàn cấu trúc dữ liệu topo. Hình 1. Giao nhau của hai cạnh 73
2. ' ' Nửa cạnh đảo với ei được ký hiệu là ei , Nửa cạnh đảo với ej được ký hiệu là ej , ' ' vùng giáp bên phải của ei là a2. vùng giáp bên phải của ej là b2. ' Xét 4 nửa cạnh ei, e'i, ej, e'j giao nhau, có a1 với gốc v5 là ej2 và ej1 có góc nghiêng ngược o là vùng phải của ei; a2 là vùng phải e'i; b1 là nhau 180 . Để tìm nửa cạnh ngoặt về bên phải vùng phải của ej; b2 là vùng phải e'j. ta chỉ cần tính góc kẹp phải tại v5 của hai nửa o Nửa cạnh ei sẽ được chia thành hai nửa cạnh ei1 và ej2, nếu góc kẹp này có giá trị từ 0 o cạnh ei1 và ei2 có cùng hướng, cùng thuộc tính đến 180 thì nửa cạnh ej2 là nửa cạnh cần tìm, o vùng phải a1, trong đó gốc của nửa cạnh thứ trường hợp góc kẹp này lớn hơn 180 thì nửa ' nhất ei1 trùng với gốc của ei là v1, còn gốc của cạnh cần tìm sẽ là nửa cạnh ej1 nửa cạnh thứ hai ei2 là điểm chia v5 v2 Theo nguyên tắc chia trên ta có nửa cạnh ej v3 a2 sẽ được chia thành hai nửa cạnh ej1 và ej2 có a1 ei2 cùng hướng, cùng thuộc tính vùng phải b1, gốc ej1 của ej1 trùng với gốc của ej là v3, gốc của ej2 là e'i2 điểm chia v5 e'j1 Kết quả được thể hiện trên Hình 2 ' ' - 4 nửa cạnh ban đầu ei, ei , ej, ej được thay ' ', thế bằng 8 nửa cạnh mới ei1, ei2, ei1 , ei2 ej1, ej2, ei1 v5 ej2 ' ' ej1 , ej2 e' e'j2 b2 - từ các vùng a1, a2 và b1, b2 ta có các vùng i1 chồng phủ a b , a b a b , a b 1 1 1 2, 2 1 2 2 v a b b1 v4 1 1 1 Hình 3. Xác định vùng giao khi gặp điểm chia v2 a2b2 v3 a2 a1 Như vậy, theo hình 3 ta sẽ chọn được hai nửa ei2 ej1 cạnh ei1 và ej2 với các thuộc tính vùng tương e'i2 ứng là a1 và b1. Các nửa cạnh tiếp theo nửa cạnh e'j1 a1b2 ej2 có thuộc tính vùng b1 sẽ dễ dàng được tìm a2b 1 thấy theo cấu trúc DCEL cho đến giao điểm tiếp ei1 v5 ej2 theo của hai cạnh có thuộc tính vùng a1 và b1. Tương tự như vậy, từ điểm giao thứ hai này có e'j2 b2 e'i1 thể dễ dàng xác định tất cả các nửa cạnh có v1 a1b1 b1 v4 thuộc tính vùng a1 cho đến giao điểm tiếp theo. Quá trình này chỉ kết thúc khi quay trở về giao điểm đầu tiên. Kết quả một vùng chồng phủ Hình 2. Nguyên tắc chia cạnh mới sẽ được tạo ra với thuộc tính a1b1 và thuộc 2.2. Lát kín 1 vùng tính vùng của các nửa cạnh nói trên sẽ phải 2.2.1. Khi có giao điểm trên đường biên được lưu thêm thuộc tính là a1b1. Giả sử ta xuất phát từ nửa cạnh ei1 có điểm Bằng cách tạo các vùng mới tại tất cả các đích là điểm chia v5 của vùng bản đồ thứ nhất giao điểm của vùng a1 ta sẽ lần lượt tạo ra các (có thuộc tính a1), cần tìm nửa cạnh của vùng vùng chồng phủ mới có các thuộc tính a1bi. bản đồ thứ 2 (có thuộc tính b1) để tạo vùng Khi lát kín vùng a1 các cạnh của của vùng chồng phủ mới (có thuộc tính tổ hợp a1b1). Đây bi bên trong a1 luôn được sử dụng hai lần, nếu là trường hợp đặc biệt của bài toán khoanh có các cạnh chỉ được sử dụng một lần thì tập vùng. hợp các cạnh này sẽ tạo thành biên một vùng Để giải quyết trường hợp này, ta phải chọn nằm trong a1 (hình 4). Tiếp tục theo trình tự như nửa cạnh tiếp theo có gốc là điểm chia v5 đồng trên cho vùng nằm trong a1 này cho đến khi lát thời có hướng quay về bên phải. Hai nửa cạnh kín hết vùng a1. 74
3. Phần còn lại (nếu có) sau khi xét hết các nửa cạnh của ai a1 bj Các vùng của bản đồ A: nét liền Các vùng của bản đồ B: nét đứt Hình 4. Lát kín một vùng khi có giao điểm trên đường biên Sau khi lát kín toàn bộ vùng a1 thì quá trình được tiếp tục cho tới khi lát xong tất cả các Biết được vùng bj thì toàn bộ vùng ai sẽ vùng ai được lát kín nếu vùng bj không chứa các vùng 2.2.2. Lát kín 1 vùng khi không có giao điểm bên trong (vùng đảo). Trường hợp vùng bj có trên đường biên các vùng đảo bên trong thì ta lại xác định bài Khi tất cả các nửa cạnh của vùng ai đều toán ngược lại, tìm tất cả các vùng đảo của bj không có giao điểm với cạnh của các vùng b nằm trong vùng ai. Khi đó vùng chồng phủ ai sẽ (hình 5), vấn đề đầu tiên cần phải giải quyết là bổ sung thêm các vùng đảo này cùng thuộc tính xác định vùng ai hiện đang ở trong vùng bj nào tổ hợp tương ứng. Đối với phần bên trong các hoặc chứa những vùng bj nào. Ta chỉ cần lấy vùng đảo cách xử lý hoàn toàn tương tự. một đỉnh đầu mút trong các cạnh của vùng ai và 2.3. Thuật toán chồng phủ sử dụng thuật toán định vị điểm theo phương Trên cơ sở các phân tích trên, ta có thể xây pháp bản đồ hình thang [2], [3] với độ phức tạp dựng một quy trình thuật toán theo các bước O(logn) để xác định điểm thuộc vùng bj nào. như sau: Đầu vào: Danh sách cạnh liên kết kép của bj bản đồ A có n vùng và bản đồ B có m vùng Đầu ra: Danh sách liên kết kép cho bản đồ AB mô tả kết quả chồng phủ ai a. Xác định giao điểm các cạnh, bổ sung các điểm giao, tại các giao điểm này chia và cập nhật thuộc tính vùng các nửa cạnh theo nguyên tắc ở mục 2.1 đồng thời xác định góc ngoặt phải phù hợp (mục 2.2.1) và gắn thuộc tính cạnh trước, cạnh sau ngay cho các nửa cạnh này. Tất cả các nửa cạnh bị chia sẽ lưu thành nửa cạnh lịch sử. b. Lát từng vùng ai (i=1-n) Hình 5. Lát kín một vùng khi Bước 1. Xuất phát từ nửa cạnh đầu tiên của không có giao điểm trên đường ai gọi là e1, đánh dấu xét e1 biên 75
4. Bước 2. Tìm nửa cạnh đi tiếp (next) cho tới khi chồng phủ hai tờ bản đồ đều được xác định khi điểm cuối của nó trùng với điểm đầu của e1 và gắn thuộc tính. Như vậy, thuật toán đã thỏa - Nếu thuộc tính vùng phải của tất cả các mãn yêu cầu đặt ra. nửa cạnh thuộc vùng mới vừa tạo đều là ai thì Để thực hiện chồng phủ hai tờ bản đồ cần vùng này không giao với B, lúc này cần tìm xác định giao điểm mà độ phức tạp của bài toán xem nó thuộc vùng bj nào theo thuật toán trình xác định giao điểm theo các tài liệu [1, 2, 3, 4] bày trong mục 2.2.2 và gắn thuộc tính aibj. đều là O(nlogn) nên độ phức tạp của cả quá trình chồng phủ sẽ là O (nlogn). - Nếu có một nửa cạnh bất kỳ trong danh Việc xử lý lát từng vùng theo thuật toán ở sách nửa cạnh của vùng vừa tạo thuộc b thì ta j mục 2.3 với cấu trúc dữ liệu danh sách cạnh liên được ngay thuộc tính a b . i j kết kép sẽ cho độ phức tạp thuật toán trung bình Bước 3. Lần lượt lấy nửa cạnh chưa đánh là O(n) do xử lý lần lượt từng phần tử của danh dấu xét của ai và lặp lại các bước 1, 2 cho đến sách, trường hợp cần sử dụng thuật toán tìm khi xét hết các nửa cạnh của ai điểm trong vùng có độ phức tạp là O(logn) [2, Bước 4. Kiểm tra trong tất cả các nửa cạnh 3]. Như vậy, độ phức tạp của thuật toán chồng của B đã dùng, liệt kê danh sách các nửa cạnh phủ trên cũng sẽ là O(nlogn). đảo chưa dùng. Ở đây xảy ra hai trường hợp: Điều đó cho thấy, với thuật toán nhóm tác - Nếu không còn nửa cạnh đảo chưa dùng giả xây dựng, độ phức tạp thuật toán của quá thì ai đã được lát hết, lúc này chuyển sang trình chồng phủ không tăng nhưng lại đem lại bước 5. sự linh hoạt cho các thao tác biên tập vùng. - Nếu còn nửa cạnh đảo chưa dùng thì từ TÀI LIỆU THAM KHẢO danh sách này tạo ra một vùng khép kín mới gọi là b . Lấy b đóng vai trò như một a và quay trở y y i [1]. Robert Sedgewick, 1995. Cẩm nang thuật lại bước 1. toán, Tập 2, Nhà xuất bản Khoa học kỹ thuật. Bước 5. Chuyển sang vùng ai tiếp theo và [2]. Mark de Berg, Marc van Kreveld, Mark quay trở lại bước 1 cho đến khi lát hết các vùng Overmars, Otfried Schwarzkopt, 2000. ai thì sẽ được danh sách liên kết kép AB mô tả Computational Geometry, Algorithms and kết quả chồng phủ hai bản đồ A và B. Applications, Springer-Verlag, Berlin: 29-33. 3. Kết luận [3]. Joseph O'Rourke, 1998. Computational Thuật toán của nhóm tác giả xây dựng đã Geometry in C, Second Edition, Cambridge được thử nghiệm với nhiều trường hợp khác University Press, New York. nhau của hai tờ bản đồ, hình 4 là một ví dụ trực [4]. Michael F. Worboys, 1995. GIS: A quan thử nghiệm trường hợp tổng quát của thuật Computing Perspective, Taylor & Francis, toán. Với thuật toán này, tất cả các vùng tạo ra London. SUMMARY New method of solving overlay problem using dcel structure Tran Thuy Duong, Pham The Huynh, Hanoi University of Mining and Geology When solving map overlay problem, making the overlays and determining combined attribute of two subdivisions is usually carried out together with determining the intersections of edges of the maps. In this paper was introduced one method of making the overlays and giving the attributes by another aproach after determining intersections of edges. To solve this problem the authors used data structure of Doubly Connected Edges List for analizing and bulding the algorithm. The algorithms and the method introduced by authors are not only for solving the maps overlay problem but also a basic of bulding of editing topo functions which has important role of improving cadastral mapping in Vietnam. 76