[Tóm tắt] Luận án Nghiên cứu công nghệ thành lập và ứng dụng bản đồ số địa chính trong điều kiện Việt Nam

hời với quá trình chuyển đổi tọa độ của các đối tượng không gian. Bản đồ tổng thể theo đơn vị hành chính sau khi chuyển đổi hệ tọa độ, tiến hành biên tập lại, tạo mô hình Topo, các thửa đất vẫn lưu trữ chỉ số duy nhất của thửa đất. Khi cần cập nhật thông tin sẽ tham chiếu đến chỉ số này để lấy thông tin thuộc tính. 2.3. Giải pháp chuyên môn hóa công tác nội - ngoại nghiệp 2.3.1. Giải pháp đề xuất - Phân lô thửa đất Phân chia khu vực đo vẽ thành các lô thửa đất liền kề. Các lô thửa đất này được phân chia theo nguyên tắc phân tách nhau bằng các đối tượng hình tuyến như giao thông, thủy lợi... phù hợp với đặc điểm khu đo. Tiến hành đánh số lô thống nhất từ đầu đến cuối trong quá trình đo đạc và biên tập bản đồ. Chỉ số tham chiếu duy nhất đến thửa đất sẽ là: MX.SL.ST, trong đó MX là mã xã, SL là số hiệu lô, ST là số hiệu thửa đất trong lô. Việc đánh số thửa đất thực hiện tuần tự, không được trùng lặp trong lô sao cho các thửa đất liền kề nhau có số hiệu thửa kề nhau để dễ tìm kiếm. Việc đánh số hiệu thửa có thể được thực hiện ngay khi vẽ sơ họa các lô thửa đất. Từ đó, các thửa đất được định danh duy nhất, dễ dàng trong thu thập thông tin thuộc tính, không xảy ra nhầm lẫn khi một số thông tin trùng nhau. - Tạo dữ liệu không gian và dữ liệu thuộc tính - In các lô thửa đất - Đo đạc ngoại nghiệp - Xử lý số liệu nội nghiệp sơ bộ - Kiểm tra đối soát - Biên tập lô thửa đất 2.3.2. Hiệu quả của giải pháp - Tận dụng được nhân lực tổ đo, chuyên môn hóa công việc nội nghiệp và ngoại nghiệp. Công việc ngoại nghiệp không yêu cầu cán bộ kỹ thuật cao, công việc nội nghiệp có thể tận dụng được lượng cán bộ kỹ thuật nữ có kỹ thuật cao, các bản vẽ được biên tập theo một quy chuẩn cụ thể; - Người quản lý có thể kiểm soát được khối lượng công việc thực hiện mọi lúc mọi nơi mà không cần ở tại khu vực đo vẽ (kiểm tra bằng Google Earth); - Việc phân chia khu vực đo vẽ thành các lô thửa đất là một quan điểm mới nhằm mục đích quản lý khu đo một cách hợp lý hơn. Với cách phân chia này dễ kiểm soát, dễ đối 8 soát, chỉnh sửa, các tổ đo sau khi đã được phân công có thể hoạt động độc lập. Tiến hành biên tập riêng rẽ, xuất các hồ sơ thửa đất theo từng lô thửa mà không cần phải thành lập bản đồ tổng như quy trình thành lập bản đồ hiện nay. Quy trình này có thể tận dụng được khả năng làm việc song song giữa đo vẽ bản đồ và xây dựng hồ sơ địa chính đồng thời giúp cho quá trình quản lý đất đai sau này cũng thuận lợi hơn; - Các lô thửa đất được quản lý riêng bảo toàn được mối quan hệ liền kề giữa các thửa đất và thỏa mãn được các yêu cầu của hệ thống tham chiếu thửa đất dù thay đổi sang hệ tọa độ khác. 2.4. Giải pháp lựa chọn mô hình dữ liệu phù hợp quản lý và biên tập Hiện nay, mô hình dữ liệu để quản lý và biên tập các đối tượng đồ họa thường sử dụng hai mô hình chính: Mô hình dữ liệu Spaghetti và mô hình dữ liệu Vector Topo. Để có giải pháp lựa chọn mô hình dữ liệu nào phù hợp với việc quản lý và biên tập bản đồ số địa chính, tiến hành phân tích các mô hình từ đó đưa ra lựa chọn hợp lý. 2.4.1. Mô hình dữ liệu Spaghetti Là mô hình dữ liệu đơn giản, các đối tượng chỉ được lưu trữ bằng các cặp toạ độ. Trong cấu trúc dữ liệu Spaghetti, đơn vị cơ sở là các cặp tọa độ trên một không gian địa lý xác định. Do đó, mỗi đối tượng điểm được xác định bằng một cặp tọa độ (x, y); mỗi đối tượng đường được biểu diễn bằng một chuỗi những cặp tọa độ (xi, yi); mỗi đối tượng vùng được biểu diễn bằng một chuỗi những cặp toạ độ (xj, yj) với điểm đầu và điểm cuối trùng nhau. Đặc điểm: Cấu trúc Spaghetti không ghi nhận đặc trưng kề nhau của hai vùng kề nhau, nghĩa là tại hai vùng kề nhau sẽ có hai cạnh chung kề nhau, cạnh chung của hai vùng kề nhau là hai cạnh độc lập nhau. Cấu trúc này đơn giản, dễ trình bày, biên tập vì vậy vẫn được sử dụng rộng rãi để thành lập bản đồ, tuy nhiên khối lượng lưu trữ lớn, trùng lặp dữ liệu, không ghi nhận đặc trưng kề nhau của các vùng nên khó áp dụng trong quản lý dữ liệu bản đồ số địa chính. 2.4.2. Mô hình dữ liệu Topo Là một mô hình phức tạp, các đối tượng được quản lý không chỉ bởi toạ độ mà còn bằng cả mối quan hệ không gian giữa các đối tượng. 2.4.2.1. Cấu trúc Winged-Edge Topology Cấu trúc Winged-Edge Topology (còn gọi là cấu trúc cạnh có cánh) quản lý các cạnh thửa đất với các mối liên kết cạnh trái trước, trái sau, phải trước, phải sau, mặt trái, mặt phải. Các cạnh đều phải xác định hướng. Đặc điểm của cấu trúc này lưu trữ các cạnh theo hướng do đó việc xác định hướng của cạnh thửa cần đặc biệt quan tâm, từ đó mới xác định được các cạnh trái trước, trái sau, phải trước, phải sau. Ưu điểm: Khối lượng lưu trữ dữ liệu nhỏ do không dư thừa dữ liệu, mỗi cạnh liên kết với bốn cạnh khác. Nhược điểm: Cách lưu trữ tương đối phức tạp, phải tạo mô hình Topo trước thì mới xây dựng được cấu trúc dữ liệu. 2.4.2.2. Cấu trúc dữ liệu Doubly Connected Edge List (DCEL) DCEL là cấu trúc dữ liệu danh sách cạnh liên kết kép quản lý bản vẽ và mối quan hệ Topo giữa các thửa đất (Hình 2.6). Mỗi cạnh thửa đất được quản lý bởi hai nửa cạnh có hướng ngược nhau và nửa cạnh này là nửa cạnh đảo của nửa cạnh kia. DCEL quản lý dữ liệu bởi 3 bảng: Bảng danh sách đỉnh; bảng danh sách nửa cạnh và bảng danh sách vùng. 9 Ưu điểm của cấu trúc dữ liệu DCEL là đơn giản, dễ quản lý, có thể tạo ngay được cấu trúc dữ liệu DCEL mà chưa cần tạo mô hình Topo, chỉ cần dựa vào mối quan hệ không gian giữa các nửa cạnh. Nhược điểm: mô hình này có nhược điểm là dung lượng lưu trữ lớn. Nhược điểm này hiện nay với cấu hình máy tính lớn không còn là vấn đề đáng ngại nữa. 2.4.2.3. Cấu trúc dữ liệu Link-Node Cấu trúc dữ liệu Link-Node là cấu trúc liên kết các điểm + Link là chuỗi các đoạn không cắt nhau có cùng những thuộc tính chung và không cắt các link khác trừ điểm đầu và điểm cuối. + Node: là điểm đầu hoặc điểm cuối của Link, một Node có thể là điểm chung của nhiều Link. Các tọa độ của Node được lưu vào một file riêng biệt, có thể được tham chiếu tới các Link khác qua điểm đầu và điểm cuối của Link đó. Ưu điểm của cấu trúc dữ liệu Link-Node là dung lượng lưu trữ ít hơn, thay các đoạn liền kề chung của hai vùng bằng các Link, ít dư thừa dữ liệu. Nhược điểm: lưu trữ tương đối phức tạp, cần xác định chính xác các Nodes, các Links ngoài ra trên mỗi Link cần quản lý danh sách tọa độ các điểm trong Link, cần phải tạo mô hình Topo trước mới tạo được cấu trúc dữ liệu. Qua nghiên cứu các mô hình dữ liệu cho thấy, các mô hình Topo đều thuận lợi cho việc quản lý mô hình Topo thửa đất, tuy nhiên cấu trúc dữ liệu DCEL quản lý các nửa cạnh độc lập là cấu trúc đơn giản, dễ hiểu, nên dễ xử lý. Chính vì vậy, trong nghiên cứu của luận án, chọn mô hình Topo với cấu trúc dữ liệu DCEL để nghiên cứu. CHƯƠNG 3. SỬ DỤNG CẤU TRÚC DỮ LIỆU DCEL TRONG THÀNH LẬP VÀ ỨNG DỤNG BẢN ĐỒ SỐ ĐỊA CHÍNH Các phần mềm biên tập bản đồ địa chính ở Việt Nam hiện nay hầu hết chỉ tập trung tạo mô hình Topo mà chưa chú trọng đến việc lưu trữ mối quan hệ Topo của các vùng. Chính vì vậy, mỗi khi có sự biến động về thông tin không gian của vùng cần phải xây dựng lại mô hình Topo. Quá trình này vừa tốn thời gian, vừa mất đi các thông tin thuộc tính của các vùng đã có. Sau khi tạo lại Topo người sử dụng phải gắn thêm các dữ liệu thuộc tính cho các vùng phát sinh và việc này thường khó kiểm soát bởi các vùng biến động có thể ở nhiều nơi trên bản vẽ. Chính vì vậy, người sử dụng thông thường gán lại toàn bộ cơ sở dữ liệu thuộc tính trên bản vẽ khi có bất kỳ một biến động nào về vùng dù chỉ những thay đổi nhỏ. Đây là một trong những công việc tốn thời gian và dễ nhầm lẫn, bỏ sót trong công tác nội nghiệp. Để giải quyết vấn đề này, cần phải xây dựng một hệ thống biên tập chuyên dụng với một mô hình cấu trúc dữ liệu Topo phù hợp đồng thời có các giải pháp để quản lý cơ sở dữ liệu khi có biến động về vùng mà vẫn đảm bảo mối quan hệ Topo giữa các vùng. Với cấu trúc dữ liệu lựa chọn là DCEL một số vấn đề quan trọng trong công tác thành v1 v2 v3 v4 Hình 2.6. Mô hình cấu trúc danh sách cạnh liên kết kép v6 e1 e'1 e2 e'2 e4 e'4 e5 e'5 e3 e'3 a1 a2 v5 a3 10 lập và ứng dụng bản đồ số như tạo mô hình Topo, biên tập thửa đất, chồng phủ các vùng cần có những giải pháp, thuật toán cụ thể để thực hiện. Trước hết cần nghiên cứu một số thuật toán cơ sở sẽ áp dụng trong việc sử dụng cấu trúc DCEL thành lập và ứng dụng bản đồ số địa chính. 3.1. Một số thuật toán cơ sở 3.1.1. Sắp xếp và tìm kiếm 3.1.1.1. Sắp xếp nhanh 3.1.1.2. Tìm kiếm nhị phân 3.1.2. Xác định điểm nằm ở phía nào của đoạn thẳng Đoạn thẳng được xem như một vectơ có chiều từ đầu mút thứ nhất đến đầu mút thứ hai. Khi giải quyết bài toán này, chúng ta cần chú ý đến các trường hợp ba điểm thẳng hàng. Hàm ccw có ba giá trị 1, -1 và 0, trong đó 1: điểm xét ở bên trái, -1 :điểm xét ở bên phải. Khi ba điểm thẳng hàng, 1: đầu mút thứ hai nằm giữa, -1: đầu mút thứ nhất nằm giữa, 0: điểm xét nằm trong đoạn thẳng. Hàm này được xây dựng trên cơ sở xét dấu của tích có hướng hai vectơ, vectơ thứ nhất là bản thân đoạn thẳng, vectơ thứ hai nối từ điểm thứ hai đến điểm xét. 3.1.3. Kiểm tra giao của hai đoạn thẳng Trong mối quan hệ giữa hai đoạn thẳng, trường hợp thường gặp nhất là bài toán xác định giao điểm. Tuy nhiên đôi khi chúng ta chỉ muốn biết chúng có thực sự giao nhau hay không mà không cần xác định điểm giao. Trong trường hợp này, chúng ta chỉ cần kiểm tra điều kiện: hai đầu mút của đoạn thẳng này phải nằm ở hai phía so với đoạn thẳng kia và ngược lại, khi đó hàm ccw của hai đầu mút này sẽ có dấu ngược nhau. 3.1.4. Kiểm tra điểm nằm trong đa giác Bài toán này nhằm xác định xem một điểm có nằm trong miền một đa giác khép kín hay không. Bài toán Điểm nằm trong đa giác có nhiều ứng dụng trong thực tiễn. Đây là bài toán cần được giải quyết cho hầu hết các phần mềm đồ họa. Bài toán này sẽ được mở rộng để giải quyết các bài toán phức tạp hơn như đoạn nằm trong một đa giác, miền nằm trong một đa giác. 3.1.5. Phân hoạch không gian đối tượng Khi tổ chức một CSDL, người ta thường sắp xếp chúng theo một cách nào đó để thuận tiện cho việc tìm kiếm dữ liệu khi cần thiết. Việc này cũng tương tự việc tổ chức sắp xếp các từ trong một cuốn từ điển theo thứ tự ABC để thuận tiện cho việc tra cứu. Một ví dụ khác là việc sắp xếp các cuốn sách trong thư viện theo thứ tự của tên các tác giả hoặc sắp xếp theo chủ đề để người thủ thư có thể dễ dàng tìm thấy cuốn sách theo yêu cầu của người đọc. Việc sắp xếp dữ liệu theo thứ tự như vậy đòi hỏi một số phí tổn về thời gian và nguồn lực ban đầu, tuy nhiên việc tìm kiếm chúng sẽ được thực hiện nhanh chóng hơn nhiều. Đối với các loại dữ liệu khác nhau sẽ tương ứng với cách sắp xếp phù hợp khác nhau. Phân hoạch không gian là thuật ngữ để chỉ việc sắp xếp các đối tượng đồ họa theo đặc điểm vị trí của chúng trong không gian với mục đích tương tự. Thông thường, việc tìm kiếm các đối tượng đồ họa được tìm kiếm theo một vùng phẳng nào đó. Trong các ứng dụng thực tế, vùng tìm kiếm được giới hạn bởi một hình chữ nhật là trường hợp thường gặp nhất. 3.1.6. Tính diện tích đại số một đa giác Một đa giác có n đỉnh, mối đỉnh có tọa độ (xi, yi). Diện tích đại số của đa giác S được tính theo công thức cơ bản: 11      n 1i 1i1ii yyx2 1S với yn+1 = y1; y0 = yn Diện tích đại số cho giá trị có dấu, nếu tính theo chiều kim đồng hồ sẽ có dấu dương, tính ngược chiều kim đồng hồ có dấu âm. 3.1.7. Xác định góc hợp bởi phương thẳng đứng với đoạn thẳng Một đoạn thẳng AB nối hai điểm A (xA, yA) và B (xB, yB). Góc α hợp bởi phương thẳng đứng từ A tới đoạn thẳng AB theo chiều kim đồng hồ được tính như sau: Đặt x = xB - xA; y = yB - yA; atn(x) là giá trị arctan của x π = 3.14159265358979 là hằng số Nếu y = 0 và x > 0 thì α = π * 0.5; Nếu y = 0 và x < 0 thì α = 1.5* π Nếu y > 0 thì y xatn    Nếu y < 0 thì y xatn    + π Nếu α < 0 thì α = α + 2* π (Để đảm bảo α luôn không âm) 3.2. Thuật toán tạo mô hình Topo sử dụng cấu trúc DCEL 3.2.1. Nhập điểm, sắp xếp và lọc điểm trùng. Sau khi nhập điểm là tọa độ các đầu mút của các đoạn, việc sắp xếp được thực hiện theo thứ tự: đầu tiên theo X, sau đó theo Y đối với các điểm có X giống nhau. Việc sắp xếp theo hoành độ X sử dụng thuật toán cơ sở QuickSort (theo thuật toán 3.1.1.1), còn khi sắp xếp theo Y vì số điểm trong mỗi đoạn cần sắp nhỏ hơn nhiều, nên có thể sắp xếp theo các phương pháp khác hiệu quả hơn như sắp xếp chọn, sắp xếp chèn... Việc phát hiện và lọc điểm trùng được tiến hành song song với quá trình sắp xếp theo Y, các điểm trùng sẽ bị loại bỏ và các điểm còn lại sẽ được dồn lên trên. Độ phức tạp của bước này phụ thuộc vào việc sắp xếp, do sử dụng QuickSort nên về mặt trung bình độ phức tạp sẽ là O(nlogn). Kết quả thu được là một danh sách điểm đã được sắp xếp với số lượng điểm Nđ 3.2.2. Xác định các đoạn hở, các đoạn giao nhau Một trường hợp thường xảy ra trong thực tế đo đạc ngoại nghiệp, khi một điểm được đo hai lần, do sai số đo và tính toán, dẫn đến tọa độ thu được của điểm này các lần đo có giá trị khác nhau. Đối với trường hợp cần loại bớt một giá trị tọa độ, phải có chỉ tiêu điểm trùng. Cách giải quyết trong trường hợp nối tắt cần xác định vị trí giao nhau của hai cạnh (theo thuật toán 3.1.3), bổ sung một điểm mới và dùng điểm này để chia các cạnh nối tắt thành hai cạnh mới. 3.2.3. Nhập cạnh, sắp xếp, lọc cạnh trùng Sau khi thực hiện việc sắp xếp và lọc điểm trùng, các đầu mút của các đoạn có chỉ số khác nhau sẽ phải trỏ tới các điểm khác nhau. Sau đó sử dụng hàm tìm kiếm nhị phân với khóa là tọa độ đối với danh sách điểm đã lọc và sắp xếp ở bước trên để xác định chỉ số điểm của các đầu mút cạnh (đoạn thẳng) nhập. Tiếp theo, đến bước lọc cạnh trùng, lúc này chỉ cần thao tác trên các chỉ số của đầu mút mà không cần quan tâm đến tọa độ. Trước hết, tiến hành việc sắp xếp các đoạn thẳng với khóa là các chỉ số của đầu mút thứ nhất của các đoạn, sau đó thực hiện việc sắp xếp với khóa là đầu mút thứ 2 đối với những phần mà đầu mút thứ nhất trùng nhau theo góc hợp bởi phương thẳng đứng tới đoạn thẳng từ bé đến lớn. Kết quả thu được là một danh sách đoạn thẳng đã được sắp xếp theo chỉ số của một đầu mút. 12 Kiểm tra nếu một đỉnh chỉ có một hướng thì đỉnh gốc này là đầu tự do sẽ đánh dấu lỗi để kiểm tra sửa chữa cho đến khi hết lỗi, lúc này mỗi đỉnh sẽ có ít nhất hai đoạn thẳng nối với đỉnh này; Các đoạn thẳng này chính là các nửa cạnh trong DCEL. Vấn đề đặt ra là tạo danh sách DCEL từ danh sách này như thế nào. 3.2.4. Xác định thông tin lưu trữ DCEL Bảng danh sách đỉnh xác định hết sức dễ dàng, bảng danh sách nửa cạnh các thông tin đỉnh gốc, nửa cạnh đảo cũng không khó khăn khi xác định. Đỉnh gốc là điểm đầu của đoạn thẳng, nửa cạnh đảo là chỉ số đoạn thẳng có điểm cuối trùng với điểm đầu của đoạn thẳng xét. Như vậy, cần xác định các thông tin còn lại là nửa cạnh sau, nửa cạnh trước và vùng phải của nửa cạnh. Do các đoạn thẳng đã được sắp xếp tăng dần theo điểm đầu và tăng dần theo góc so với phương thẳng đứng của đoạn thẳng nên việc xác định thông tin lưu trữ trong DCEL trở nên hết sức đơn giản bởi một vùng sẽ chứa hai đoạn thẳng kề nhau,. Từ đó, việc xác định thuộc tính nửa cạnh trước và nửa cạnh sau theo phương pháp như sau: Lần lượt xét các đoạn thẳng ei đã sắp xếp theo từng điểm đầu của đoạn thẳng, ký hiệu ei.Next là nửa cạnh sau, ei.Prev là nửa cạnh trước, ei.Twin là nửa cạnh đảo của nửa cạnh xét ei; ei-1 là nửa cạnh bên trái; ei+1 là nửa cạnh bên phải có cùng đỉnh gốc với ei đã sắp xếp theo góc so với phương thẳng đứng (nếu cùng một đỉnh chỉ có hai hướng thì nửa cạnh trái và nửa cạnh phải trùng nhau; nếu có ba hướng trở lên thì nửa cạnh trái của nửa cạnh đầu là nửa cạnh cuối và nửa cạnh phải của nửa cạnh cuối là nửa cạnh đầu trong danh sách sắp xếp theo đỉnh gốc). Gắn thông tin nửa cạnh trước và nửa cạnh sau của cạnh ei theo công thức: ei.Prev = ei+1.Twin; (ei.Twin).Next = ei-1 (3.1) Trên hình 3.3a nửa cạnh xét ei là 23: 21.Twin = 12; 23.Twin = 32; ei-1 = ei+1 = 21 Áp dụng công thức (3.1) được: 23.Prev = 21.Twin; (23.Twin).Next = 21 Trên hình 3.3b nửa cạnh xét ei = 35: 34.Twin = 43; 35.Twin = 53; ei+1 = 34; ei-1 = 32 Áp dụng công thức (3.1) được: 35.Prev = ei+1.Twin hay 35.Prev = 34.Twin = 43 (35.Twin).Next = ei-1 hay 53.Next = 32 3 2 1 3 5 4 2 a. Đỉnh 2 hướng b. Đỉnh nhiều hơn 2 hướng ei ei+1 ei-1 ei ei+1 ei-1 Hình 3.3. Xác định thuộc tính DCEL ek 13 Tương tự như vậy, lần lượt gắn hết thông tin của các nửa cạnh theo từng đỉnh sẽ có đầy đủ thông tin như Đỉnh gốc, Nửa cạnh đảo, Nửa cạnh sau, Nửa cạnh trước của tất cả các nửa cạnh. 3.2.5. Khoanh vùng Sau khi có danh sách các nửa cạnh gắn thông tin theo cấu trúc DCEL, với đặc tính các nửa cạnh trong danh sách sẽ chỉ được sử dụng duy nhất một lần khi khoanh vùng, thuật toán khoanh vùng như sau: Bước 1: Gắn thông tin "đã sử dụng" cho tất cả các nửa cạnh là False; Bước 2: Lần lượt xét từng nửa cạnh ei, kiểm tra thông tin "đã sử dụng" nếu có giá trị là True thì xét nửa cạnh tiếp theo, nếu có giá trị là False thì gắn thông tin "đã sử dụng" là True, lưu thông tin đỉnh gốc vào danh sách điểm của vùng DV(); Bước 3: Kiểm tra nửa cạnh sau của cạnh xét: - nếu Đỉnh gốc của ei.twin (nửa cạnh đảo của ei) trùng với DV(1) thì khép kín vùng, đặt chỉ số vùng (đây là thông tin vùng phải của tất cả các nửa cạnh đã xét) rồi quay lại bước 2; - nếu không, lưu đỉnh gốc của ei.twin vào DV() rồi quay lại bước 3. Trong quá trình khoanh vùng sẽ xảy ra một số trường hợp cần tiến hành loại bỏ các điểm không phù hợp trong DV() ra khỏi đường biên của vùng được tạo. Khi điểm khởi đầu để quét nằm trên đỉnh của một đa giác cụt, các điểm cần loại nằm đối xứng ở hai đầu. Khi điểm xuất phát nằm trên đường biên của vùng trong quá trình khoanh vùng mới gặp phải các đường đa giác cụt, thì các điểm cần loại lại nằm ở giữa. Kết quả của quá trình khoanh vùng là xác định được danh sách các vùng lưu trữ bởi danh sách đỉnh vùng DV(). Xác định diện tích đại số của từng vùng theo danh sách DV(), nếu diện tích đại số của vùng nhỏ hơn 0 ("vùng âm") thì đó là vùng bao ngoài của nhiều vùng có diện tích đại số lớn hơn 0 ("vùng dương") liên thông hoặc là vùng nằm trong một "vùng dương" khác ("vùng đảo"). Như vậy, đối với những "vùng âm", cần phải thực hiện một phép kiểm tra xem vùng này có nằm trong một vùng nào trong số các "vùng dương" hay không, nếu không sẽ là vùng ngoài biên, còn nếu có sẽ là "vùng đảo" của vùng đó và gắn thông tin "vùng đảo" cho DCEL. Kết quả của quá trình khoanh vùng là cấu trúc DCEL đầy đủ cho các vùng. Sử dụng thuật toán cơ sở tìm điểm trong vùng để lấy được chỉ số thửa đất, từ đó gắn kết với bảng thông tin thuộc tính cập nhật thông tin thuộc tính. 3.3. Biên tập thửa đất sử dụng cấu trúc DCEL Sau khi xây dựng được cấu trúc DCEL của các thửa đất, mối quan hệ Topo giữa các thửa đất đã được xác lập, tuy nhiên quá trình biên tập thửa đất không thể tránh được các thao tác tách, gộp thửa nhất, thêm, bớt đỉnh thửa trong quá trình cập nhật biến động đất đai. Vấn đề đặt ra là làm thế nào biên tập các thửa đất mà không làm phá vỡ cấu trúc DCEL đã được xác lập, bảo toàn cấu trúc dữ liệu Topo. 3.3.1. Tách thửa đất Ký hiệu các đỉnh là v kèm chỉ số, ví dụ như vi; các nửa cạnh có kí hiệu là e, ví dụ như ej, các vùng kí hiệu là a, ví dụ như ak. Một thửa đất (sau đây gọi tắt là thửa) ai sẽ bao gồm một danh sách các nửa cạnh có thuộc tính vùng (thửa) là ai. Các nửa cạnh đảo của các nửa cạnh này sẽ có các thuộc tính vùng là các vùng giáp với ai. Khi tách thửa liên quan đến 2 nửa cạnh ei, ej trong vùng với các điểm phân tách m, n lần lượt thuộc ei, ej. Nối các điểm m, n bằng một đường nối (có thể là đoạn thẳng, đường cong hoặc kết hợp nhiều đoạn thẳng, đường cong) sẽ phát sinh ra các điểm mới, 14 các nửa cạnh mới và các thửa mới được đánh số hiệu thửa tăng thêm từ tổng số thửa đã có. Khi chỉnh sửa thửa đất bằng các phép dựng hình sẽ phát sinh các đỉnh và các nửa cạnh mới bên trong thửa. Thửa đất này sẽ được chia nhỏ thành các thửa đất mới. Các thửa đất mới sẽ lát kín thửa đất này. Trước tiên ta xét việc chia thửa đất làm hai bằng một đường chia. Đường chia thửa này có thể có các đầu mút hoặc là nằm trên cạnh hoặc là đỉnh của thửa đất được chia. a. Hai đầu mút đường chia đều nằm trên cạnh thửa Giả sử thửa a2 bị chia thành hai thửa mới bằng một đường chia có hai đầu mút nằm trên nửa cạnh ei và ej. Hình 3.4 mô tả các các cạnh (ei, e’i), (ej, e'j) và các vùng a1, a2, a3 trước khi vùng a2 bị chia. Khi đó ei và ej có cùng thuộc tính vùng là a2 còn các nửa cạnh đảo e'i và e'j sẽ có các thuộc tính vùng tương ứng là a1 và a3 Tại 2 điểm chia trên 2 nửa cạnh ei, ej, 2 nửa cạnh ei, ej và vùng a2 sẽ được lưu thành lịch sử, đồng thời phát sinh thêm các nửa cạnh ei1, ej1, ei2, ej2 . Các nửa cạnh đảo e'i, e'j cũng được xử lý tương tự, sẽ phát sinh các nửa cạnh ek, e’k và các vùng a4, a5.(Hình 3.5). Các thuộc tính của ei1, ei2 sẽ lấy theo thuộc của nửa cạnh ei; các thuộc tính của e’i1, e’i2 lấy theo thuộc tính của nửa cạnh đảo e’i; tương tự, các thuộc tính của ej1, ej2 lấy theo nửa cạnh ej; còn các thuộc tính của e’j1, e’j2 lấy theo nửa cạnh e’j. Cần cập nhật thêm các thông tin nửa cạnh sau, nửa cạnh trước cho các nửa cạnh phát sinh. Lúc này cơ sở dữ liệu sẽ được lưu trữ với các đỉnh, các nửa cạnh mới, đồng thời phát sinh thêm các vùng liên quan. Việc xét đường chia bằng một cạnh (ek và e'k là đảo của nhau) làm đơn giản hóa việc phân tích mà không mất tính tổng quát. Khi xuất hiện điểm chia, cơ sở dữ liệu điểm sẽ được bổ sung. Trong trường hợp này hai điểm chia v1, v2 sẽ được thêm vào cơ sở dữ liệu điểm. Tạo vùng a4: - xuất phát từ nửa cạnh chia ek có điểm đầu là v1, điểm cuối là v2, xác định ej2 có gốc là điểm cuối v2 rồi tìm nửa cạnh tiếp theo của ej2. - tìm nửa cạnh tiếp theo cho đến khi nửa cạnh tiếp theo là ei1 có điểm cuối là v1 - cập nhật thuộc tính cho tất cả nửa cạnh trên vùng thành a4 Tạo vùng a5: -Làm tương tự như trên cho nửa cạnh đảo e'k b. Hai đầu mút của đường chia là đỉnh thửa Nếu đầu mút của đường chia là đỉnh, các nửa cạnh mới và đỉnh mới được tạo ra chỉ nằm trên đường chia ek. Giả sử đường chia xuất phát tại đỉnh v1 là điểm gốc của nửa cạnh ei+1 và là điểm cuối của nửa cạnh ei ; đường chia ek có điểm cuối tại đỉnh v2 là điểm gốc của nửa cạnh ej+1 và là điểm cuối của nửa cạnh ej a2 a1 ei e'i ej e'j Hình 3.4. Các cạnh thửa đất trước khi chia a3 a5 a1 ek e'i1 ej e'j2 Hình 3.5. Hai đầu mút chia trên cạnh a3 a4 e'k ej e'j1 ei e'i2 eiv1 v2 15 Quá trình tạo các vùng a4, a5 sẽ được tiến hành tương tự như mô tả ở mục a, với vai trò của ei như ei1, ej như ej2 ; ei+1 như ei2, ej+1 như ej1 c. Một đầu mút nằm trên cạnh, một đầu mút là đỉnh thửa Đối với trường hợp này khi đầu mút của đường chia nằm trên cạnh sử dụng cách chia được mô tả ở mục a, còn đối với đầu mút của đường chia là đỉnh thửa ta sử dụng cách chia được mô tả ở mục b. 3.3.2. Gộp thửa Thao tác gộp thửa trong Vùng chỉnh sửa cần phải xác định đường bao của thửa đất gộp. Duyệt theo các nửa cạnh của từng thửa đất được chọn, nếu vùng thuộc tính các nửa cạnh đảo không nằm trong danh sách số hiệu thửa đất bị gộp thì nửa cạnh này thuộc đường bao thửa đất mới, thuộc tính của nửa cạnh này sẽ được cập nhật; còn nếu ngược lại thì loại cả hai nửa cạnh này và đưa chúng vào lịch sử lưu trữ. Trong hình 3.8, là ví dụ gộp 3 thửa đất a2, a3, a4 thành thửa đất a5. Các nửa cạnh nét đứt sẽ bị loại bỏ do vùng thuộc tính các nửa cạnh đảo nằm trong danh sách số hiệu thửa đất bị gộp, ngược lại các nửa cạnh nét liền hình thành đường bao thửa đất mới a5. Thông tin DCEL của các nửa cạnh nét liền trên hình vẽ cần được cập nhật lại. 3.3.3. Thêm bớt đỉnh Trường hợp tổng quát khi cạnh (gồm hai nửa cạnh ek, e’k đảo nhau) được thay thế bằng một đường đa tuyến có cùng chung điểm đầu và điểm cuối hoặc ngược lại. Ta nhận thấy các cạnh của đường đa tuyến có thuộc tính giống với (ek, e’k), do đó chỉ cần sao chép thuộc tính của cạnh (ek, e’k) cho từng cạnh của đa tuyến hoặc ngược lại và bổ sung hoặc loại bỏ các điểm, các nửa cạnh cần thiết, cập nhật thêm thông tin nửa cạnh sau và nửa cạnh trước cần thiết. Việc thêm bớt đỉnh thửa không làm tăng giảm số vùng. 3.3.4. Tạo đường song song với cạnh chọn Sau khi chọn được cạnh, nhập khoảng cách và chọn phía tạo đường song song, sẽ xác định được thửa đất chứa nửa cạnh chọn. Tiến hành tìm giao điểm của đường song song này với các nửa cạnh của thửa đất, từ đó xác định các điểm v7, v8 và tạo ra hai vùng mới a4 và a5; vùng a3 và các nửa cạnh bị chia sẽ đưa vào lịch sử để lưu trữ. Cập nhật DCEL bằng cách gán các thuộc tính cho các nửa cạnh mới tạo ra. 3.4. Chồng phủ các vùng sử dụng cấu trúc DCEL 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. Với việc tạo mô hình Topo lại cho hai bản đồ sau khi biến các cạnh giao cắt nhau giữa hai bản đồ thành các đoạn nhỏ hơn sẽ chỉ tạo được các vùng giao khi đó dữ liệu thuộc tính tổ hợp của hai bản đồ cần xử lý phức tạp. 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. Vấn đề chồng phủ bản đồ đã được trình bày trong nhiều tài liệu, 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. Phương pháp giải quyết là trộn hết tất cả các cạnh của hai tờ bản đồ, kiểm tra khi có giao nhau giữa hai đoạn thì chia hai đoạn thẳng giao Hình 3.8. Gộp thửa v2 ei e'i ei+1 e'i+1 ej e'j ej+ e'j+1 a5 a2 a4 a3 a1 16 nhau thành bốn đoạn thẳng. Kết quả sẽ được một danh sách cạnh mới của cả hai bản vẽ, từ đó tiến hành khoanh vùng với danh sách cạnh này. Cách giải quyết này có ưu điểm là nhanh (có độ phức tạp O(nlogn)) và giải quyết đồng loạt cho tất cả các vùng của hai tờ bản đồ. 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 của các nửa cạnh trong danh sách DCEL. Bài toán chồng phủ vùng liên quan đến vấn đề phân tích các vùng tại giao điểm khi các vùng giao nhau, khi đó cần xem xét đến vấn đề chia cạnh và xác định thuộc tính của các vùng bị phân chia do chồng phủ (lát kín một vùng), từ đó xây dựng nên thuật toán chồng phủ hai tờ bản đồ sử dụng cấu trúc dữ liệu DCEL. 3.4.1. Chia cạnh Giả sử ta có hai nửa cạnh ei và ej của hai vùng bất kỳ giao nhau, trong đó ei thuộc vùng a1 (theo quy ước luôn nằm bên phải của ei), ej thuộc vùng b1 (Hình 3.11) Nửa cạnh đảo với ei được ký hiệu là ei', vùng giáp bên phải của ei' là a2 Nửa cạnh đảo với ej được ký hiệu là ej', 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 là vùng phải của ei; a2 là vùng phải e'i; b1 là vùng phải của ej; b2 là vùng phải e'j. Nửa cạnh ei sẽ được chia thành hai nửa cạnh ei1 và ei2 có cùng hướng, cùng thuộc tính vùng phải a1, trong đó gốc của nửa cạnh thứ nhất ei1 trùng với gốc của ei là v1, còn gốc của nửa cạnh thứ hai ei2 là điểm chia v5 Theo nguyên tắc chia trên ta có nửa cạnh ej sẽ được chia thành hai nửa cạnh ej1 và ej2 có cùng hướng, cùng thuộc tính vùng phải b1, gốc của ej1 trùng với gốc của ej là v3, gốc của ej2 là điểm chia v5 Kết quả được thể hiện trên Hình 3.12 - 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, ej1', ej2' - từ các vùng a1, a2 và b1, b2 ta có các vùng chồng phủ a1b1, a1b2, a2b1, a2b2 3.4.2. Lát kín một vùng 3.4.2.1. Lát kín một vùng khi có giao điểm trên đường biên Giả sử xuất phát từ nửa cạnh ei1 có điểm đích là điểm chia v5 của vùng bản đồ thứ nhất (có thuộc tính a1), cần tìm nửa cạnh của vùng bản đồ thứ 2 (có thuộc tính b1) để tạo v2 v1 v3 v4 a2 a1 b2 b1 ei e'i ej e'j Hình 3.11. Giao nhau của hai cạnh v5 v2 v1 v3 v4 a2 a1 b2 b1 ei2 e'i ej2 e'j Hình 3.12. Nguyên tắc chia cạnh v5 ei1 e'i ej1 e'j a2b2 a1b2 a1b1 a2b1 17 vùng chồng phủ mới (có thuộc tính tổ hợp a1b1). Đây là trường hợp đặc biệt của bài toán khoanh vùng. Để giải quyết trường hợp này, chọn nửa cạnh tiếp theo có gốc là điểm chia v5 đồng thời có hướng quay về bên phải. Hai nửa cạnh với gốc v5 là ej2 và e'j1 có góc nghiêng ngược nhau 180o. Để tìm nửa cạnh ngoặt về bên phải chỉ cần tính góc kẹp phải tại v5 của hai nửa cạnh ei1 và ej2, nếu góc kẹp này có giá trị từ 0o đến 180o thì nửa cạnh ej2 là nửa cạnh cần tìm, trường hợp góc kẹp này lớn hơn 180o thì nửa cạnh cần tìm sẽ là nửa cạnh e'j1 Như vậy, theo hình 3.13 sẽ chọn được hai nửa cạnh ei1 và ej2 với các thuộc tính vùng tương ứng là a1 và b1. Các nửa cạnh tiếp theo nửa cạnh ej2 có thuộc tính vùng b1 sẽ dễ dàng được tìm thấy theo cấu trúc DCEL cho đến giao điểm tiếp 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ó thể dễ dàng xác định tất cả các nửa cạnh có 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ủ mới sẽ được tạo ra với thuộc tính a1b1 và thuộc tính vùng của các nửa cạnh nói trên sẽ phải được lưu thêm thuộc tính là a1b1. Bằng cách tạo các vùng mới tại tất cả các giao điểm của vùng a1 ta sẽ lần lượt tạo ra các vùng chồng phủ mới có các thuộc tính a1bi. Khi lát kín vùng a1 các cạnh của của vùng bi bên trong a1 luôn được sử dụng hai lần, nếu có các cạnh chỉ được sử dụng một lần thì tập hợp các cạnh này sẽ tạo thành biên một vùng nằm trong a1 (Hình 3.14). Tiếp tục theo trình tự như trên cho vùng nằm trong a1 này cho đến khi lát kín hết vùng a1. 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 vùng ai. 3.4.2.2. Lát kín 1 vùng khi không có giao điểm trên đường biên Khi tất cả các nửa cạnh của vùng ai đều không có giao điểm với cạnh của các vùng b (Hình 3.15), vấn đề đầu tiên cần phải giải quyết là xác định vùng ai hiện đang ở trong vùng bj nào hoặc chứa những vùng bj nào. Ta chỉ cần lấy một đỉnh đầu mút trong các cạnh của vùng ai và sử dụng thuật toán định vị điểm theo phương pháp bản đồ hình thang với độ phức tạp O(logn) để xác định điểm thuộc vùng bj nào. v2 v1 v3 v4 a2 a1 b2 b1 ei2 e'i ej2 e'j v5 ei1 e'i ej1 e'j a1b1 Hình 3.13. Xác định vùng giao khi gặp điểm chia bj ai Hình 3.14. Lát kín một vùng khi có giao điểm trên đường biên Phần còn lại (nếu có) sau khi xét hết các nửa cạnh của ai 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 Biết được vùng bj thì toàn b sẽ được lát kín nếu vùng bj không ch vùng bên trong (vùng đảo). Trư bj có các vùng đảo bên trong thì ta l định bài toán ngược lại, tìm t đảo của bj nằm trong vùng a chồng phủ ai sẽ bổ sung thêm các vùng đ này cùng thuộc tính tổ hợp tương với phần bên trong các vùng đ hoàn toàn tương tự. 3.4.3. Thuật toán chồng phủ Trên cơ sở các phân tích trên, ta có th xây dựng một quy trình thuật toán theo các bước như sau: Đầu vào: Danh sách c kép của bản đồ A có n vùng và b m vùng; Đầu ra: Danh sách liên k bản đồ AB mô tả kết quả chồng ph a. Xác định giao điểm các cạnh, b điểm giao, tại các giao điểm này chia và c nhật thuộc tính vùng các nửa c xác định góc ngoặt phải phù h 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 lưu thành nửa cạnh lịch sử. b. Lát từng vùng ai (i=1-n) theo sơ đ toán ở hình 3.16. 3.4.4. Đánh giá thuật toán ch Để thực hiện chồng phủ cần xác định giao điểm mà đ bài toán xác định giao điểm theo các tài li đều là O(nlogn) nên độ phức t Việc xử lý lát từng vùng theo thu liên kết kép sẽ cho độ phức tạ tử của danh sách, trường hợp c là O(logn). Như vậy, độ phức t Điều đó cho thấy, với thu chồng phủ không tăng nhưng l chồng phủ. 3.5. Sử dụng cấu trúc DCEL tạo các ứng dụng bản đồ số địa chính 3.5.1. Lập hồ sơ địa chính Hồ sơ địa chính bao gồ thửa đất theo từng tờ bản đồ); biến động đất đai (lưu trữ lịch s chủ sử dụng quản lý đất theo hi 18 ộ vùng ai ứa các ờng hợp vùng ại xác ất cả các vùng i. Khi đó vùng ảo ứng. Đối ảo cách xử lý ể ạnh liên kết ản đồ B có ết kép cho ủ. ổ sung các ập ạnh đồng thời ợp và gắn ạnh bị chia sẽ ồ thuật ồng phủ hai tờ bản đồ ộ phức tạp của ệu ạp của cả quá trình chồng phủ sẽ là O(nlogn). ật toán trên với cấu trúc dữ p thuật toán trung bình là O(n) do xử lý l ần sử dụng thuật toán tìm điểm trong vùng có đ ạp của thuật toán chồng phủ trên cũng s ật toán xây dựng, độ phức tạp thuậ ại đem lại sự linh hoạt cho các thao tác biên t m: Bản đồ địa chính; Sổ mục kê đất đai Sổ địa chính (thể hiện thông tin chủ s ử biến động đất đai); Bảng tổng hợp s ện trạng đo đạc lập bàn đồ địa chính; ai Hình 3.15. Lát kín m không có giao điểm trên đư Hình 3.16. Sơ đồ thu liệu danh sách cạnh ần lượt từng phần ộ phức tạp ẽ là O(nlogn). t toán của quá trình ập vùng khi (thể hiện thông tin ử dụng); Sổ theo dõi ố thửa, diện tích, số Bản mô tả ranh bj ột vùng khi ờng biên ật toán chồng phủ 19 giới, mốc giới thửa đất; Phiếu xác nhận kết quả đo đạc hiện trạng thửa đất; Giấy chứng nhận quyền sử dụng đất. Với bản đồ địa chính được phân chia thành các lô thửa đất, các thửa đất được gắn một chỉ số quản lý duy nhất MX.SL.ST và quản lý cơ sở dữ liệu theo cấu trúc DCEL lưu trữ được lịch sử thửa đất nên việc lập hồ sơ địa chính trở nên đơn giản hơn do quản lý được đầy đủ thông tin thửa đất cũng như mối quan hệ liền kề giữa các thửa đất, hệ thống tham chiếu thửa đất rõ ràng. Các thửa đất được quản lý theo từng lô thửa (phân khu) nên việc quản lý đất đai thuận tiện hơn. Tuy nhiên, để ứng dụng lập hồ sơ địa chính cần có quy định cụ thể về hồ sơ địa chính phù hợp với cách phân lô thửa đất. 3.5.2. Lập bản đồ hiện trạng sử dụng đất Bản đồ hiện trạng sử dụng đất là bản đồ chuyên đề đất đai, thể hiện sự phân bố các loại đất theo quy định về chỉ tiêu kiểm kê theo mục đích sử dụng đất tại thời điểm kiểm kê đất đai và được lập theo đơn vị hành chính các cấp, vùng địa lý tự nhiên - kinh tế và cả nước. Bản đồ hiện trạng sử dụng đất là tài liệu quan trọng và cần thiết cho công tác quản lý lãnh thổ, quản lý đất đai và các ngành kinh tế, kỹ thuật khác đang sử dụng đất. Với nguồn dữ liệu là bản đồ địa chính số, việc thành lập bản đồ hiện trạng sử dụng đất hiện nay được thực hiện bằng cách: - Ghép các tờ bản đồ địa chính số; - Loại bỏ những đối tượng không thuộc nội dung bản đồ hiện trạng trên bản đồ địa chính; - Liên kết các thửa đất liền kề có cùng mục đích sử dụng tạo thành các vùng hiện trạng và tô màu cho các vùng hiện trạng theo quy định; - Biên tập bản đồ hiện trạng sử dụng đất; - Thống kê diện tích đất đai, tạo các bảng biểu báo cáo. Trong các vấn đề trên, vấn đề liên kết các thửa đất liền kề có cùng mục đích sử dụng tốn nhiều thời gian và dễ xảy ra nhầm lẫn. Với cấu trúc DCEL thuật toán xử lý vấn đề này như sau: - Bước 1. Ghép các DCEL của các lô thửa đất bản đồ thành DCEL tổng; Đối với các vùng nằm giữa các lô thửa đất thường là các đối tượng giao thông thủy hệ hình tuyến sẽ thêm các đoạn liên kết giữa các lô thửa để khép kín các đối tượng này bằng công cụ biên tập thửa đất; - Bước 2. Xác định thuộc tính loại đất hiện trạng cho các nửa cạnh DCEL tổng; - Bước 3. Duyệt qua các nửa cạnh của DCEL tổng, nếu các nửa cạnh và nửa cạnh đảo có cùng thuộc tính loại đất thì sẽ bị loại bỏ đồng thời gắn thuộc tính nửa cạnh trước và nửa cạnh sau cho các nửa cạnh thay đổi, sau quá trình này sẽ được DCEL mới của các vùng hiện trạng; - Bước 4. Khoanh vùng các vùng hiện trạng theo thuật toán khoanh vùng sử dụng cấu trúc DCEL đã trình bày ở trên. Với DCEL mới này vấn đề tổng hợp diện tích, tô màu các vùng hiện trạng theo loại đất trở nên tương đối đơn giản. 3.5.3. Lập bản đồ giải phóng mặt bằng Trong công tác giải phóng mặt bằng, bản đồ địa chính là tài liệu vô cùng quan trọng. Nếu có dữ liệu bản đồ địa chính số được cập nhật biến động đất đai thường xuyên và chính xác thì quá trình lập hồ sơ giải phóng mặt bằng giản đơn hơn nhiều. Lúc này, 20 chỉ cần đưa ranh giới giải phóng mặt bằng lên bản đồ địa chính, từ đó xác định các thửa đất liên quan đến công tác giải phóng mặt bằng bằng cách xác định các thửa đất có giao với đường ranh giới giải phóng mặt bằng. Trên bản đồ địa chính chứa đầy đủ các thông tin như thông tin chủ sử dụng đất, tổng diện tích thửa đất, mục đích sử dụng, địa chỉ... đây là những thông tin quan trọng trong quá trình giải phóng mặt bằng. Với cấu trúc DCEL thuật toán tạo vùng cho bản đồ giải phóng mặt bằng như sau: Bước 1. Tiến hành tạo DCEL bản đồ ranh giới giải phóng mặt bằng với các vùng khép kín là đường ranh giới giải phóng mặt bằng. DCEL này gắn thêm thông tin vị trí (trong hoặc ngoài) của nửa cạnh trên đường ranh giới nhằm xác định khu vực giải phóng mặt bằng. Bước 2. Chồng phủ bản đồ ranh giới giải phóng mặt bằng lên các tờ bản đồ địa chính theo thuật toán chồng phủ sẽ xác định được các vùng giải phóng mặt bằng. 3.5.4. Xây dựng hệ thống địa chính đa mục đích Trên cơ sở quản lý được bản đồ số địa chính tới từng thửa đất, mỗi thửa đất được gắn một chỉ số duy nhất định danh thửa. Kết hợp với các bảng cơ sở dữ liệu quan hệ chứa các loại thông tin khác nhau, chồng phủ với các loại bản đồ đơn tính khác, từ đó cho phép tra cứu thông tin đồng thời kết xuất ra các dạng dữ liệu tổng hợp, phân tích với nhiều mục đích khác nhau. CHƯƠNG 4. XÂY DỰNG CHƯƠNG TRÌNH THỬ NGHIỆM 4.1. Lựa chọn ngôn ngữ lập trình Sử dụng ngôn ngữ lập trình Visual Basic chương trình thử nghiệm 4.2. Khái quát về ngôn ngữ lập trình Visual Basic a. Phần giao diện b. Phần chương trình c. Kiểu dữ liệu - biến và hằng d. Tùy biến chế độ biên dịch chương trình bằng Visual Basic 6.0 Phần biên dịnh chương trình thành mã máy, ngôn ngữ lập trình Visual Basic cung cấp có những tùy chọn nâng cao được đề cập dưới đây: - Assume No Aliasing: không sử dụng những bí danh (Alias); - Remove Array Bounds Checks : Kiểm tra giới hạn của mảng; - Remove Integer Overflow Checks : kiểm tra tràn số nguyên; - Remove Floating Point Error Checks: kiểm tra lỗi dấu phẩy động; - Allow Unrounded Floating Point Operations: so sánh những biểu thức chứa dấu phẩy động mà không cần làm tròn với độ chính xác đúng; - Remove Safe Pentium FDIV Checks : kiểm tra an toàn với các phép toán chia 0 (không) của Pentium (Pentium Floating-point Division) và tắt các mã đặc biệt của bộ vi xử lý Pentium với các lỗi FDIV. 4.3. Xây dựng chương trình thử nghiệm Chương trình được tác giả xây dựng bằng ngôn ngữ lập trình Visual Basic 6.0. 4.3.1. Giao diện chương trình Chương trình được thiết kế với giao diện một cửa sổ đồ họa, hệ thống trình đơn bằng tiếng Việt và hệ thống thanh công cụ. 4.3.2. Các trình đơn *. Trình đơn Tệp: Tạo mới, mở bản vẽ DXF, Shape file, DCEL, ghi lại *. Trình đơn Vẽ: Vẽ các đối tượng đồ họa cơ bản như Điểm, Đoạn thẳng, Đa tuyến ... 21 *. Trình đơn Hiển thị: Các chức năng hiển thị như thu, phóng, trượt *. Trình đơn Tiện ích: Có các chức năng Sửa lỗi, tạo vùng, gán chỉ số thửa, chính xác hóa tọa độ, nhập thông tin thuộc tính, tra cứu thông tin, gộp thửa, chia thửa, tạo bản đồ hiện trạng, chuyển sang Google Earth, chồng xếp bản đồ. 4.3.3. Giải pháp tạo thư viện liên kết động phục vụ xây dựng chương trình - Tạo ra 1 file Link.exe mới đặt trong thư mục C:\Program Files\Microsoft Visual Studio\VB98, còn file Link.exe thật thì đổi tên thành 1 file khác (ví dụ là LinkThat.exe). Khi IDE gọi file Link.exe giả (do ta xây dựng lại) thì file Link.exe này sẽ làm nhiệm vụ đọc các tham số được IDE truyền sang, thêm tham số "/DEF" vào và gọi file LinkThat.exe với tham số mới (đã có /DEF). Tất nhiên là phải kiểm tra, nếu có tồn tại các file *.DEF và Project (dự án) cần tạo là Project kiểu DLL thì mới thêm tham số. - Tạo một Project mới trong VB6, kiểu Project là ActiveX DLL. Để nguyên Class1 mà VB6 đã tạo sẵn, không cần viết mã lệnh gì vào đó cả, nhưng vẫn phải giữ lại vì VB6 cần phải có 1 Class trong Project kiểu ActiveX DLL thì mới chạy. Sau đó, thêm vào một module để chứa các hàm cần xây dựng bình thường như các Sub hay Function với khai báo Public (dùng chung). - Tạo tệp Module Definition File (*.DEF): Sử dụng trình soạn thảo NotePad soạn một file cùng tên với tên thư viện cần tạo và có đuôi là DEF - Dịch Project đã tạo ở bước trên tạo thành file DLL dạng Standard, khi đã có thư viện liên kết động dạng *.DLL (ví dụ: MyLibrary.Dll). Kết quả, được thư viện liên kết động *.DLL dạng chuẩn, có thể sử dụng trong các ngôn ngữ lập trình khác. 4.3.4. Giải pháp tăng tốc độ tính toán của chương trình - Chọn kiểu dữ liệu phù hợp khi khai báo biến vì thông thường các kiểu dữ liệu Single và Double sẽ tốn thời gian thực hiện hơn trong các phép toán; - Dùng các phép nhân để thay thế phép chia nếu có thể vì phép chia tốn thời gian hơn phép nhân (ví dụ: sử dụng A * 0.5 thay cho A/2); - Tránh sử dụng biểu thức lũy thừa, khi lập trình lưu ý có thể thay thế bằng các phép nhân đơn giản hơn nếu có thể. Ví dụ sử dụng A*A thay cho A^2; - Kiểm tra những trường hợp đặc biệt ở bên ngoài vòng lặp bởi các phép thử hay kiểm tra điều kiện logic hầu như không mất nhiều thời gian thực hiện, do vậy nên lựa chọn để tránh phải thực hiện nhiều phép toán trong vòng lặp; - Đặt những công việc tính toán lớn ở những vòng lặp bên trong khi bắt buộc sử dụng các vòng lặp lồng nhau thì hiệu quả tính toán sẽ cao hơn; - Cần tùy biến chế độ biên dịch an toàn tùy thuộc ngôn ngữ lập trình để tăng tốc độ tính toán chương trình khi thực thi. 4.3.5. Thử nghiệm chương trình a. Thử nghiệm chính xác hóa tọa độ điểm trên bản vẽ sơ đồ lô thửa Bước 1: Sử dụng chức năng mở tệp lô thửa DXF cần chính xác hóa tọa độ; Bước 2: Mở tệp tọa độ chính xác, tên điểm trùng với tên điểm thể hiện trên lô thửa; Bước 3: Sử dụng chức năng chính xác hóa tọa độ trong trình đơn Tiện ích sẽ được bản vẽ mới đã được chính xác hóa tọa độ với mối liên kết giữa các điểm giống như tệp lô thửa vẽ sơ họa. 22 Kết quả được bản vẽ lô thửa trong hệ tọa độ chính xác thể hiện được ranh giới thửa đất như bản bản vẽ lô thửa vẽ sơ họa. b. Thử nghiệm chuyển đổi bản đồ số địa chính sang Google Earth  Số liệu: Bản đồ xã An Khánh - Hoài Đức - Hà Nội tờ số 24. Tỷ lệ 1/500. Kinh tuyến trục 1050, múi chiếu 30.  Cách sử dụng chương trình: Bước 1: Sử dụng chức năng mở tệp DXF cần chuyển; Bước 2: Chọn chức năng chuyển sang Google Earth với kinh tuyến trục 1050, múi chiếu 30; Bản đồ sau khi chuyển sang Google Earth sẽ giúp cho việc quản lý và đối soát thuận lợi. c. Thử nghiệm sử dụng cấu trúc DCEL trong biên tập và xây dựng ứng dụng bản đồ số địa chính *. Tạo mô hình Topo *. Nhập thông tin thửa đất từ cơ sở dữ liệu Dữ liệu thuộc tính thửa đất được lưu trữ trong bảng tính Excel được liên kết với dữ liệu không gian thông qua chỉ số duy nhất của thửa đất. *. Gộp thửa 23 Các thửa đất cần gộp được chọn trực tiếp trên bản vẽ, sau khi chọn xong nhấn chuột phải sẽ hiện ra bảng gộp thửa đất. Nhấn nút "Gộp thửa" sẽ gộp các thửa đất được chọn thành một thửa mà không cần tạo lại mô hình Topo. * Tách thửa *. Tra cứu thông tin thửa đất *. Tạo bản đồ hiện trạng sử dụng đất Qua quá trình thực nghiệm đã hiện thực hóa được các phân tích lý thuyết, kiểm nghiệm lại những thuật toán sử dụng mô hình dữ liệu DCEL, áp dụng giải pháp tăng tốc độ tính toán cho thấy hiệu quả rõ rệt, từ đó thấy được tính đúng đắn của thuật toán xây dựng cũng như những giải pháp hoàn thiện quy trình công nghệ thành lập và ứng dụng bản đồ số địa chính mang tính khả thi và phù hợp với điều kiện Việt Nam; giải pháp tăng tốc độ tính toán thực sự hiệu quả, có thể áp dụng trong các ngôn ngữ lập trình và các chương trình khác nhau. 24 KẾT LUẬN VÀ KIẾN NGHỊ Luận án đã nghiên cứu quy trình công nghệ thành lập và ứng dụng bản đồ số địa chính ở Việt Nam hiện nay, đánh giá các ưu nhược điểm, từ đó đưa ra các giải pháp hoàn thiện quy trình công nghệ thành lập bản đồ địa chính phù hợp với các tiến bộ khoa học kỹ thuật và công nghệ thông tin hiện nay. Với các giải pháp hoàn thiện là bước đột phá mới trong quy trình, có nhiều điểm mới, đã được kiểm chứng ở Công ty cổ phần khảo sát thiết kế và xây dựng Miền Bắc và xí nghiệp cổ phần công nghệ GIS thuộc Công ty tư vấn triển khai công nghệ và xây dựng Mỏ - Địa chất. Qua các nghiên cứu, đánh giá một cách tỉ mỉ, khách quan cùng với các phân tích, thuật toán, thực nghiệm cụ thể cho thấy: - Cách tiếp cận mới về thông tin trực quan làm chuyên môn hóa công tác nội- ngoại nghiệp đẩy nhanh tốc độ thành lập bản đồ địa chính; - Quan điểm mới về quy trình công nghệ thành lập bản đồ địa chính phù hợp với sự tiến bộ của khoa học kỹ thuật ở Việt Nam hiện nay; - Sử dụng cấu trúc dữ liệu danh sách cạnh liên kết kép là giải pháp phù hợp để quản lý và khai khác dữ liệu bản đồ số địa chính vừa linh hoạt trong công tác thành lập vừa dễ dàng trong việc cập nhật biến động đất đai; - Thuật toán chồng phủ các vùng sử dụng cấu trúc dữ liệu danh sách cạnh liên kết kép là một thuật toán mới làm tăng tính linh hoạt khi tạo vùng, vừa lưu trữ được thông tin thuộc tính vừa đảm bảo tốc độ xử lý các vùng chồng phủ; - Phương pháp tối ưu hóa sử dụng hợp lý nguồn tài nguyên của môi trường lập trình là một trong những biện pháp hiệu quả để tăng tốc độ chương trình. * Kết luận: Luận án đã giải quyết được những vấn đề còn tồn tại phân tích trong phần tổng quan: - Đề xuất được một số giải pháp hoàn thiện quy trình công nghệ thành lập và ứng dụng bản đồ số địa chính trong điều kiện Việt Nam để vừa thuận lợi trong quá trình thành lập vừa dễ dàng trong công tác cập nhật biến động đất đai phù hợp với sự tiến bộ của khoa học công nghệ ngày nay. - Đề xuất sử dụng cấu trúc dữ liệu DCEL và xây dựng các thuật toán với cấu trúc dữ liệu này làm cơ sở xây dựng hệ thống phần mềm đồ họa độc lập phù hợp với điều kiện Việt Nam trong công tác thành lập và ứng dụng bản đồ số địa chính. - Chương trình thử nghiệm đã hiện thực hóa được các phân tích lý thuyết, kiểm nghiệm lại những thuật toán và các giải pháp từ đó thấy được tính đúng đắn của các thuật toán xây dựng và các giải pháp đề xuất. *. Kiến nghị Những giải pháp đưa ra làm thay đổi cả một hệ thống quy trình công nghệ thành lập bản đồ số địa chính, vì vậy tác giả kiến nghị: - Cần có những nghiên cứu cụ thể, hội thảo rộng rãi giữa các nhà khoa học và đơn vị sản xuất để xây dựng một hệ thống quy định kỹ thuật thống nhất trong công tác thành lập bản đồ số địa chính; - Cần có những chính sách ưu tiên và có sự đầu tư nhiều hơn nữa về trang thiết bị kỹ thuật và kinh phí để xây dựng hệ thống phần mềm đồ họa độc lập của Việt Nam giải quyết tất cả các bước từ thu thập số liệu đến biên tập bản đồ số địa chính và ứng dụng bản đồ số địa chính một cách hiệu quả. 25 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ CỦA TÁC GIẢ 1. Nguyễn Trọng San, Phạm Thế Huynh (2007), "Giải pháp chuyển đổi bản đồ địa chính từ hệ HN-72 sang hệ VN-2000", Tạp chí khoa học kỹ thuật Mỏ - Địa chất, (18), tr. 84-86. 2. Phạm Thế Huynh (2007), "Nghiên cứu sử dụng thư viện mã nguồn mở MapObject vào khai thác thông tin không gian và thuộc tính bản đồ", Tạp chí khoa học kỹ thuật Mỏ - Địa chất, (20), tr. 29-33. 3. Phạm Thế Huynh, Đinh Hải Nam (2011), "Cập nhật thông tin địa chính từ Excel sang Famis và tự động hóa tổng hợp diện tích các loại đất trên bản đồ địa chính", Tạp chí khoa học kỹ thuật Mỏ - Địa chất, (34), tr. 37-40. 4. Trần Thùy Dương, Phạm Thế Huynh, Nguyễn Công Sơn, Nguyễn Duy Hoàng (2011), "Một cách tiếp cận mới về vấn đề tăng tốc độ tính toán trong lập trình ứng dụng", Tạp chí khoa học kỹ thuật Mỏ - Địa chất, (34), tr. 17 - 22. 5. Trần Thùy Dương, Phạm Thế Huynh (2014), "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", Tạp chí khoa học kỹ thuật Mỏ - Địa chất, (46), tr. 73-76. 6. Phạm Thế Huynh (2014), "Một cách tiếp cận mới trong việc giải quyết bài toán biên tập thửa đất sử dụng cấu trúc dữ liệu danh sách cạnh liên kết kép", Tạp chí khoa học Đo đạc và Bản đồ, (20), tr. 14-18. 7. Đinh Hải Nam, Phạm Thế Huynh, Trần Thùy Dương (2014), "Xử lý đối tượng thửa đất có cạnh là đường cong", Tạp chí khoa học Đo đạc và Bản đồ, (21), tr. 13-20. 8. Nguyễn Trọng San, Phạm Thế Huynh, Nguyễn Thế Công (2003), "Nghiên cứu quy trình công nghệ chuẩn hóa hệ tọa độ, chính xác hóa và hiện chỉnh bản đồ địa chính", Đề tài cấp Bộ mã số B2003-36-58. 9. Phạm Thế Huynh, Trần Thùy Dương (2008), "Nghiên cứu xây dựng các đối tượng đồ họa phục vụ quá trình tự động hóa thành lập bản đồ địa chính trong điều kiện Việt Nam", Đề tài cấp Bộ mã số B2008-02-51.