A Quantitative Directional Relations Model Considering Topology and Distance

Full Text (PDF, 332KB), PP.18-24

Views: 0 Downloads: 0


Xuehua TANG 1,*

1. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan, China

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2010.02.03

Received: 13 Sep. 2010 / Revised: 13 Oct. 2010 / Accepted: 18 Nov. 2010 / Published: 8 Dec. 2010

Index Terms

Directional relations, coarse direction relations reference, directional topologic reference, directional coordinate


Original models for direction relations ignored the restriction of topology and distance relations to direction representation. To improve the representation of direction relations model by pondering about the influence of topology and distance relations on direction relations, we categorize direction reference frame into topological reference and coarse directions reference and present a new direction relations quantitative and statistics models based on the new direction reference frames. Instead of degree, this new model uses a coordinate-based quantitative method to describe direction relations for the distance restrain, while it reflects the constraints of topology by the direction reference frame and by the coordinate representation. It covers all intricacies imposed by different types of objects and has more sensitivity to the configuration of objects. Experiments have been carried out and the results indicate the excellent efficiency in view of directional description.

Cite This Paper

Xuehua TANG, "A Quantitative Directional Relations Model Considering Topology and Distance", IJIGSP, vol.2, no.2, pp.18-24, 2010. DOI: 10.5815/ijigsp.2010.02.03


[1]A. Frank. “Qualitative Spatial Reasoning: Cardinal Directions as an Example”, International Journal of Geographic Information Systems, 1996, 10 (3): 269 -290.

[2]D. Peuquet, C.X. Zhan, “An algorithm to determine the directional relationship between arbitrary-shape polygons in the plane”, Pattern Recognition, 1987, 20(1):65–74.

[3]A. Frank. “Qualitative spatial reasoning about distances and directions in geographic space”, Journal of Visual Language and Computing, 1992, 3:343–371.

[4]DENG Min, “Discussion on Statistical Model of Direction Relation Between Spatial Objects in GIS”, Geoinformatica, 2008,12:193–217.

[5]XIA Yu, ZHU Xinyan, LI Deren, QIN Kun,. Research on spatial directional relation description model, Science of Surveying and Mapping, 2007, 32(5), pp.94-97.

[6]Yan H W, “Research on Formal Description Model of Spatial Direction”, Acta Geodaetica et Cartographica Sinica,2003, 32(1):42-46

[7]J.F. Allen, “Maintaining knowledge about temporal intervals,” Communications of the ACM, 1983, Vol. 26(11):832–843.

[8]R. Billen, E. Clementini, “Introducing a reasoning system based on ternary projective relations in P.Fisher(Ed.)”, Developments in Spatial Data Handling, 2004,381–394.

[9]B. Bennett, “Logical representations for automated reasoning about spatial relations” , Ph.D thesis, School of Computer Studies, University of Leeds, 1997.

[10]S.K. Chang, Q.S. Shi, and C.W. Yan, “Iconic indexing by 2D-strings,” IEEE Transactions on Pattern.

[11]S.K. Chang and E. Jungert, Symbolic projection for image information retrieval and spatial reasoning, London: Academic, 1996.

[12]J. Chen, C. Li, Z. Li, and C. Gold, “A Voronoi-based 9-intersection model for spatial relations”, International Journal of Geographical Information Science, 2001, 15(3):201–220.

[13]S. Cicerone, P. Di Felice, “Cardinal directions between spatial objects: the pairwise-consistency problem”, Information Sciences, 2004, 164:165–188.

[14]C. Claramunt, M. Thériault, “Fuzzy semantics for directional relations between composite regions”, Information Sciences, 2004, 160:73–90.

[15]E. Clementini, P. Di Felice, and D. Hernández, “Qualitative representation of positional information”, Artificial Intelligence, 1997, 95(2):317–356.

[16]M. Egenhofer and R. Franzosa,. “Point-set topological spatial relationships,” International Journal of Geographical Information Systems, 1991, 5(2):161–174.

