Geoinformatics

Geodata is data with spacial reference to the earth (and technically not in reference to other planets). That spacial reference could be direct (with coordinate systems) or indirect (reference to a well-established spatial object, e.g. a city, Brandenburger Tor, etc.).

Examples are:

• Maps and plans

• surveing data (building ground plans, supply lines)

• remote sensing data (satellite images, radar data, earth gravity measurements)

• secondary products of remote sensing data (digital terrain models, 3D city models)

• navigational data

• sensor data (rain radar, water level)

A lot of data is geodata. Music would be an example of non-geodata. Or bank data.

A GIS (geographical information system) is a computer-based system for

• input and update

• management and modelling (putting the data in tables via UML (unified modeling language))

• simulation and analyzation (buffer analysis, flowdirection analysis…)

• presentation and output

of geodata (functional components).

GIS does not equal the GIS software (ArcGIS, QGIS).

The structural components of a GIS are:

• hardware (PC, storage)

• software (e.g. ArcGIS, QGIS)

• data (the most valuable + longest life span!)

• user

A GIS links thematic information with geometric data.

• Land information systems (LIS)

  • system for legal foundation and documentation, e.g. cadastral map, city base maps

• Network Information Systems (NIS)

  • system for mapping operating resources, such as gas, water, energy, telecommunication

• Spatial Information Systems (SIS)

  • tool for planning and development, e.g. regional land use plan

• Environmental Information Systems (EIS)

  • environmental impact assessment

• Application Specialized Information Systems (AIS)

  • tool for navigation, transport managment

In a GIS, abstraction is required to model the real world. Our model represents the real world in a specific way, whatever the application is. For example, if we want to know more about the forests in our area, we would map the forests and not necessarily all power supply lines, even if they’re also there.

So, in order to model the real world, the application and the phenomena that needs modeling in order to fulfill that appllication must be chosen.

Then, the spatial data model must be chosen (raster/vector) to represent the data in a conceptual model.

Goinformatics is the science that “deals with” geodata. It is a bridge between computer sciences and geo sciences.

• External view: How the GIS is presented to the user (interface, system environment, etc.)

• Conceptual view: Thematic, geometric and topological modelling of a section of the real world

• Logical view: Representation of the models in data structures

• Internal view: Physical data storage and management

• Discrete objects: well-defined objects (points, lines, or polygones), “can be counted”, are usually instances of some category (e.g. trees, buildings, …) represented in vector data, can usually be described by attributes

• Continuous fields: data has no boundaries and “overlaps” the surface entirely, where every point is measurale and has a different value (e.g. temperature, air pressure, precipitation, terrain, soil types). Variations can be smooth or sudden; can also be defined along lines (traffic on a road, pollution in a river). There are different kinds of continuous fields:

  • scalar fields (only one variable)

  • vector fields (two or more variables; wind strength and direction!)

• the world is dynamic and changes eventually - how do we represent change over time? (Areas might change to points if forest is cut down or changes naturally)

• how to model different phenomena - i.e. roads as polygons or lines? -> depends on the context/appilcation; but many real-world features do not fit into the avaiable categories (points, lines, polygons)

• scale (small-scale: roads as lines. bigger scale: roads as polygons. But at what scale does a “city area” become different buildings (represented as individual polygons)?

• thematic modeling (identify and group similar features with the same properties (i.e. all roads are one entity, all buildings etc.)) -> in the field of GIS, typically grouping by thematic layer principle or object class principle

• geometric modeling (putting features into a specific geometry, i.e. vector or raster)

• topological modeling

Both are methods used in thematic modeling, so grouping similar features together in a specific way, either by

1) thematic layer principle: each theme is modeled in its own layer (i.e. trees in one layer, houses in one layer, streets in one layer) and the geographical information system consists of a number of layers that can be activated/deactivated; to then solve a specific problem, layers can be selected, combined and analyzed together (overlays, buffer, intersecting etc.). That principle is not very flexible as features HAVE to fit in the definition of the layer

2) (hierarchical) object class principle: comparable with object-oriented programming; world consists of objects that are instances of classes (grouping by classes) -> classes can be hierachically organized (+ have relations to other classes), subclasses inherit properties of parent class -> more flexible than thematic layer principle

