Executing convex polytope queries on nD point clouds

Haicheng Liu

doi:10.1016/j.jag.2021.102625

2021-12-01

Haicheng Liu *

Peter van Oosterom

Martijn Meijers

DOI：10.1016/j.jag.2021.102625

原文链接

查看原文

摘要

En 中文

Efficient spatial queries are frequently needed to extract useful information from massive nD point clouds. Most previous studies focus on developing solutions for orthogonal window queries, while rarely considering the polytope query. The latter query, which includes the widely adopted polygonal query in 2D, also plays a critical role in many nD spatial applications such as the perspective view selection. Aiming for an nD solution, this paper first formulates a convex nD-polytope for querying. Then, the paper integrates three approximate geometric algorithms - SWEEP, SPHERE, VERTEX, and a linear programming method CPLEX, developing a solution based on an Index-Organized Table (IOT) approach. IOT is applied with space filling curve based clustering and advanced querying mechanism which recursively refines hypercubic nD spaces to approach the query geometry for primary filtering. Results from experiments based on both synthetic and real data have confirmed the superior performance of SWEEP. However, the algorithm may lag behind CPLEX due to pessimistic intersection computation in high dimensional spaces. In a real application, by properly transforming a perspective view selection into a polytope query, the solution achieves a sub-second querying performance using SWEEP. In another flood risk query, SWEEP also leads the others. In general, the robust and efficient solution can be immediately used to address different polytope queries, including those abstract ones whose constraints on combinations of different dimensions are formed into a polytope model. Besides, the knowledge of high dimensional computations acquired also provides significant guidance for handling more nD GIS issues.

Keyword:

nD point clouds

Polytope query

Spatial data structures

CPLEX

Perspective view selection