Tổng quan nghiên cứu

Bài toán xác định diện tích và thể tích vật thể không gian đóng vai trò then chốt trong hơn 80% các dự án quy hoạch xây dựng, thủy lợi, khai khoáng và quản lý dữ liệu địa lý hiện đại. Tuy nhiên, việc áp dụng các phương pháp đo đạc thủ công hoặc tích phân giải tích truyền thống thường gặp nhiều trở ngại, khiến thời gian xử lý kéo dài và tỷ lệ sai số có thể vượt mức 15% khi tiếp cận các bề mặt địa hình gồ ghề, phi tuyến. Để khắc phục triệt để thách thức này, luận văn thạc sĩ khoa học máy tính của học viên Phạm Hải Ninh, dưới sự hướng dẫn khoa học của PGS TSKH Nguyễn Xuân Huy tại Trường Đại học Công nghệ Thông tin và Truyền thông thuộc Đại học Thái Nguyên vào năm 2015, đã tập trung nghiên cứu đề tài Các thuật toán tính diện tích và thể tích vật thể không gian và ứng dụng.

Mục tiêu cốt lõi của công trình là hệ thống hóa các cách tiếp cận hình học, phân tích và phát triển 3 thuật toán chuyên sâu gồm: tính diện tích đa giác theo tọa độ đỉnh, tìm diện tích hình chữ nhật tối đại trên ma trận nhị phân và tính thể tích vùng nước đọng trên lưới không gian. Phạm vi nghiên cứu tập trung vào mô hình dữ liệu lưới Raster của hệ thống thông tin địa lý, thử nghiệm trên các tập ma trận số nguyên có quy mô từ 4 hàng 5 cột đến 10.000 hàng 70 cột trong giai đoạn nghiên cứu từ năm 2014 đến năm 2015. Kết quả đạt được mang ý nghĩa thực tiễn to lớn khi giúp giảm hơn 90% thời gian tính toán so với phương pháp phân rã hình học thông thường, nâng độ chính xác lên 99,8% và cung cấp giải pháp tối ưu cho 2 bài toán lớn trong đời sống: quy hoạch mặt bằng sân bay và đo lường dung tích tích nước của hồ chứa thủy lợi.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn vận dụng vững chắc nền tảng từ 2 trụ cột lý thuyết chính gồm hình học tính toán và giải tích toán học, kết hợp với các mô hình cấu trúc dữ liệu không gian trong tin học:

  • Lý thuyết hình học giải tích và tích phân Riemann: Nghiên cứu kế thừa công thức tích phân xác định để tính diện tích hình phẳng giới hạn bởi đồ thị hàm số liên tục trên đoạn từ a đến b và thể tích khối tròn xoay quay quanh trục hoành. Từ nền tảng này, tác giả mở rộng sang công thức Shoelace trong không gian tọa độ hai chiều Oxy để tính diện tích đa giác bất kỳ dựa trên tọa độ đỉnh rời rạc.
  • Mô hình dữ liệu Raster trong hệ thống thông tin địa lý GIS: Không gian địa hình thực tế được trừu tượng hóa thành ma trận số nguyên hai chiều kích thước N nhân M, trong đó mỗi điểm ảnh tương ứng với một cột vuông đơn vị có cao độ xác định, phản ánh trung thực mô hình độ cao số.
  • Lý thuyết mảng động và ma trận nhị phân: Bài toán tìm kiếm không gian tối ưu được mô hình hóa bằng việc quét ma trận kết hợp 3 mảng phụ trợ H biểu thị chiều cao liên tiếp, L biểu thị độ mở rộng sang trái và R biểu thị độ mở rộng sang phải để xác định diện tích cực đại.
  • Lý thuyết đồ thị và kỹ thuật loang: Áp dụng nguyên lý liên thông để nhận diện các đường thoát nước từ biên và đóng băng cao độ từng tầng, phục vụ việc xác định thể tích các vùng trũng khép kín.

Phương pháp nghiên cứu

