Executing convex polytope queries on nD point clouds

Liu, H.; Thompson, R.J.; van Oosterom, P.J.M.; Meijers, B.M.

doi:10.1016/j.jag.2021.102625

Executing convex polytope queries on nD point clouds

Title

Executing convex polytope queries on nD point clouds

Author

Liu, H. (TU Delft GIS Technologie)
Thompson, R.J. (TU Delft GIS Technologie)
van Oosterom, P.J.M. (TU Delft GIS Technologie)
Meijers, B.M. (TU Delft GIS Technologie)

Date

2021

Abstract

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.

Subject

CPLEX
nD point clouds
Perspective view selection
Polytope query
Spatial data structures

To reference this document use:

http://resolver.tudelft.nl/uuid:9385d43e-8448-42eb-af38-bb4b88394961

DOI

https://doi.org/10.1016/j.jag.2021.102625

ISSN

0303-2434

Source

International Journal of Applied Earth Observation and Geoinformation, 105

Part of collection

Institutional Repository