A tile-based method for geodesic buffer generation in a virtual globe

ABSTRACT

Geometric buffers are important for spatial analysis in many applications of geographic information systems (GISs), such as environmental measurement and management, human health, urban planning, etc. Geometric buffer generation algorithms are well studied in the Euclidean space where the buffer distance is measured by Euclidean metrics; however, very few algorithms are available for generating geometric buffers on the terrain surface in a virtual globe where the buffer distance is measured by geodesic metrics. This paper proposes a tile-based method for geodesic buffer generation according to the characteristics of a virtual globe. It extends the vector tile model (VTM) to organize terrain and vector data, and the XYH algorithm is improved to build geodesic distance fields for terrain meshes. Based on the data organization and the improved XYH algorithm, a geodesic buffer is generated via three main steps: selecting and assembling tiles, updating geodesic distance fields and tracing the boundaries of buffer zones. This method is implemented with multi-scale terrain and vector data, and the experimental results show that it is valid and exact and can be applied in practical applications.

KEYWORDS:

• Virtual globe
• geodesic distance
• geometric buffer
• terrain mesh
• vector

Acknowledgements

This research was supported by the National Key R&D Program of China [grant number 2017YFB0503703], the National Natural Science Foundation of China [grant number 41171314], the Nature Science Foundation Innovation Group Project of Hubei Province, China [grant number 2016CFA003], and the LIESMARS Special Research Funding. In addition, comments from the anonymous reviewers and editors are appreciated.

Disclosure statement

No potential conflict of interest was reported by the authors.

Supplemental meterial

Supplemental data for this article can be accessed here

Window filtering theorems

Preliminaries: Assume that a triangle mesh is defined as , where represents vertices, represents triangle faces, and represents the oriented edges of . When a sequence of triangle faces is unfolded into a common plane, the geodesic path between two points is a straight line that passes through a sequence of vertices and edges. A window is a collection of points whose geodesic paths from their sources share the same vertex-edge sequence. It can be classified into three types:

(1) a pseudo-source window is actually a vertex , where is the geodesic distance from the point-source to.

(2) an interval window is an interval of an edge from a point-source, shown in Figure 1(a), where is ’s the last parent pseudo-source window, is the geodesic distance from the point-source to .

(3) a parallel-source window that is an interval of an edge from a line-source , shown in Figure 1(b), where is the shortest distance between and .

Theorem 1(Mitchell et al. 1987). A geodesic path between the source and destination cannot pass through vertices whose total angle is less than 2.

Theorem 2 (Figure 2(a)); (Chen and Han 1990, Xin et al. 2011). Let be any window (an interval window or a parallel-window) that covers the vertex on the oriented edge of , at most one of them can have two children which provides a shorter distance than other windows.

Theorem 3. (1) Let be an interval window on the oriented edge of . is the current shortest distance of .If or or , then is invalid that can’t provide a shortest sequence (Figure 2(b)); (Xin and Wang 2009, Xin et al. 2011).

(2) Let be an parallel-source window on the oriented edge of . is the current shortest distance of .If or or , then is invalid that can’t provide a shortest sequence (Figure 2(c)); (Xin and Wang 2009, Xin et al. 2011).

Additional information

Funding

This work was supported by the National Key R&D Program of China [grant number 2017YFB0503703]; the National Natural Science Foundation of China [grant number 41171314]; the Nature Science Foundation Innovation Group Project of Hubei Province, China [grant number 2016CFA003]; and the LIESMARS Special Research Funding.