L1-Spatial Concepts L1 - Spatial Concepts NGEN06 &

L1-Spatial Concepts L1 - Spatial Concepts NGEN06 & TEK230: Algorithms in Geographical Information Systems by: Irene Rangel, updated 2015-11-02 by Sadegh Jamali 1 L1-Spatial Concepts Concept of Space Object model > set of objects (vector)

Field-based model -> set of locations with properties (raster or grid) How do we store geographic data (geometry)? 2 L1-Spatial Concepts Aim Understand the relationship between spatial queries and mathematical concepts. Know how topological relationships are defined in GIS. Get knowledge about the relationship between type of queries and suitable methods of storing geographic data.

3 L1-Spatial Concepts Content 1. 2. 3. 4. 5. 6. Spatial queries Set-based queries Topological queries

Graph-based queries Euclidean queries Storing relationships or deriving in real-time? 4 L1-Spatial Concepts Spatial Queries Set-based query: Is Uganda a country in Africa? Africa 5 L1-Spatial Concepts

Spatial Queries Topological queries Which countries are neighbours to Uganda? Africa Topological Relationships 6 L1-Spatial Concepts Spatial Queries Graph-based queries How long is the traveling distance from Uganda to

Egypt? Africa Relationships between elements distance between elements 7 L1-Spatial Concepts Spatial Queries Euclidean queries What is the area of Uganda?

8 L1-Spatial Concepts Do we always need coordinates to answer spatial queries? 9 L1-Spatial Concepts We are not always relying on coordinates (or the Euclidean space) in GIS; by storing set-based, topological and graph-based data explicitly (without using coordinates) we can answer many spatial queries without considering coordinates.

But how storing explicitly? 10 L1-Spatial Concepts Set-based queries Countries_in_africa ={Egypt, Uganda, ...} Z={..., -2, -1, 0 1 2, ...} R= the real numbers R2 = R x R E= {x=(x1,x2) | x R2 , 0 Logical Operators: OR AND NOT 12 L1-Spatial Concepts

Data structure to store set based data explicitely Is Uganda a country in Africa? Table: Countries_in_Africa Country Capital Uganda Kampala Egypt Cairo Nigeria

Lagos Etc. 13 L1-Spatial Concepts Topological queries Topology is derived from the Greek and means the science of position. Topological Space: A set and a number of subsets (which follow certain rules)

14 L1-Spatial Concepts Topological Relationships? Using a rubber sheet (where all points, lines and areas are drawn), topological relationships are the properties that remain between the points, lines and areas for all possible kinds of deformation of the rubber sheet (except tearing). <- Rubber sheet transformation Examples: Point is inside a polygon Two lines intersect Not a topological relationship: an object is close to another (spatial relationship) 15 L1-Spatial Concepts Topological transformation 1) There should be one-to-one correspondence between the elements in the original and transformed set (bijection). 2) Two points that are connected in the original set should also be connected in the transformed set. 16 L1-Spatial Concepts

Topological Relationships 17 L1-Spatial Concepts 4-intersection model It is defined using the boundary and the interior of objects. This terminology is defined for cells (2 dimensional, connected sets without holes - closed) in R2. A A

A Connected Not Connected 18 L1-Spatial Concepts 4-intersection model Definitions of boundary and interiors of connected objects (A) in R2 Boundary ( A ) Interior (Ao)

Point The empty set Point Line The end points The line apart from the end points Area The line(s) that

constitute the border of the area The area inside the border lines 19 L1-Spatial Concepts Definitions of topological relationships (using the 4-intersection model) A B A0 B0

A B0 A0 B Topological relationship A disjoint B

A meets B

A equals B A inside B

A coveredBy B B inside A

A covers B

A overlaps B = empty set = not empty set 20 L1-Spatial Concepts Definitions of topological relationships (using the 4-intersection model) A disjoint B

A inside B A contains B A meets B A equals B A coveredBy B A covers B A overlaps B 21

L1-Spatial Concepts Other models of topological relationships 9-intersection model (DE-9IM) The 4-intersection model is actually not that suitable for expressing topological relationships between line and/or point objects. DE-9IM was proposed to be an international standard by the International Standard Organization ISO19125-1. Defines topological relationships using interior, exterior and boundary of objects. 22 L1-Spatial Concepts

Data structures to store topological data explicitly Link-node structure: a data structure that consists of a set of data records (nodes) linked together and organized by references (links). 23 L1-Spatial Concepts Graph-based queries Also called network queries They consider distances Shortest (fastest) route is a typical example.

