A cell-based algorithm for evaluating directional distances in GIS

Abstract

Directional distance is commonly used in geographical information systems as a measure of openness. In previous works, the sweep line method and the interval tree method have been employed to evaluate the directional distances on vector maps. Both methods require rotating original maps and study points in every direction of interest. In this article, we propose a cell-based algorithm that pre-processes a map only once; that is, it subdivides the map into a group of uniform-sized cells and records each borderline of the map into the cells traversed by its corresponding line segment. Based on the pre-processing result, the neighbouring borderlines of a study point can be directly obtained through the neighbouring cells of the point, and the borderlines in a definite direction can be simply acquired through the cells traversed by the half line as well. As a result, the processing step does not need to enumerate all the borderlines of the map when determining whether a point is on a borderline or finding the nearest intersection between a half line and the borderlines. Furthermore, we implement the algorithm for determining fetch length in coastal environment. Once the pre-processing is done, the algorithm can work in a complex archipelago environment such as to calculate the fetch lengths in multiple directions, to determine the inclusion property of a point, and to deal with the singularity of a study point on a borderline.

Keywords:

• directional distance
• fetch length
• uniform subdivision
• point-in-polygon

Acknowledgements

The research was supported by Chinese 973 Program (2004CB719400), the National Science Foundations of China (60625202, 60533070) and Chinese 863 Program (2007AA040401). The second author was supported by the project sponsored by a Foundation for the Author of National Excellent Doctoral Dissertation of PR China (200342) and the Fok Ying Tung Education Foundation (111070).

We want to thank Mika MurtojÄrvi who kindly helped us by providing the source codes for quantifying distances from points to polygons. In addition, we would like to thank the reviewers for their helpful comments.