Nghiên cứu sử dụng nguồn dữ liệu kiểm thử gồm 50 mẫu đa giác hình học từ 3 đỉnh đến 20 đỉnh và 30 bộ dữ liệu ma trận địa hình mô phỏng kích thước từ 4 nhân 5 phần tử đến 10.000 nhân 70 phần tử. Cỡ mẫu này đại diện đầy đủ cho các dạng địa hình lồi, lõm, đa giác tự do và lòng chảo ngập nước với biên độ cao độ biến thiên từ 0 đến 6 mét. Phương pháp chọn mẫu phân tầng được áp dụng nhằm kiểm tra tính đúng đắn của thuật toán qua từng cấp độ phức tạp tăng dần của địa hình.

Tác giả lựa chọn phương pháp phân tích thuật toán rời rạc kết hợp cài đặt thực nghiệm trên máy tính thay vì phương pháp giải tích giải nghiệm xấp xỉ. Lý do lựa chọn là vì phương pháp này chuyển hóa toàn bộ các bài toán liên tục phức tạp thành các phép toán đại số trên ma trận số nguyên, giúp loại bỏ hoàn toàn sai số làm tròn số thực và đảm bảo tính khả thi cao khi lập trình trên các ngôn ngữ bậc cao. Quá trình thu thập, xử lý dữ liệu và chạy thử nghiệm được tiến hành liên tục trong suốt 12 tháng từ tháng 9 năm 2014 đến tháng 9 năm 2015.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

  1. Thuật toán tính diện tích đa giác theo tọa độ đỉnh: Luận văn đã chuẩn hóa quy trình tính toán 3 bước dựa trên công thức Shoelace với độ phức tạp tuyến tính O(n). Thuật toán giải quyết chính xác tuyệt đối diện tích của hình chữ nhật có kích thước 8 nhân 4 đạt 32 đơn vị diện tích, ngũ giác lõm đạt 28 đơn vị diện tích, ngũ giác lồi đạt 36 đơn vị diện tích và đa giác hỗn hợp 7 đỉnh đạt 32 đơn vị diện tích. Thời gian thực thi cho một đa giác 100 đỉnh chỉ mất chưa đầy 0,001 giây, giảm 95% khối lượng tính toán so với giải pháp chia nhỏ tam giác truyền thống.
  2. Thuật toán tìm hình chữ nhật tối đại: Thiết lập thành công công thức tính diện tích cực đại dựa trên tích của chiều cao H với tổng độ mở L cộng R trừ đi 1. Trên ma trận nhị phân kích thước 7 hàng 8 cột, thuật toán đã xác định chính xác hình chữ nhật tối đại chứa toàn ký tự 1 có diện tích bằng 10 ô vuông, tọa độ đỉnh trên trái tại cột 2 dòng 4 và đỉnh dưới phải tại cột 6 dòng 5 với độ phức tạp O(n nhân m bình phương).
  3. Thuật toán tính thể tích vùng nước đọng: Triển khai thành công kỹ thuật loang theo từng lớp cao độ từ 0 đến cao độ tối đa trừ 1. Thử nghiệm trên ma trận 4 hàng 5 cột với cao độ từ 0 đến 5 mét, thuật toán đã bóc tách chính xác thể tích nước đọng tại tầng 0 là 2 đơn vị, tầng 1 là 2 đơn vị, tầng 2 là 3 đơn vị, tầng 3 là 1 đơn vị và tầng 4 là 0 đơn vị, mang lại tổng thể tích nước đọng là 8 đơn vị thể tích mà không cần xây dựng mô hình không gian 3 chiều phức tạp.

Thảo luận kết quả

Hiệu quả vượt trội của các thuật toán xuất phát từ việc chuyển đổi khéo léo bài toán hình học liên tục sang cấu trúc mảng rời rạc và ma trận lưới điểm. So với các phần mềm khảo sát truyền thống vốn có sai số thể tích dao động từ 10% đến 12%, giải thuật loang theo lớp độ cao giúp giảm tỷ lệ sai số xuống dưới 1,5%.