• Entity-Relationship-Model (ER)

• Nijsen Information Analysis Method (NIAM)

• Object Modeling Technique (OMT)

• Unified Modeling Language (UML)

A Coordinate Reference System (CRS) is necessary to relate the coordinates of an object to the physical model of the real world.

Origin and axes orientation differ between mathematical and geodetic coordinate systems!

There are 2D- and 3D coordinate systems.

A geographic 3D coordinate system looks like this:

Points with equal latitude form a line called parallel, points of the same longitude form a meridian line.

There are “concentional” geographic reference systems, such as WGS84, and projected coordinate systems, such as UTM or Gauss-Krüger.

Projected coordinate systems project the earth models’ surface onto a flat map using a cylinder, a cone or a plane.

• equal area projection (sinosoidal projection)

• conformal projection (mercator projection)

A point set consists of a lot of points. They can be inside the point set (interior), meaning the points on the neighborhood of a point are also inside the point set.

Or they can be on the boundary of a point set, meaning the neighboring points are not completely inside the point set.

Or they can be both, which is the closure of a point set.

Everything not inside the closure is the exterior of a point set.

• Operations compute from one or several geo data layers a new layer

• model typically used for raster data

The operations:

• local: combine values at the same location from one or many layers (+, -, /, sin, boolean)

• focal: value of a raster cell is determined by combining values from the (defined) local neighborhood (e.g. mean value, minimum, flow accumulation)

• zonal: Summarize data values in some way that fall within given zones (mean values in a specific zone)

zonal:

A raster model with more resolution is not always more accurate, just “more defined”. For different purposes, the resolution may have to be higher or is fine when lower.

class x:

def __init_ (self, y, z):

self.y = y

self.z = z

Geopandas is an open-source python library designed to work with geospatial data. It’s based on the Pandas library and uses the DataFrame as well, just with an extra column for the geometry.

Functions are for example:

• spatial joins

• coordinate transformations

• geometric manipulations such as buffers, centroids…

• plotting geospatial data

import library

df.plot() OR

df.explore() <- shows dataframe on a global Earth’s map

mask = berlin_district[“inhabitants”] <= 1000

berlindistrictselected = berlin_district.loc[mask]

geodataframe.sort_values(by=’hello’, ascending=True)

1. Geocentric ellipsoid: WGS84, is determined by satellite orbital data and is considered more accurate for fitting the entire surface of the earth than for a specific region. the polar axis is defined by the rotational axis of the earth, the center of the ellipsoid is the center of the mass.

2. Regional ellipsoid: good for regions & not for the whole earth. Are in general not geocentric but parallel to the rotational axis. Example: Krassowski ellipsoid (for Eurasia, used in the eastern block).

3. classical ellipsoid: neither geocentric nor parallel to the rotational axis. Defined by local measurements. Example: Bessel ellipsoid (reference ellipsoid for europe from 1841).

A datum describes the position and orientation of a conventional reference system to a global geocentric system, it is a reference point or surface against which position measurements are made, it‘s a set of data which contains:

• the position and

• the dimension of the reference ellipsoid with respect to the Geoid.

shapely is a python library dedicated to the manipulation of geometric forms, such as points (Point or MultiPoint), lines (LineString or MultiLineString), and polygons (Polygon or Multipolygon) as well as the collections of those.

shapely.within(line,polygon) -> is line within polygon? OR

shapely.contains(polygon,line) -> does polygion contain line?

1. crosses: shapely.crosses(line1,line2) -> do line1 and line2 cross each other?

2. contains: shapely.contains(polygon, line) -> does polygon contain line?

3. within: shapely.within(line1, polygon -> is line1 within polygon?

4. intersection: shapely.intersection(polygon1, polygon2) -> intersection between polygon1 and polygon2 (everything that is there in both polygons)

5. union: shapely.union(polygon1, polygon2) -> union between polygon1 and polygon2

6. difference: shapely.difference(polygon1, polygon2) -> polygon1 - polygon2

For Raster data, the basic building block is the individual cell, while the point itself (coordinate pair) is the basic building block in vector data.

a) Raster data: the shape is described by a group of cells

