A new algorithm based on Region Partitioning for Filtering candidate viewpoints of a multiple viewshed

ABSTRACT

Selecting the set of candidate viewpoints (CVs) is one of the most important procedures in multiple viewshed analysis. However, the quantity of CVs remains excessive even when only terrain feature points are selected. Here we propose the Region Partitioning for Filtering (RPF) algorithm, which uses a region partitioning method to filter CVs of a multiple viewshed. The region partitioning method is used to decompose an entire area into several regions. The quality of CVs can be evaluated by summarizing the viewshed area of each CV in each region. First, the RPF algorithm apportions each CV to a region wherein the CV has a larger viewshed than that in other regions. Then, CVs with relatively small viewshed areas are removed from their original regions or reassigned to another region in each iterative step. In this way, a set of high-quality CVs can be preserved, and the size of the preserved CVs can be controlled by the RPF algorithm. To evaluate the computational efficiency of the RPF algorithm, its performance was compared with simple random (SR), simulated annealing (SA), and ant colony optimization (ACO) algorithms. Experimental results indicate that the RPF algorithm provides more than a 20% improvement over the SR algorithm, and that, on average, the computation time of the RPF algorithm is 63% that of the ACO algorithm.

KEYWORDS:

• Multiple viewshed analysis
• viewpoint
• region partitioning
• RPF algorithm

Acknowledgments

The research was supported by the National Natural Science Foundation of China [grant number 41471316] and a project funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions-PAPD [grant number 164320H101]. The authors express their gratitude to the journal editor and the reviewers, whose thoughtful suggestions played a significant role in improving the quality of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The research was supported by the National Natural Science Foundation of China [grant number 41471316] and a project funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions-PAPD [grant number 164320H101].