Location Aware Apps — Geographic Information

Smartphones and other devices with location tracking capability have enabled a number of use cases in everyday life. E.g.:

1. Navigation services while travelling by various modes of transport
2. On-demand services such as cabs, delivery and home services
3. Health and fitness apps that track activity patterns
4. Location based marketing services
5. Augmented reality and gaming apps
6. Indoor asset tracking
7. Indoor proximity engagement

Location aware apps that run on these devices build on a number of underlying technologies. This is a series of articles that provide an overview of the various technologies that are brought together to deliver these use cases.

1. Location
2. Connectivity
3. Geographic Information

Geographic Information Systems

Geographic Information Systems (GIS) are information systems that are concerned with the creation, storage, analysis and presentation of geographic data. Google Maps has become the most popular and readily available GIS platform. This makes it the preferred starting point for any Shared Mobility solution. However, for improved geoanalytics, additional GIS capabilities typically need to be built in-house.

Datum

A geographical point is defined by its latitude, longitude and elevation in reference to a geodetic system. Both Google Maps and the GPS system are based on the World Geodetic System (WGS) 84 datum. The WGS standardizes the following measures for geographic information:

• Geographic coordinate system — centered at the Earth’s center of mass. The Prime Meridian is designated as 0° Longitude, and the Equator is designated as 0° Latitude.
• Geodetic datum — the mathematical ellipsoid model representing the Earth’s shape used as the reference frame for measurements. The geodetic latitude refers to the angle between the equatorial plane and the normal to the surface at the point. The geodetic longitude refers to the angle between the Prime Meridian and the meridian at that point. The height of the point with respect to the surface of the ellipsoid is referred to as the geodetic height. The standalone terms latitude and longitude typically refer to these definitions. The term geographic latitude is also used sometimes. The term geocentric latitude however measures the angle with respect to a line drawn to the center instead of using the normal.
• Gravitational equipotential surface — also referred to as the geoid, it defines the mean sea level. The elevation, also referred to as the orthometric height, is the height with respect to the geoid.

Projection

GIS data is built on underlying cartographic information that describes the 3-dimensional geographic features of a surface. The database is built using approaches like surveying, and remote-sensing based on techniques from photogrammetry (geographic measurements from photographs) and geodesy (shape and size of Earth for geographic information). A map is used to visualize this 3-dimensional cartographic information using a projection technique such as the Mercator (cylindrical) or the Lambert (conical) projection. The map may also present additional GIS data as overlaid layers e.g. terrain information as a layer of contour lines. There are numerous types of maps based on the information they show, and the purpose they serve. E.g. Topographic maps depict ground relief in detail and are often used for military planning.

Google Maps and most other electronic map providers use a Spherical Normal (equatorial) variant of the Mercator projection for its map images — this projection preserves angles so that e.g. when zoomed-in, cross-roads are shown correctly at right angles.

Maps

The different layers of electronic maps can be rendered as a raster or as a vector. Raster maps are a 2-dimensional renderings no different from a printed map, with limited zooming. Vector maps are geometric descriptions that can be rendered at any zoom level. Vectors can be rendered as points, lines/polylines (connected points) or polygons (shapes). These geometries can be used to represent features such as points-of-interest, road geometry, and area perimeters respectively. Vector based rendering improves the fidelity for both zooming-in and zooming-out. When zooming-in, the vectors can be re-rendered with more detail. When zooming-out features can be clustered using an algorithm like geohashing.

Web mapping is the process of creating and rendering electronic maps over the web. A number of companies offer Web GIS as a cloud based service that provides APIs for custom web mapping. This includes ArcGIS, Mapbox and QGIS. These systems uses multiples sources to gather and maintain their data. E.g. Google Maps uses the following:

• User Updates — Google provides various mechanisms for users to contribute improvements
• Local Guides — This is a points based voluntary program to encourage users to contribute improvements.
• Android Location Services — The location service on mobile phones is used to crowdsource road and traffic information.
• Content Partners — Organizations can contribute their own data. Organizations can also share indoor maps and floor plans. Transit providers can also share routes and timings. (Apple Maps also allows map contributions).
• Street View — Google drives their own vehicles to create maps using imagery and GPS.
• Imagery — Google Earth and Google Maps stitch together images from various aerial and satellite imagery sources to create photographic overlays.

Google Maps was initially structured as raster tiles organized in a quad-tree scheme. In this scheme, each tile is defined as a 256x256 pixel raster. Zoom level ‘0’ is the level at which the entire world is covered by a single tile. Each level of zoom from there doubles the resolution in both dimensions so that the single tile is replaced by 4 tiles. So for 20 zoom levels, 360 billion tiles will be needed. With this scheme, 22 levels are sufficient for practical purposes. With Google Maps 5.0 released in 2010, raster tiles were replaced with vector tiles. Vector tiles reduce the amount of data that needs to be downloaded, and enables dynamic rendering for improved interactivity, layering, and offline operation. OpenStreetMaps (OSM) and other mapping services also use a tiled mapping approach — OSM terms such maps as ‘slippy maps’.

