An equal‐area triangulated partition method for parallel Xdraw viewshed analysis. (27th February 2019)

• Record Type: Journal Article
• Authors: Dou, Wanfeng; Li, Yanan; Wang, Yanli
• Is Part Of: Concurrency and computation. Volume 31:Number 17(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2019-02-27
• Subjects: equal‐area triangulated partition -- parallel computing -- terrain visibility analysis -- Xdraw viewshed algorithm; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5216
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: This paper presents an effective equal‐area triangulated partition method (EATP) for parallel viewshed computation based on Xdraw algorithm that is a viewshed analysis algorithm with lower overhead. Our approach is to first partition the target domain into eight 45° octants along a coordinate‐axis direction and diagonal line direction around a given observer. Each octant remains mutually independent on data dependency based on the principle of Xdraw algorithm. Then, each octant is repartitioned into equal‐area sub‐regions with the shape of the triangle according to the requirements of system platform such as the number of computing nodes or processors and the size of memory of each node. Our method is beneficial to group these triangle sub‐regions for determination of their dependent relationships during the computation of visibility and distribution of each triangle sub‐region to a suitable node. The unified expression of the sub‐regions is simple for implementation of parallel Xdraw viewshed algorithm. The experimental results are evaluated to demonstrate a distinct improvement in computation performance compared with other partition methods such as equal‐angle and simple equal‐area methods.