tailieunhanh - 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

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 đề 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. | T¹p chÝ KHKT Má - §Þa chÊt, sè 46, 4-2014, 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 Bài toán chồng phủ vùng của hai hay nhiều tờ bản đồ là bài toán có nhiều ứng dụng trong các hệ thống GIS/LIS. Bài toán chồng phủ đã được trình bày trong [2], trong đó đã sử dụng thuật toán quét (plane sweep) giải quyết đồng thời bài toán xác định các giao điểm các cạnh và bài toán xác định vùng chồng phủ với các thuộc tính tổ hợp. Cách giải quyết này có ưu điểm là nhanh (có độ phức tạp nlogn) và giải quyết đồng loạt cho tất cả các vùng của hai tờ bản đồ. Các thuật toán xác định giao điểm cũng được mô tả trong tài liệu [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 chồng phủ thì cần phải xác định thuộc tính của chúng. Để giải quyết vấn đề này, có một cách giải quyết bài toán này theo một cách tiếp cận khác trên cơ sở phân tích các vùng tại giao điểm và dùng các vùng bản đồ thứ hai lần lượt lát kín 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