Compared to outdoor maps, indoor maps can be more complex. The data collection is more effortful as the methods described above cannot be used indoors, and needs to be updated more frequently. Indoor maps are typically rendered as vector maps. The data is more dense, and requires more layers to provide greater control to users. In addition, there needs to be a way to identify and navigate the multiple levels in a multi-story building.

Geodata

Geographical data is any data that is associated with a geographic location. Such data may be stored in static files, or in indexed databases. A few of the common file formats are:

• GeoJSON — Used to describe simple geographical features (points, lines, polygons), along with associated attributes. The structure is based on JSON, and particularly suitable for web communication.
• Keyhole Markup Language (KML) — Used to describe geographic annotation and visualization information that can be rendered by mapping applications. The structure is based on XML, and is typically distributed as zipped KMZ files.
• Digital Raster Graphic (DRG) and Digital Line Graph (DLG) — Used by the US Geological Survey to store raster maps and vector maps respectively.
• Shapefile — A vector storage format defined by ESRI specifying the location, shape and attributes of geographic features. It is stored as a zip file containing a .shp file specifying the shapes; a .shx file specifying a shape index; a .dbf specifying feature attributes in a columnar format; a .prj file specifying the coordinate system and projection information; and other optional fies
• GeoTIFF — A metadata standard that allows georeferencing information to be embedded in a TIFF file.

The Geospatial Data Abstraction Layer (GDAL) is an open source library that can be used to read and write most of these raster and vector data formats.

Spatial databases are used when geographical data needs to be searched and queried. These databases can be used to store simple geometric points, lines and polygons, or more complex structures such as point clouds (3D object scan) or topological coverage (spatial relationships such as continuity and connectivity). Along with simple search queries, the databases may also support complex operations such as spatial measurements and geometry construction.

A number of algorithms are available to index spatial data such as:

• Geohashing — Hierarchically partition space in a regular grid pattern. With this approach, as the hash value grows in length, the precision of the location increases. A powerful example of this is Uber’s H3 library that implement a hexagonal hierarchical spatial index.
• R-tree — This method creates a balanced tree of rectangles, and is the preferred method for indexing spatial data. Each object is added to the minimum bounding rectangle that results in the smallest increase in size.
• kd-tree — The k-dimensional tree is a binary tree that partitions k-dimensional space in two at every level.

A number of databases implement support for spatial data, large and small, including:

• ESRI Geodatabase — The ESRI ArcGIS support three different types of spatial databases or ‘geodatabases’ — the file geodatabase (storage in a .gdb file), personal geodatabase (storage in a Microsoft Access database), and the ArcSDE geodatabase (interface with a database like PostgreSQL or Oracle).
• Couchbase — Supports geospatial queries using ‘spatial views’. This is an incremental MapReduce view that creates an R-tree to make such queries faster.
• MongoDB — Mongo DB supports 2d Indexes and 2dsphere Indexes to support geospatial queries.
• PostgreSQL — The PostGIS extension adds support for geographic objects and geospatial queries.

A number of companies and groups maintain repositories of global geodata:

• Google Maps is the most ubiquitous and easy to integrate source of geodata.
• OpenStreetMap (OSM) is an open-source geodata repository available across the globe. OSM data also powers other services like Mapbox.
• HERE Maps is largely owned by a consortium of German automotive companies and provides geodata for automotive and other segments.
• TomTom provides navigation devices and map data based on its geodata. TomTom has also been the source of data for Apple Maps.

Visualization

Location aware apps are often used to support spatial decision making by employing various techniques for visualization and manipulation.

Some of the default components of map visualization are:

• View Position — A given map can be ‘viewed’ from different positions for different perspectives. The parameters that define the ‘view’ are the centre of view, the zoom level, the tilt angle, and the bearing. Changing the view position is used to reveal different information about a region on the map.

Each of the parameters can be independently manipulated:

• Pan using a one-finger drag gesture
• Zoom using a two-finger pinch gesture
• Tilt using a two-finger vertical drag gesture
• Bearing using a two-finger twist gesture

• Location Marker — A ‘pin’ is drawn on a map to identify a specific location or a point of interest (POI). The standard pin used by Google Maps is the red-color ‘inverted tear-drop’ icon with a black center and a soft shadow. This is implemented as a ‘billboard’ marker i.e. it does not change bearing or tilt with changing view position. Location markers can be manipulated by:
• Searching for an address by typing it out in a text field, that may also support auto-completion. This process is referred to as geocoding.
• Dropping a pin at a location and showing its address. This can be done with a single tap or a long press at the location. This process is referred to as reverse geocoding.

