An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane

摘要

The directional relationship between two polygons (e.g. left, above, beside, east, north) is an important spatial property and can also be used as a selection criterion for retrieving objects from a spatial database. If the database is large, this could help significantly in speeding search by reducing the size of the necessary search space. This paper builds upon past work to develop a model for determining the directional relationship in 2-D space between two simply-connected polygons of arbitrary shape, size and distance from each other. The model is based on visual interpretation and is data structure independent. The model is also stated in algorithmic terms, and is found to have a computational complexity of O(n), where n is the total number of vertices or cells used to represent the two polygons.