24 L1-Spatial Concepts Graph-based queries Traveling time between airports. The points (A, B, ... , H) are airports (i.e. elements in the set airports). The edges denote that there are flight routes between the airports. 25 L1-Spatial Concepts Graph-based and metric queries In a graph-based query there is no restriction on the distances between the elements in the set.

Metric query is a sub-set of a graph-based query that set constraints on the distances-> they must obey the rules of a metric. 26 L1-Spatial Concepts Metric query A metric (d) is a distance measure between two elements in a set. The metric has to obey the 3 following rules (where p,q, and r are elements in the set, d=metric): 1. d(p,q)>=0, d(p,q)=0 p=q 2. d(p,q)=d(q,p) (symmetry) 3. d(p,q)<=d(p,r)+d(r,q) (triangle inequality) 27 L1-Spatial Concepts Metric query There are an infinite number of metrics. Two of the most common metrics (in R2) in GIS are: 1) Euclidean distance: d ( p, q) ( x p - x q ) 2 ( y p - y q ) 2 2) Manhattan distance: d(p,q)= |xp- xq| + |yp- yq| 28 L1-Spatial Concepts Data structures to store graph-based data explicitly

Graphs can be stored as matrixes. Sparse graphs are normally stored in adjacency list (Sedgewick, 2002 ). 29 L1-Spatial Concepts Euclidean queries What is the distance between a building and a road? -> Require coordinates to be stored. 30 L1-Spatial Concepts

Storing relationships or deriving in real time? In some cases the relationships can be derived from stored coordinate data. Traveling distance (but not traveling time) Storing relationships explicitly: Advantages: It saves processing time Could enhance the quality of the answer Disadvantages: It takes more space in memory It entails redundancy (storing same information twice) 31 L1-Spatial Concepts

Storing relationships or deriving in real time? A few things you should consider before you decide what relationships should be stored explicitly: What type of queries will the database serve? How will the database be maintained? Will the database be connected to other databases? 32

Recently Viewed Presentations

  • ITGS Networks Terms: Connection types

    ITGS Networks Terms: Connection types

    Wi-Fi! A few important quotes: "Conforming to the 802.11a or 802.11b IEEE standards in the 2.4GHz frequency range" "A communication system that uses low-power microwave radio signals to connect laptop computers, PDAs, and web-enabled cell phones to the Internet"
  • Aligning learning and assessment - University of Western Sydney

    Aligning learning and assessment - University of Western Sydney

    Paul Parker, UWS Student Learning Unit ''But it's not really user friendly' Student perceptions of criteria & standards and exemplars Learning guides should include: 29(d) Annotated models of student essays or reports, or marking guides, to clarify expectations about what...
  • Numerical Methods and Programming

    Numerical Methods and Programming

    Numerical Methods and Programming P. B. Sunil Kumar Department of Physics IIT Mdras [email protected] Basic structure (1) C Programing for beginners (2) How accurate and precise are your numerical answers ?
  • 1-1 Nets

    1-1 Nets

    Nets and Drawings for Visualizing Geometry. Problem 1: How can you determine by looking at the net that surface E and surface F will be opposite one another in the cube? If the cube were turned one quarter-turn counterclockwise without...
  • Monday March 14th BEFORE THE SECOND BELL RINGS:

    Monday March 14th BEFORE THE SECOND BELL RINGS:

    (1) Last week, I visited a second-grade class to teach a short reading lesson.(2) Sitting all around me on the floor, the students listened as I read to them one version of The Three Little Pigs.(3) Their teacher had read...
  • Acute Coronary Syndrome: Patterns and Correlates of Household ...

    Acute Coronary Syndrome: Patterns and Correlates of Household ...

    SECONDHAND SMOKE: THE IMPORTANCE OF SMOKE-FREE ENVIRONMENTS Mini-Lecture 4 Module: Tobacco and Community Medicine and Public Health
  • Name of Conference

    Name of Conference

    Larry Chase. Casting a Wider Net. November 2, 2019. OUR CHALLENGE. ... Even after units chartered by the Church of Jesus Christ of Latter Day Saints close at the end of the year, we estimate every unit commissioner would need...
  • Understanding Knowledge Overview  Definitions  Cognition  Expert Knowledge  Human

    Understanding Knowledge Overview Definitions Cognition Expert Knowledge Human

    Knowledge is understanding of information based on its perceived importance Knowledge, not information, can lead to a competitive advantage in business Types of Knowledge Shallow (readily recalled) and deep (acquired through years of experience) Explicit (codified) and tacit (embedded in...