[17]R. Goyal, “Similarity assessment for cardinal directions between extended spatial objects”, Ph.D thesis, University of Maine, 2000.

[18]R. Haar, “Computational models of spatial relations”, Technical report: TR-478, MSC-72-03610, Computer Science, University of Maryland, 1976.

[19]D. Hernández, “Qualitative representation of spatial knowledge”, Lecture Notes in Computer Science, 804, Springer, 1994.

[20]Z.L. Li, R.L. Zhao, and J. Chen,. “A Voronoi-based spatial algebra for spatial relations”, Progress in Natural Science, 2002, 12(7):528–536.

[21]G. Ligozat, “Reasoning about cardinal directions,” Journal of Visual Languages and Computing, 1998, 9:23–44.

[22]A. Mukerjee and G.A. Joe. “Qualitative model for space”, Proceedings of the 8th National Conferenceon Artificial Intelligence, Boston, MA, 1990, pp.721–727.

[23]D. Papadias, “Relation-based representation of spatial knowledge,” Ph.D thesis, Department of Electricaland Computer Engineering, National Technical University of Athens, 1994.

[24]D. Papadias and M. Egenhofer. “Algorithms for hierarchical spatial reasoning,” GeoInformatica, 1997, 1(3):251–273.

[25]D. Pullar and M. Egenhofer, “Toward formal definitions of topological relations among spatial objects”, Proceedings of the 3rd International Symposium on Spatial Data Handling, Sydney, Australia, August, 1988.

[26]D.A. Randell, Z. Cui, and A. Cohn, “A spatial logic based on regions and connection”, Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning, Morgan Kaufmann, San Mateo, CA, 1992, pp. 165–176.

[27]J. Renz and B. Nebe, “On the complexity of qualitative spatial reasoning: A maximal tractable fragmentof the region connection calculus”, Artificial Intelligence, 1999, 108(1–2):69–123.

[28]R. Röhrig, “A theory for qualitative spatial reasoning based on order relations”, Proceedings of the 12th International Conference on Artificial Intelligence, 2: 1418–1423, 1994. 

[29]J. Sharma. “Integrated spatial reasoning in geographic information systems: Combining topology and direction,” Ph.D thesis, The Graduate School, University of Maine, 1996.

[30]A.P. Sistla, C. Yu, and R. Haddad. “Reasoning about spatial relationships in picture retrieval systems,” in Proceedings of VLDB-94, 570–581, 1994.

[31]S. Skiadopoulos and M. Koubarakis, “Composing cardinal directions relations”, Proceedings of the 7th International Symposium on Spatial and Temporal Databases (SSTD’01), Springer, Berlin, 2001,299–317.

[32]R.K. Goyal, “Similarity Assessment for Cardinal Directions Between Extended Spatial Objects”, Ph.D Thesis, the University of Maine, 2000.

[33]LIU Yu, GONG Yongxi, ZHANG Jing and GAO Yong, “Representation and Reasoning of Spatial Relations in Geographical Space”, Geography and Geo-Information Science, 2007, 23(5), pp.1-6.

[34]Yan H., Chu Y., Li Z and Guo R., “A quantitative description model for direction relations based on direction groups”, Geoinformatica, 2006, 10(2), pp. 177- 195.

[35]Spiros Skiadopoulos, Nikos Sarkas, Timos Sellis and Manolis Koubarakis, “A Family of Directional Relation Models for Extended Objects”, IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2007.19(8), pp.1116-1129. 

[36]Chang S K, etc. “Iconic Indexing by 2-D string”, IEEE Trans. Pattern Anal•Machine Intell•, 1987,(9) : 413-428.

[37]R.K. Goyal, Max J. Egenhofer, “Similarity of Cardinal Directions”, Proceedings of ACM SIGMOD International Conference on Management of Data, 1984, 8: 47-57.