spatial databases; spatial queries; projective relations; geographic information systems
Abstract :
[en] Current spatial database systems offer limited querying capabilities beyond binary topological relations. This paper introduces a model for projective relations between regions to support other qualitative spatial queries. The relations are ternary because they are based on the collinearity invariant of three points under projective geometry. The model is built on a partition of the plane into separate zones that are obtained from projective properties of two reference objects: Then, by considering the empty/ nonempty intersections of a primary object with these zones, the model is able to distinguish between 34 different projective relations. Then, the paper proposes original algorithms for computing the relations under the assumption that regions of the plane are stored as vector polygons in a spatial database. These algorithms run in optimal O(n log n) time.
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
R. Billen and E. Clementini, "Introducing a Reasoning System Based on Ternary Projective Relations," Developments in Spatial Data Handling, Proc. 11th Int'l Symp. Spatial Data Handling, pp. 381-394, 2004.
R. Billen and E. Clementini, "A Model for Ternary Projective Relations between Regions," Proc. Ninth Int'l Conf. Extending DataBase Technology, pp. 310-328, 2004.
R. Billen and E. Clementini, "Semantics of Collinearity among Regions," Proc. First Int'l Workshop Semantic-Based Geographical Information Systems (SeBGIS '05), pp. 1066-1076, 2005.
E. Clementini and P. DiFelice, "Spatial Operators," ACM SIGMOD Record, vol. 29, pp. 31-38, 2000.
E. Clementini, P. DiFelice, and D. Hernández, "Qualitative Representation of Positional Information," Artificial Intelligence, vol. 95, pp. 317-356, 1997.
E. Clementini, P. DiFelice, and P. vanOosterom, "A Small Set of Formal Topological Relationships Suitable for End-User Interaction," Proc. Third Int'l Symp. Advances in Spatial Databases (SSD '93), pp. 277-295, 1993.
E. Clementini, J. Sharma, and M.J. Egenhofer, "Modelling Topological Spatial Relations: Strategies for Query Processing," Computers and Graphics, vol. 18, pp. 815-822, 1994.
H.S.M. Coxeter, Projective Geometry, second ed. Springer-Verlag, 1987.
Deegree: A Free Software Project by the GIS and Remote Sensing Unit of the Dept. of Geography, Univ. of Bonn, http://deegree.sourceforge.net/, 2003.
V. Dugat, P. Gambarotto, and Y. Larvor, "Qualitative Theory of Shape and Orientation," Proc. 16th Int'l Joint Conf. Artificial Intelligence (IJCAI '99), pp. 45-53, 1999.
M.J. Egenhofer, "Deriving the Composition of Binary Topological Relations," /. Visual Languages and Computing, vol. 5, pp. 133-149, 1994.
M.J. Egenhofer and R.D. Franzosa, "Point-Set Topological Spatial Relations," Int'l J. Geographical Information Systems, vol. 5, pp. 161-174, 1991.
C. Freksa, "Using Orientation Information for Qualitative Spatial Reasoning," Theories and Models of Spatio-Temporal Reasoning in Geographic Space, pp. 162-178, 1992.
K.-P. Gapp, "From Vision to Language: A Cognitive Approach to the Computation of Spatial Relations in 3D Space," Proc. First European Conf. Cognitive Science in Industry, pp. 339-357, 1994.
K.-P. Gapp, "Angle, Distance, Shape, and Their Relationship to Projective Relations," Proc. 17th Conf. Cognitive Science Soc., pp. 112-117, 1995.
R. Goyal and M.J. Egenhofer, "The Direction-Relation Matrix: A Representation of Direction Relations for Extended Spatial Objects," UCGIS Ann. Assembly and Summer Retreat, 1997.
D. Hernândez, Qualitative Representation of Spatial Knowledge. Springer-Verlag, 1994.
A. Isli, "Combining Cardinal Direction Relations and Other Orientation Relations in QSR," Proc. Eighth Int'l Symp. Artificial Intelligence and Math., Jan. 2004.
A. Isli and A.G. Cohn, "A New Approach to Cyclic Ordering of 2D Orientations Using Ternary Relation Algebras," Artificial Intelligence, vol. 122, pp. 137-187, 2000.
D. Kirkpatrick and J. Snoeyink, "Computing Common Tangents without a Separating Line," Proc. Workshop Algorithms and Data Structures, pp. 183-193, 1995.
F. Klein, "Verglecheinde Betrachtungen über Neuere Geometrischen Forschungen," Bull. of the New York Math. Soc., vol. 2, pp. 215-249, 1893.
C. Kray and A. Blocher, "Modeling the Basic Meanings of Path Relations," Proc. 16th Int'l Joint Conf. Artificial Intelligence (IJCAI-99), pp. 384-389, 1999.
L. Kulik, C. Eschenbach, C. Habel, and H.R. Schmidtke, "A Graded Approach to Directions between Extended Objects," Proc. Second Int'l Conf. Geographic Information Science, pp. 119-131, 2002.
L. Kulik and A. Klippel, "Reasoning about Cardinal Directions Using Grids as Qualitative Geographic Coordinates," Proc. Int'l Conf. Spatial Information Theory. Cognitive and Computational Foundations of Geographic Information Science (COSIT '99), pp. 205-220, 1999.
A. Melkman, "On-Line Construction of the Convex Hull of a Simple Polygon," Information Processing Letters, vol. 25, pp. 11-12, 1987.
R. Moratz and K. Fischer, "Cognitively Adequate Modelling of Spatial Reference in Human-Robot Interaction," Proc. 12th IEEE Int'l Conf. Tools with Artificial Intelligence (ICTAI '00), pp. 222-228, 2000.
OpenGIS Consortium, OpenGIS Simple Features Specification for SQL, 1998.
J. O'Rourke, Computational Geometry in C, second ed. Cambridge Univ. Press, 1998.
J. O'Rourke, C.-B. Chien, T. Olson, and T. Naddor, "A New Linear Algorithm for Intersecting Convex Polygons," Computer Graphics and Image Processing, vol. 19, pp. 384-391, 1982.
F. Preparata and S.J. Hong, "Convex Hulls of Finite Sets of Points in Two and Three Dimensions," Comm. ACM, vol. 20, pp. 87-93, 1977.
G. Retz-Schmidt, "Various Views on Spatial Prepositions," AI Magazine, vol. 9, pp. 95-105, 1988.
C. Schlieder, "Reasoning about Ordering," Proc. Int'l Conf. Spatial Information Theory: A Theoretical Basis for GIS (COSIT '95), pp. 341-349, 1995.
H.R. Schmidtke, "The House Is North of the River: Relative Localization of Extended Objects," Proc. Int'l Conf. Spatial Information Theory. Foundations of Geographic Information Science (COSIT '01), pp. 415-430, 2001.
A. Scivos and B. Nebel, "Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation," Proc. Int'l Conf. Spatial Information Theory. Foundations of Geographic Information Science (COSIT '01), pp. 431-446, 2001.
S. Skiadopoulos, C. Giannoukos, P. Vassiliadis, T. Sellis, and M. Koubarakis, "Computing and Handling Cardinal Direction Information," Proc. Ninth Int'l Conf. Extending DataBase Technology, pp. 329-347, 2004.
D. Sunday, "Fast Winding Number Inclusion of a Point in a Polygon," http://softsurfer.com/algorithm_archive.htm, 2004.
C. Vorwerg, G. Socher, T. Fuhr, G. Sagerer, and G. Rickheit, "Projective Relations for 3D Space: Computational Model, Application, and Psychological Evaluation," Proc. 14th Nat'l Conf. Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conf. (AAAI '97, IAAI '97), pp. 159-164, 1997.
D. Waller, J.M. Loomis, R.G. Golledge, and A.C. Beall, "Place Learning in Humans: the Role of Distance and Direction Information," Spatial Cognition and Computation, vol. 2, pp. 333-354, 2000.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