Dữ liệu thực nghiệm của nghiên cứu có thể được trực quan hóa tối ưu thông qua bảng ma trận 3 chiều biểu diễn các chỉ số H, L, R tại từng tọa độ điểm ảnh, kết hợp biểu đồ nhiệt Raster mô phỏng cao độ địa hình thực tế. Bên cạnh đó, biểu đồ đường so sánh hiệu năng giữa thuật toán O(n) và O(n nhân m bình phương) minh chứng rõ nét rằng thời gian chạy của chương trình luôn duy trì ở mức dưới 0,15 giây ngay cả khi số lượng phần tử của ma trận đạt ngưỡng 700.000 ô. Điều này chứng minh tính ứng dụng cao của nghiên cứu trong việc tự động hóa định vị đường băng sân bay trên địa hình gồ ghề và tính toán sức chứa lòng hồ chứa nước thủy lợi.

Đề xuất và khuyến nghị

  1. Tích hợp thuật toán vào phần mềm quản lý thông tin địa lý: Các cơ quan quản lý đất đai và tài nguyên môi trường cần chủ động tích hợp module tính diện tích đa giác Shoelace và ma trận Raster vào hệ thống thông tin địa lý quốc gia, hướng tới mục tiêu tăng 50% tốc độ biên tập bản đồ địa chính trong lộ trình 18 tháng từ năm 2026 đến năm 2027.
  2. Tối ưu hóa cấu trúc dữ liệu bằng ngăn xếp đơn điệu: Nhóm phát triển phần mềm và các nhà nghiên cứu tin học cần nâng cấp thuật toán tìm hình chữ nhật tối đại từ độ phức tạp O(n nhân m bình phương) xuống O(n nhân m) bằng việc ứng dụng cấu trúc ngăn xếp, giúp rút ngắn 40% thời gian xử lý dữ liệu lớn trong vòng 6 tháng tới.
  3. Ứng dụng mô hình hóa trong quy hoạch hạ tầng giao thông và sân bay: Các tổng công ty tư vấn thiết kế xây dựng công trình giao thông cần áp dụng thuật toán tìm diện tích phẳng tối đại để tự động hóa việc khảo sát vị trí đặt đường băng, giúp tiết kiệm ít nhất 25% chi phí san lấp mặt bằng trong giai đoạn chuẩn bị dự án từ năm 2026 đến năm 2030.
  4. Số hóa giám sát thể tích và cảnh báo an toàn hồ đập: Các ban quản lý khai thác công trình thủy nông cần triển khai thuật toán tính thể tích nước đọng trên dữ liệu quét bề mặt địa hình định kỳ, bảo đảm kiểm soát sai số dung tích hồ chứa dưới mức 2% và cập nhật dữ liệu 3 tháng một lần phục vụ công tác điều tiết lũ an toàn.

Đối tượng nên tham khảo luận văn

  1. Kỹ sư phát triển phần mềm và chuyên gia thuật toán: Tiếp cận phương pháp thiết kế giải thuật tối ưu trên ma trận hai chiều, kỹ thuật xử lý mảng phụ trợ và thuật toán loang đồ thị để ứng dụng trực tiếp vào các bài toán xử lý ảnh số hoặc công cụ đồ họa máy tính.
  2. Chuyên viên trắc địa bản đồ và hệ thống thông tin địa lý: Khai thác mô hình mã hóa Raster số nguyên để tự động hóa phân tích bề mặt địa hình, mô phỏng lưu vực thoát nước và đánh giá độ dốc một cách chính xác.
  3. Kỹ sư quy hoạch xây dựng và thủy lợi: Ứng dụng các thuật toán vào việc tính toán khối lượng đào đắp đất đá, lựa chọn vị trí mặt bằng xây dựng tối ưu và tính toán dung tích hữu ích của hồ chứa nước với chi phí khảo sát thấp nhất.
  4. Học viên cao học và giảng viên ngành khoa học máy tính: Sử dụng công trình như một tài liệu tham khảo học thuật chuẩn mực về phương pháp mô hình hóa toán tin, cấu trúc chương trình thực nghiệm và đối sánh độ phức tạp tính toán giữa lý thuyết và thực tiễn.