b) Vector data: the shape is described by coordinates (lines & areas: a series of connected points who all consist of coordinate pairs)

Raster data is widely used for continuos fields, as the value of each cell represents a specific value (e.g. temperature, precipitation etc.).

That is not possible for vector data. If we want to display continuous fields in vector data, we can use isolines in which every line represents a specific value (often used for elevation data)

with the dissolve() function (example: berlin_districts.dissole(by=”district")

with the geopandas library, you can call the function set_geometry() on a geodataframe and put the row you want to base the geometry on in the brackets.

• Connectivity (links between spacial objects, for example line features that meet at common endpoints or street networks)

• Adjacency (information about the direct neighbors of spacial objects, for example area fatures that share common boundaries)

• Containment (information about the overlap between spacial objects, for example features that occupy the same space)

Topological data structures enable the explicit modelling of topological relations between spacial objects.

• reduces data storage by storing less boundaries because they are shared by neighbors

• prevents inconsistencies in the geometric modeling due to closing gaps when editing or digitizing data

• allows analysis on topological relations of connectivity, adjacency and containment (shorttest paths, minimum spanning trees etc.)

• simplifies the managment of tesselations

A 2-Manifold describes the concept of each point of the surface being surrounded by a 2-dimensional region - except for the points on the boundary, of course. The 2-dimensiojnal region belongs to the surface as well, like in point set modeling.

Not all point sets can be implemented as 2-manifold surfaces - for example objects who touch each other at a single point or line segment like this:

These are special cases where the object is split into several parts.

By their bounding surface(s). The boundary consists of several faces that arer “glued together”. The solid is then either located within and on the boundary (closed set) or only within the boundary (open set).

1. face

2. edge

3. vertex/node

This is called a polyhedron. Due to every line segment being a straight line, the data structure is reduced.

The simplest case: Faces are represented as polygons (sequence of coordinate triplets - the corner points!) -> the solid is a collection between those -> the relations between the polygons is not stored -> high redundancy of (corner) point coordinates -> often used in GIS

In this case above, due to not storing the relations between the faces, there is no topological data structure. The geometries are given by a sequence of points (coordinates).

This is called a polygon based boundary model.

the geometries are given by a sequence of points (coordinates). therefore, a lot of points are stored in several geometries (redundancy) which consists in a higher storage cost and possible inaccuracies in topological relations (gaps/overlaps, especially when changing the geometry without wanting to change the topology).

1. Polygon Based Boundary Model (no topological data structure)

2. 3D Vertex Based Boundary Model

3. Edge based Boundary Model

Vertices are stored as independent topological entities into the data structure. The vertices are associated with coordinates and polygons are then defined by a sequence of vertices.

The verices are listed in a specfic order, e.g. clockwise, which is good for many algorithms.

Firstly, the vertices are stored seperately like in the 3D vertex model. Then, the edges are stored seperately as well while being desribed with a sequence of vertices. the faces are then not desribed by vertices, but by the edges.

For curved edges, edges can be linked with control points that define the curved geometry.

Edges are not always directed in a clockwise direction (if faces share edges, that is just not always possible.) Therefore, in the winged edge topological data structure, the direction is stored as well. For every edge, the “neighboring” edge and their direction is stored. That results in every edge being linked, so that only the start edge must be stored because the edges are linked and the direction is known.

Two dataframes can be merged with the merge() function on a column that is the same in both dataframes. This column must be defined in the function.

This is a possible function: schools_district = schools.merge(sub_districts,on="sub_district")

Dataframes can also be spatially merged (spatial join) with the sjoin()-function.

The 6 arguments of the funtion are:

• left_df : the left geodataframe.

• right_df : the right geodataframe.

• how : the rule to join the geodataframes (left, right, inner).

• predicate : spatial predicate (intersects, contains, within, touches, crosses, overlaps).

• lsuffix : the suffix to apply to overlapping column names of the left geodataframe.

• rsuffix : the suffix to apply to overlapping column names of the right geodataframe.

sjoin_nearest()-function joins two dataframes according to how close they are to one another. with the max_distance-argument, the maximal distance can be determined.

The overlay()-function has several types: intersection, union, identity, difference

• Identity: Includes the area of the input polygons and the areas of the overlay polygons that lie within them. Attribute values are taken from input and overlay polygons

• Erase: Includes the part of the input polygons that is not in the area of the overlay polygons. Attribute values are taken over from the input polygon

• Union: Includes the union of input and overlay polygons. Attribute values are taken over from the input polygon

• Intersect: Includes parts of the input and overlay polygons that exist in both layers.

A network is a collection of interconnecting lines along which there is a flow of data, objects, or materials. They also include topological information (vertices/nodes and edges).

Raster models are not a good choice for this.

Examples: Berlin underground network, street networks

• Seven Bridges of Königsberg (walk trough city and cross each bridge exactly once)

• the house of Saint Nick

• Dog Walking Problem (n dogs, m kids (m >_ n), is there for every dog a candidate for walking? -> solution: vertex-disjoint edge set E with size n

• Map Coloring Problem (neighboring regions can not have the same colour!)

• Chinese Postman problem (deliver mail following the shortest path -> solved via finding an eularian path!)

• collection of vertices

• collection of edges that consist of pairs of vertices

An eularian path is a path that uses each edge exactly once, while a hamiltonian path is a path that uses each vertex exactly once.

1. traversable or semi-eularian

2. Eularian or unicursal

3. traceable

4. planar

No, because there is no path that connects both of them. They in itself are probably also not connected because of some islands that may or may not have street access.

It needs to be connected and the degree of all vertices is even except for the start & end vertex for an eularian path (degree: numvber of edges that are incident to the vertex).

For an eularian cycle, the graph must be connected, planar and the degree of all edges must be even, no exceptions.

There is no efficient algorithm known that determines if a graph contains a Hamiltonian path or cycle, yo can just try out all possibilities until you find one.

Via using 2D Lists - this is not suitable for big or complex raster data, though.

The lists look like this:

The list consists of several lists (each nlist represents a row! and the elements in the lists represent a cell)

For visualizing raster data, the matplotlib library is useful, especiall the function imshow/(), which visualizes 2D arrays (like raster data) in an image.

Another way of working with raster data is using the rasterio library, which can be used to read and write raster data. For example, with rasterio.open(), a raster file can be read using a dataset reader. Also, the CRS of a raster file can be determined.

import rasterio

from rasterio.crs import CRS

test = rasterio.open(‘Data/RSMS_17_2020_01.asc’, mode='r+')

crs25832 = CRS.from_epsg(25832)

test.crs = crs25832

test.close()

DEM (digital elevation model): contain elevation information, often represented as a raster

DTM (digital terrain model): subset of DEMs containing height information only for the bare ground

DSM (digital surface model): subset of DEMs containing height information including all structures like buildings, trees etc

nDSM (normalized digital surface model): contains relative height information for all structures like buildings, trees etc and can be obtained by subtracting the DTM from the DSM (The nDSM can be obtained as nDSM = DSM - DTM)

Vertex a is a predecessor of b if e = (a, b) ∈ E

Vertex a is a successor of b if e = (b, a) ∈ E

5: 5 is a predecessor of 2

2: 2 has 2 predecessors (1,5) and one sucessor (3)

1: 1 has one predecessor (3) and two sucessors (2,4)

4: 4 has one sucessor (3) and one predecessor (1)

3: 3 has two predecessors (2,4) and one sucessor (1)

Matrix:

List:

For weighted graphs, the weight is also stored in the entry of the adjacent vertex (as a pair)

incidence matrix:

The n × m incidence matrix represents the relationships between n vertices and m edges for a graph. Directed edges are depicted by using a - sign in front of incoming edges (predecessors).

• matrix: n², while n is the number of vertices

• list: equal to the number of edges the vertex is incident to

One can

1. use an edge list, where the entire edge list must be looked through

2. use an adjacency matrix if the graph is undirected (if directed, the matrix only shows the sucessors)

3. use the adjacency list and search through all lists (if directed) or through the entries for x or y

1. Depth first search: recursive algorithm (calls itself again and again) which always marks the current vertex as visited and then looks at the neighbors of that vertex, chose one neighbor, mark the parent and repeat

2. Breadth first search: iterative algorithm (solves a problem step-wise by repeating a process) that uses a queue to determine which vertex is looked at next

A recursive algorithm solves a problem by repeatetly calling itself, while an iterative algorithm solves a problem step-wise by repeating a certain process.

An example for a recursive algorithm is depth first search, while the breadth first search algorithm is an example for an iterative algorithm.

Depth first search:

Breadth first search:

The breadth first search provides the shortest path from the root vertex of the spanning tree to all other vertices of the graph, where the weights of all edges are assumed to be the same

A weighted graph associates a „cost value“ (weight) with every edge in the graph. An unweighted graph does not have that. In most cases, the weight on the edges is the set of positive rational or integer numbers (if they are negative, we might get some problems, for example in incidence lists, where we set a - in front of edges who are predecessors to the vertex).

The weight of a path is the sum of the weights of the edges that belong to the path.

• single-pair (shortest path from one vertex to another vertex)

• single-source (shortest path from one vertex to all other vertices; what we learned about!)

• single-destination (shortest path from all vertices to one destination vertices; for undirected graphs, this is the same as the single-source-problem; for directed graphs, the edges need to be reversed)

• all-pairs (shortest path between all pairs of vertices)

First, set the distance of the start vertex to 0 and all other vertices to ∞ and mark all vertices as not visited - this is the initialization.

The current vertex is the vertex with the shortest distance. Then, every neighbor of the current vertex is looked at and the distances are updated, if the new distance is shorter than the previous one. Then, the current vertex is marked as visited.

This is repeated until the destination vertex (single-pair-problem) or all other vertices (single-source-problem) have been visited.

This is an iterative algorithm, surch as the breadth first search.

C)

No.

The graph must bean undirected, weighted graph.

First, create a forest with no edges from the vertcies of said graph.

Put the edges of the graph as a set/queue Q (a priority queue can be used).

While Q is not empty, remove the edge witht the lowest weight from Q - if the edge connects two different trees, them add it to the forest so that two trees are joined together. Otherwise, discard the edge.

Repeat until Q is empty.

For graphs that are not connected, the algorithm finds the minimal spanning forest.

The graph must be undirected and weighted and not connected (several connected components), so that not a minimum spanning tree but a minimum spanning forest is found.

graph_tool

graph = gt.Graph(directed=False)

Then add the vertices like this:

vx = graph.add_vertex(len(vertices_gpd))

The vertex without predecessors is called the Root/parent of the tree. All other vertices have exactly one predecessor. The leaves are the vertices that have no sucessors/children. Thwe othwer vertices which are neither root or leaves are called interior vertices. As the order of the vertex, the number of successors of the vertex is desribed. the order of a tree is the largest order of a vertex occurring in a tree.

• Complete tree: every vertex has either 0 or k successor vertices → k is then the order of all interior vertices and of the tree itself. This treee is therefore complete.

• Binary tree: all vertices have order <= 2 (k = 2) (the tree is binary! Because the order of the vertices is <= 2 and the order of the tree is 2.)

Height of the tree: the height of the root - 2 in this case

Depth of vertex 4: number of edges along the path from root to vertex v - 0 in this case

Depth of vertex 0: number of edges along the path from root to vertex v - 2 in this case

Height of the vertex 16: number of edges along the longest path from vertex v to a leaf - so 1 in this case

Level of the vertex 32: the height of the tree minus the depth of that vertex - height of tree = 2, depth of the vertex = 2 so level = 2 - 2 = 0

Due to their maximum logarithmic height, the search time in a binary search tree is O(log n) (where n is the number of elements stored in the search tree)

• AVL-Tree (Binary tree)

• 2-3 Tree (no Binary tree)

• B-Tree (no Binary tree)

Especially when considering a large KD-tree, a lot of regions can be left out when searching for points. This means that there will be a lot less searching than if the point set was not divided by a KD-tree.