GIS

  

I’m writing this posting for two reasons. Firstly my company is currently engaged in a project with a client about getting
more of their data onto their intranet based mapping tool, so I’ve spent the last 3 days researching and getting back up to speed
on the industry.

Secondly my brother has just got a new job working as sales manager for a company providing GIS data, so I thought an introduction
and overview of the subject might be of use to him. Apologises if I get too technical Mike.

Geographic Information Systems

A GIS is a system the stores and displays maps electronically. Its a smart tool that helps us understand the world around us better,
to get our work done more efficiently.
I’ve been interested in GIS since one of my first jobs where I was in charge of writing a routing and optimising algorithm for
solving a variant of the Travelling Sales Problem. Essentially our product was in charge of figuring out routes for workman
to get their work down in the most efficient way possible, and send them routes on their mobile devices so they didn’t get lost.
It was really interesting work, we worked with providers of GIS data about the road network, and with the UK government for access
to electronic versions of their maps.

I think part of my interest also comes from travelling. When I first go to a new city, I’m always keen to find a map, to give
me a feel of the layout. I always choose Lonely Planet over Rough Guide, because their maps are better. It was very strange when I
was in Guyana in the Jungle, the only maps we had were from satellite images taken over 10 years ago, at a very low resolution.
Most of the time we only have a vague idea of where we were at any time. Rivercourses flood, move, the tree cover prevents
identification of key features. It made me realise how much we take accurate maps for granted.

GIS is everywhere at the moment. Tom Tom are advertising their navigation products on TV. Google Local can show me a map of my local
city in the time it takes to click a mouse, and Google Earth can let me zoom in from space to see my parents house, the roof of my
dad’s land rover. NASA can let me look at the surface of Venus.

Raster and Vector

The most important division in GIS to understand is the different between Raster and Vector information. Raster information is
pictures, its pixels that show us what our cities look like from space. Its the images that digital cameras give us. Its resolution
dependant. Vector information is mathematical in nature, its descriptions of things in terms of lines, circles, polygons.

Google earth is predominately raster based, as you zoom in loads in images with more detail.

Google Local is vector based, it shows you your local high street as a series of straight lines, it shows you the nearby river as a polygon.

The real power comes when we use raster and vector together. When we turn on the country boundaries in NASA’s World Wind
we seem them overlaid over the raster images of earth:

Raster information is an approximation to the real world, its pictures of the world. Vectors are mathematical, they are ‘idealised’
versions of the world. The mathematical nature of vectors allow us to use maths to answer questions like: “How many roads are there
within 2 miles of the river ?”. Or this more relevant example “Show me all the pubs within 2 miles of where I live” in Mappoint 2004:

Raster examples:

Pictures of landscapes, from space or from aircraft
Pictures of clouds
Infrared pictures showing heat usage

Vector examples:

Countries, Regions, Postal boundaries
Streets, Motorways, Garages
Wind speeds, wave heights

Organisations

OpenGIS

The main organisation dealing with GIS standards appears to be the “Open Geospatial Consortium”, a group of 300 organisation
worldwide. It has prepared various specifications for open standards:

GML: A geographical data format based on XML
Simple Features (SFSQL): A standard way to store data within standard SQL Databases
Various web interfaces for providing both vector and raster information in agreed formats (GML)

Companies

The leaders in the industry for GIS software seem to be ESRI, Mapinfo and Integraph.
The two largest data providers are NAVTEQ, used by Google maps, and TeleAtlas.

Representation

An important thing to understand in GIS is that there is no universal ‘best’ representation for coordinates on Earth. The earth
is not an exact sphere, its not flat, so various different schemes have been invented. Which is used is, as ever, is dependant
on what your trying to achieve.

Longitude and Latitude

The standard way of representing points on the earth is obviously using long and lat. Longitude is the lines from the North Pole to
the South Pole, with 0 degrees going through Greenwich, London. Latitude is the lines around the ‘waist’ of the earth, with 0 degrees
at the equator, + 90 degrees being the north pole.

Longitude and Latitude are measured against a known datum. This is the reference model used, i.e. the mathematical figures used
for calculating the best fit shape of the Earth. The most common currently in use is the WGS84 datum (WGS stands for ‘World
Geodetic System’). It is possible to convert from one datum to another, but this can require some quite complex mathematics.

GPS

Global Positioning System is where a lot of GIS data is coming from. It is a set of satellites flying through space, transmitting
signals allowing the calculation of very accurate position. GPS figures are long/lat figures based on the WGS84 datum.

Grid References

