不規則三角網格之視域計算與應用

Visibility Computation and Applications on Triangulated Irregular Networks

鄭松賓(Sung-Pin Cheng)

指導教授 ： 曾定章

國立中央大學/資訊電機學院/資訊工程學系/碩士(2006年)

摘要

由於地理資訊系統的廣泛與普及化運用，各種不同的計算與分析需求亦不斷地產生。對於地理資訊系統使用者而言，可以依照本身的需求，選擇適合的計算與分析方法以取得所需資訊是很重要的；例如，許多地理資訊系統相關的應用需要視域計算，諸如手機基地台之最大涵蓋範圍地點分析、瞭望台之最佳視野範圍地點分析、軍隊行軍撤退之最隱蔽路線等。
本研究是針對視域計算技術進行研究與實作。我們提出一個以不規格三角網格地形為基礎的視域計算演算法；這個演算法使用了特定的範圍角度來縮小處理範圍並使用射線測試函式減少投影計算量以提高執行效率。此演算法讓使用者可以更方便、更有效率的對地形執行視域計算；並提供視域計算做地理資訊系統的相關應用。

關鍵字

視域分析 ； 視域計算

並列摘要

Several important applications of geographic information systems (GIS) require visibility computation, such as, the line-of-sight communication, the optimal placement of a radial tower or a watchtower, finding the path with certain visibility properties (scenic or hidden paths) and so on. Thus, a better visibility computation algorithm makes the applications more efficient. The goal of our research is to study the visibility computation technique and implement the algorithm for several related applications.
In this study, we proposed an improved visibility computation algorithm which is based on the triangulated irregular networks. We use intersection test module instead of the general projection method to achieve the same results; moreover, we use specific angles to narrow the test range to improve performance. By the proposed methods, we can reduce the computation of the algorithm to obtain better performance.
The proposed algorithm is roughly divided into three parts: the spatial analyst, radial sort, and visibility computation. First, the spatial analyst performs the neighborhood and zone analysis for visibility computation. Second, the radial sort step decides the processing sequence. Finally, the visibility computation step calculates the visibility information.
The visibility information obtained form our visibility computation algorithm can conform to the properties of line-of-sight. Therefore, the visibility information can solve the line-of-sight computation problems on TINs for lots of applications.

並列關鍵字

visibility computation ； viewshed

參考文獻

[2]Bertrand, G., "On topological watersheds," Journal of Mathematical Imaging and Vision, vol.22, issue.2-3, pp.217-230, 2005.

[4]Chazelle, B. and L. J. Guibas, "Fractional cascading: I. A data structuring technique, " Algorithmica, vol.1, pp.133-162, 1986.

[5]Cole, R. and M. Sharir, "Visibility problems for polyhedral terrains," Journal of Symbolic Computation, vol.7, no.1, pp.11-30, 1989.

[7]D''evai, F., "Quadratic bounds for hidden-line elimination," in Proc. 2nd ACM Symposium on Computational Geometry, New York, 1986, pp.269-275.

[9]Edelsbrunner, H., L. J. Guibas, and M. Sharir, "The upper envelope of piecewise linear functions: algorithms and applications," Discrete and Computational Geometry, vol.4, pp.311-336, 1989.