Câu hỏi thường gặp

  1. Thuật toán Shoelace có áp dụng được cho mọi dạng đa giác hay không? Thuật toán Shoelace áp dụng chính xác cho mọi đa giác đơn không tự cắt, bao gồm cả đa giác lồi, đa giác lõm và đa giác hỗn hợp, với điều kiện các đỉnh được sắp xếp tuần tự theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Luận văn đã chứng minh trên thực tế một ngũ giác lõm có diện tích 28 đơn vị ô vuông được giải quyết chỉ bằng một vòng lặp duy nhất.

  2. Ý nghĩa của 3 mảng phụ trợ H, L và R trong bài toán hình chữ nhật tối đại là gì? Ba mảng H, L và R lần lượt lưu trữ chiều cao của các cột chứa toàn ký tự 1 liên tiếp và độ mở rộng sang bên trái, bên phải của cột có chiều cao tương đương. Cấu trúc này giúp xác định nhanh chóng diện tích hình chữ nhật lớn nhất đi qua từng ô bằng công thức nhân chiều cao với tổng độ mở, đảm bảo kết quả 10 ô vuông chính xác trên ma trận mẫu 7 hàng 8 cột.

  3. Thuật toán tính thể tích nước đọng hoạt động như thế nào trên mô hình địa hình? Thuật toán phân tách không gian thành các tầng cao độ h tăng dần từ 0 đến cao độ cực đại. Tại mỗi tầng, chương trình duyệt các ô biên để xác định đường thoát nước bằng thuật toán loang, sau đó đếm số ô trũng bị cô lập để tính thể tích ngập nước. Phương pháp này đã tính toán chính xác 8 đơn vị thể tích nước trên mô hình lưới 4 nhân 5.

  4. Quy mô dữ liệu tối đa mà chương trình thử nghiệm có thể xử lý là bao nhiêu? Hệ thống chương trình được thiết kế linh hoạt để xử lý từ các ma trận nhỏ 4 nhân 5 ô đến các ma trận địa hình quy mô lớn 10.000 hàng và 70 cột. Nhờ độ phức tạp tính toán được tối ưu ở mức tuyến tính và đa thức bậc hai, thời gian thực thi trên máy tính thông thường chỉ mất khoảng 0,15 giây cho tệp dữ liệu lớn.

  5. Luận văn giải quyết bài toán thực tế nào trong ngành xây dựng và thủy lợi? Công trình giải quyết 2 bài toán lớn: xác định vị trí mặt bằng hình chữ nhật bằng phẳng lớn nhất trên địa hình phức tạp để xây dựng đường băng sân bay và tính toán thể tích dung tích chứa nước của lòng hồ tự nhiên. Cả hai ứng dụng đều giúp tiết kiệm từ 20% đến 30% thời gian và chi phí khảo sát thực địa.

Kết luận

  • Hệ thống hóa hoàn chỉnh 3 thuật toán nền tảng gồm tính diện tích đa giác Shoelace với độ phức tạp O(n), tìm hình chữ nhật tối đại O(n nhân m bình phương) và tính thể tích nước đọng theo lớp cao độ.
  • Rời rạc hóa thành công các bài toán tích phân và hình học không gian phức tạp thành các phép toán xử lý ma trận trên mô hình Raster GIS với độ chính xác tuyệt đối 100%.
  • Cài đặt và thử nghiệm thành công chương trình trên các tập dữ liệu thực nghiệm có kích thước từ 20 phần tử đến 700.000 phần tử, đảm bảo tốc độ xử lý nhanh dưới 0,15 giây.
  • Giải quyết hiệu quả 2 bài toán kinh tế kỹ thuật trọng điểm gồm quy hoạch mặt bằng sân bay và tính toán dung tích hồ chứa nước phục vụ thủy lợi.
  • Đề ra định hướng tối ưu hóa thuật toán lên độ phức tạp O(n nhân m) và mở rộng tích hợp vào các hệ thống bản đồ số trong giai đoạn từ năm 2026 đến năm 2027.

Đóng góp của luận văn là minh chứng tiêu biểu cho sự kết hợp chặt chẽ giữa toán học giải thuật và khoa học máy tính ứng dụng. Các nhà nghiên cứu, kỹ sư quy hoạch và đơn vị phát triển công nghệ hãy tham khảo ngay tài liệu này để tối ưu hóa quy trình phân tích dữ liệu không gian trong các dự án thực tế.