Nearest Neighbor Query Of Planar Polygon Based On Line Segment

Spatial database has been a hot research field in recent years. It has been applied on GIS, CAD/CAM, multimedia system and digital globe fields. As a concrete application of spatial database, nearest neighbor query of spatial data has attracted more and more attention in reality. At present, nearest neighbor query of spatial data has been mainly classified into nearest neighbor queries, reverse nearest neighbor queries, K nearest neighbor queries, constrained nearest neighbor queries, group nearest neighbor queries and closet pair queries.The granularity of these nearest neighbor query bases on points. The objects were abstracted as points, and then according to the formula of distances between point and point, the nearest point to the queried point was worked out. This thesis aims at nearest neighbor query of spatial data. But the granularity of nearest neighbor query is different from the ones mentioned above. In this paper, the querying granularity of the nearest neighbor query is line segment. Its purpose is to implement the function which is not capable in the nearest neighbor query of which the granularity is points. The main researching way of this paper is as follows: By abstracting object as polygon or line segment, we worked out the R_tree according to the Hilbert values of those line segments and used the technique of spatial index and the technique of branch bound; We filtered failing nodes and transformed the relation between polygon and polygon into the relation between line segment and line segment; By introducing the concept of affecting zone of line segment, we classified the position between line segment and line segment into nine instances according to different position relation. For each instance, by some rules this paper introduced, we obtained all of the possible nearest distances, and concluded the result based on the comparison of the distances.This innovation is that the query granularity is raised from one-dimensional points to two-dimensional line segments. Theory significance of this paper is that the nearest neighbor query of objects that can not be abstracted as points was achieved. Reality significance of this paper is that we have many practice applications, for example, nearest neighbor object on the two side of highway, nearest neighbor object on the two side of high voltage wire and nearest neighbor island to waterway, and so on.