Three-dimensional Obstacle Space Based On Convex Hull Model Visual Query Research

In recent years,visual query,as a special kind of query in obstacle space,has attracted many experts and scholars to do in-depth research in two-dimensional space and made some achievements,but the research of visual query in three-dimensional space is just emerging.In the three-dimensional space,the existing AABB model and OBB model are not applicable to the real three-dimensional space in which the shape of the space object is irregular and the space posture is completely free.To solve this problem,this paper proposes a visual query method for 3D obstacle space based on convex hull model.The main content includes the following aspects.Firstly,the representation model and index structure of 3D objects are presented.For three-dimensional space the visual query demands the query results more accurate and this kind of situation,can't use traditional AABB model is proposed using three dimensional convex hull model of space objects,and based on this model to optimize the traditional R tree,put forward the combination of three dimensional convex hull and R tree index structure,the index structure named C-rTree index,Make relevant definitions for it.On this basis,the overall structure design and implementation algorithm of the index structure are given.A query operation algorithm based on 3 D C-RTree index structure is proposed.Secondly,the visibility detection of 3D convex hull and visual K-nearest neighbor query are presented.In view of the irregular shape of 3D convex hull,it is not possible to use the traditional projection method like AABB,and it is not possible to calculate the projection Angle by projecting the horizontal plane and vertical plane respectively like OBB.In this paper,the definitions of "inquiry point-object visible body" and "joint obstacle" are proposed.The visibility of the convex hull model is tested by the method of "query pointobject visible body",collision detection of obstacles and line-plane geometric calculation.This paper introduces the definition of convex hull visual query and the convex hull collision detection method used,and gives the realization of visibility detection algorithm based on convex hull model,including the visibility detection under single obstacle and the visibility detection under joint obstacle.Based on this,a 3D visual k-nearest neighbor query algorithm based on convex shell model is proposed.Finally,the experimental system is built according to the research content,and the design description of the system is given and the functions of each part of the system are introduced.Other conditions such as different data scales,different data distributions and different node thresholds were set as experimental variables,and 3D C-RTree index structure and traditional R-Tree index structure were constructed respectively to compare the accuracy of the query.It is proved that the 3D C-RTree index proposed in this paper is more accurate than the traditional R-tree node query.Different data quantities and different K values were set as experimental variables to compare and analyze the visual query results of the spatial objects of the convex shell model.The comparative experiment proves the superiority of the visual k-nearest neighbor query algorithm based on convex hull.