The Geometric Research Of Plane Line Segment Sets In Spatial Database

With the rapid development of computer technology, spatial database is widely used in areas of computer vision, image recognition, environmental protection, computational geometry, geographic information systems (GIS) and digital earth. The geometric problem of plane line segment sets is one of the important application value contents in spatial database.The geometric problems of plane line segment sets can be targeted to solve the cases which some space objects can be abstracted as line segments. In practical applications, many problems can be attributed to convex hull problems of plane line segment sets.In graphics and scientific visualization, it needs to solve the triangulation problem of plane line segment sets. The important parts of the triangulation algorithm of plane line segment sets are to reduce the complexity of the algorithm and form high-quality triangular meshes. The query problems of plane line segment sets are often met in near neighbor query.Effective index of plane line segments in nearest neighbor query of plane line segment sets can greatly accelerate the query speed.The studies of the following three aspects are made in this thesis:1. The convex hull problems of plane line segment sets. The characters of simple polygonal chain and line segment sets, which are different from point sets, are studied. A new algorithm for computing the convex hull of simple polygonal chain and a new algorithm for determining the convex hull of line segment sets are proposed.2. The triangulation problems of plane line segment sets. The triangulation algorithms for plane segment set in spatial database are analysed systematically. The advantages and disadvantages of various algorithms are summarized. Combined with the convex hull of line segment sets in the plane, a new algorithm for determining the triangulations problem of plane line segment sets and point sets is put forward.3. The near neighbor query problem of plane line segment sets. The advantages and disadvantages of R-tree, the R~+-tree, the R~*-tree, Quard-tree are researched, and the shortcommings of the indexing structures are corrected. A new spatial indexing structure, RP-tree, is presented. The indexing structure is applied for indexing a great mount of non-intersecting line segment sets. To do so can improve the efficiency of nearest neighbor query of line segment set. Based on RP-tree, a new algorithm for the nearest neighbor query of plane line segment set is put forward, whose time complexity is O (log_k n).