Modeling and computing ternary projective relations between regions

Clementini, Eliseo; Billen, Roland

doi:10.1109/TKDE.2006.102

Download

Article (Scientific journals)

Modeling and computing ternary projective relations between regions

Clementini, Eliseo; Billen, Roland

2006 • In IEEE Transactions on Knowledge and Data Engineering, 18 (6), p. 799-814

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/1679

DOI
10.1109/TKDE.2006.102

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Tkde-0190-0505-2.pdf

Publisher postprint (3.08 MB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

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.

Disciplines :

Earth sciences & physical geography
Computer science

Author, co-author :

Clementini, Eliseo; University of L'Aquila > Department of Electrical and Information Engineering

Billen, Roland ; Université de Liège - ULiège > Département de géographie > Unité de Géomatique - Topographie et géométrologie

Language :

English

Title :

Modeling and computing ternary projective relations between regions

Publication date :

June 2006

Journal title :

IEEE Transactions on Knowledge and Data Engineering

ISSN :

1041-4347

eISSN :

1558-2191

Publisher :

Ieee Computer Soc

Volume :

Issue :

Pages :

799-814

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 01 December 2008

Statistics

Number of views

182 (20 by ULiège)

Number of downloads

523 (18 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

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.
Vivid Solutions Inc., "JTS Topology Suite,"http://www. vividsolutions.com/jts/JTSHome.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.