Rather than capture coordinates as spherical coordinates (like long/lat), coordinates can be stored as a reference on a grid.
As the Earth is obviously not flat, this is an approximation, but can be easier to deal with when mapping smaller areas. The UK uses
a grid reference system for its ‘Ordnance Survey’ (OS) maps. In this coordinate system, points are measured in Eastings and Northings.
This grid is based on a different datum, OSGB36, based on a slightly different ellipsoid representation of the Earth. The ‘Helmert’
datum transformation can be used to convert to WGS84, but with an approximate error of 7m (depending on location). The image below
shows where the eastings and northings are measured from. The letters in the grids allow another way of specifying location, called
National Grid References (NGRs), with further digits specifying easting and northing offsets within each 100km grid square.
More digits give more accuracy or specify a smaller area. An example of an NGR is ‘NN 166 712’. This gives a 100m square area in
Scotland. The good thing about NGS’s is that they are useful shorthand to give approximate position, or for capturing an ‘area’.

The UK government can provide digital maps of the country in GML, with currently 440 million distinct features taking up 660
Gigabytes of storage. The data is called OS Mastermap

Formats

GML and SVG

GML and SVG are both XML based standards that are used within GIS. GML stands for Geography Markup Language, and
is a format designed to hold geographical features, geometry (vector), raster information, as well as units, coordinate
representation systems, and map styles.

SVG is actually just a generic format for holding vector graphic information, and stands for Scalable Vector Graphics.
Its like an Open Standard version of Adobe’s Flash files, and supports both raster and vector information of any kind, not just
geographic info.
The customer we are doing the GIS work for currently uses SVG for their display of GIS data inside a web browser, using
Adobe’s free SVG plugin for Internet Explorer (note: firefox supports a subset of SVG natively now). SVG has well defined Javascript
bindings so its easy to create interactive displays.

To me GML seems a better storage format and SVG a better display format.

Other

There are various file formats in use within the industry. Although the OpenGIS is pushing GML, most data seems to be available
in either ESRI’s shape format, or Mapinfo’s standard file format. Both are proprietary, but easy to parse formats that most tools
support.

Databases

There seems to be a big push to moving ‘spatial’ capabilities into databases at the moment. This makes sense as really geometry
is just another attribute of an entity. Moving the geometry into database tables allows this data to be kept alongside other
attributes, as well as allowing databases to carry out geospatial queries.

The market leader in geospatial databases is Oracle. All versions of their database support what they call Locator features.
This allows the storages of complex vectors into tables, as well as support for complex queries (e.g. find me all objects that
lie within the boundary of this polygon, find me there nearest 5 customers to our store). The top end product also has spatial
features that allow very complex geometric calculations to be done. The nice thing is that the free Oracle Express (10g at the
moment) supports the locator features. IBM’s DB2 seems to have some sort of spatial extender but I couldn’t find any information
on the web about it.

Some of the GIS software companies provide software to help with database storage, like ESRI’s ArcSDE, but these are just ‘layers’
that sit between software and the database, and are not open formats, tying you into using a particular vendor.

Two of the open source database engines have recently added spatial features to their engines. Postgres SQL has the addon
PostGIS that supports the SFSQL specification mentioned above (as does Oracle). MySQL also has spatial extensions based
on the SFSQL spec, but the current version (5.0) seems only to support planar (flat) and not spherical coordinate systems. The
mathematics used for distances, areas, etc. are different for planar and spherical representations.

It was hoped that Microsoft SQL Server would add some spatial features to the new 2005 release, but this was not the case. There
is however an interesting MSDN article showing how spatial features can be added to SQL Server, but this does not support
open standards (surprise surprise).

Spatial Indexes

When reading about GIS formats, one of the key issues is how the formats are ‘indexed’ to make retrieval efficient. Oracle uses
Helical Hyperspatial Codes (HHCodes), a data structure developed by the Canadian Hydrograph office. Despite the fancy name,
it seems to be a binary tree, dividing each dimension in order. Its designed to support as many dimensions as desired, to an
arbitrary level of detail. The MSDN article discusses the use of Hierarchical Triangular Meshes, which is a technique of
covering a globe with a mesh of subdivided triangles. These seems work well for spherical mapping, but does not seem as general
case as HHCodes. PostGIS and MySQL seems to use extensions of standard database indexes, rather than specific spatial indexing.

Summary

The GIS industry is becoming more and more important, as developers I can see us having to deal with spatial information more and
more. If i get time I’ll try and write an article on how to access SFSQL spatial data from within Delphi. For more information
see Wikipedia’s entry.

Comments (originally on blogger.com)

Paul Ramsey said…

PostGIS and MySQL use R-Tree indexes, which are rather specifically for spatial data (well, any data type which can be
decomposed to a range rectangle). So does Oracle Spatial, for that matter. Space-filling curves, which map multi-dimensional
data to something sortable into a B-Tree are ways of leveraging non-spatial database technology to be more useful for
spatial data. Space-filling techniques tend not to be as balanced as R-Trees, however. The hierarchical grid is the final
trick, and can be quite performant, but needs to be carefully tuned to the characteristics of the data, unlike R-Trees which
automagically work for data of uneven scales.

Comments are closed.