• Current Location — The last known location is typically shown on the map with a ‘flat’ marker i.e. it changes bearing and tilt with changing view position. Google Maps uses a gray dot to show the last known location when it is not able to determine the current location; and a blue dot when it is. A chevron is added to the blue dot when the device is moving in order to indicate the direction of movement. A concentric transparent blue circle is drawn around the current location to represent the accuracy of the determined location. The current location is usually automatically determined by the OS and the mapping application.

A number of web mapping services also support additional informational map layers:

• Traffic — Real time traffic information is presented using a color progression to represent congestion levels. The data is gathered by traffic information servers from sources like traffic cameras and roadside sensors. Google Maps uses crowdsourced information based on the location and speed of users’ mobile phones. Users can then access this traffic information over various channels like the ‘Radio Data System’ in the FM broadcast. Google Maps is able to acquire this information by interacting with their traffic servers using cellular data. The traffic layer in Google Maps also adds icons to indicate traffic incidents such as crashes, road closures and construction.
• Transit — The transit layer is used to display the public transit network in a city. This includes trains and buses.
• Bicycle — The bicycling layer is used to overlay bike paths and suggested bike routes. The styling of the base map is also updated to emphasize bicycle friendly roads.

Besides the above default visualizations, a location aware application may also need to map out the following:

• Routes — A route of interest can laid out on a map as a flat overlay. Routes are implemented as a polyline that joins multiple line segments. A route is defined by a starting point, and an ending point, and may also include one or more intermediate way-points. It can be used to represent a planned route that will be run in the future, or an actual route that has been taken in the past. Individual segments of a planned route are used to develop an application for turn-by-turn navigation.
• Regions — An area of interest can be laid out on a map as a ground overlay i.e. it changes bearing, tilt and also zoom with changing view position. The region is typically defined as an area fitting polygon, or as a circle. Geo-fencing is a common application for marking regions on a map. Geo-fencing is used to trigger an action when a tracked object enters or exits from the region. This can be for assuring the safety of people on a route, for securing an object of value, or for marking an area of service.

Spatial decision support systems will usually involve some additional geographical information overlaid on the map. Such information may be tagged to a fixed location e.g. a photo clip — in this case, the overlay is typically in the form of an “information window” drawn as a billboard marker. Alternatively, the information may be directional e.g. moving vehicle, or wind speed and direction — in this case, the overlay is in the form of a customized flat overlay.

There are multiple ways to visualize geographical information on a map. Some of these are:

• Marker clusters — Marker clusters are a way of visualizing multiple fixed points on a map. On zooming in, the location markers are rendered separately. On zooming out, when markers start to overlap, they are combined into a ‘cluster marker’ .

• Topological map — A topological map is used to represent the spatial representation among a set of geographically related information without necessarily maintaining scale.

• Heat map — A heat map is used to show the geographical density of some parameter. The overlay is created by computing the density in cells of fixed size to generate a density surface. This surface is then rendered using a color gradient. Most GIS applications support this.

• Thematic maps — A thematic map is used to represent a particular theme within a specific geographic area. This includes the following approaches:

• Choropleth — The intensity or aggregated data associated with a region is mapped to a ‘color progression’ for rendering the overlay. This is also referred to as an Intensity Map.

• Proportional Symbol — In this approach, the aggregated data is mapped to the size of a symbol e.g. the radius of a circle.

• Isarithmic — In this approach, a connected line is used to represent regions with the same value of some data. E.g. temperature or barometric pressure on a weather map. This is also referred to as a Contour Map.

Visualization Tools

Data visualization is often a compute intensive task that is hardware accelerated by the platform that it runs on. Visualization libraries build on a number of platform APIs such as:

• OpenGL
• WebGL

A number of libraries are available for web applications that need to visualize geographical data.

• Google Maps APIs provide some basic visualization features for rendering features like marker clusters and proportional symbol maps.
• Leaflet is an extensible open-source JavaScript library that make it easier to handle layers, and visualization with popups.
• Mapbox provides a number of vizualization tools and libraries including Mapbox.js that builds on Leaflet, and the more advanced Mapbox GL JS. Mapbox also enables enhanced visualizations for BI tools like Tableau.
• Uber has provided a number of very capable libraries that build on WebGL to enable a broad range of visualizations on geodata. Luma.gl is a Javascript library that simplifies access to WebGL functionality. deck.gl enables composing multiple layers of visualization. kepler.gl is a UI tool that builds on Luma.gl and deck.gl to enable powerful and dynamic visualizations of geodata. The family of tools is collectively known as vis.gl.