Fundamentals, implementations and experimental benchmarks of nD-polytype queries on point cloud data sets

Abstract

As an extension to 2D polygonal queries, the nD-polytope queries on point clouds also play a crucial rolein nD GIS applications such as the perspective view selection. This report rst denes the nD-polytopemathematically, and then develops an ecient nD-polytope querying solution by extending an index-organized table (IOT) approach. The solution integrates four novel intersection algorithms includingCPLEX, SWEEP, SPHERE and VERTEX, each of which can be used to realize the primary lteringfor polytope querying. The performance of these algorithms is then measured and compared using anrepresentative nD-simplex and an nD-prism query region, respectively. It turns out that SWEEP performsthe best over all, but it may degrade signicantly as dimensionality goes up. On the other hand, thelinear programming algorithm CPLEX although takes more time on intersection computation, performsmore stable. Besides, the experiments also reveal that the properties of a same geometry can changesignicantly across dierent dimensionality, and thus optimal strategies developed in 2D/3D may not beapplicable in high dimensional spaces.