Showing posts with label project colbolt. Show all posts
Showing posts with label project colbolt. Show all posts

Tuesday, June 8, 2010

Maps revisited

Last year I created a prototype map renderer in Silverlight using the OSM dataset. Since then I've been thinking about some of the issues with the design - especially:
  • the UI load time and
  • some specific issues with the Quad Store approach
  • Dataset size
  • Automated updates to the dataset, including taking differences
  • No Geograhic AI system
  • No animation engine in the renderer

I've decided that I will restart the renderer again, but with a new design, storage mechanism and using more mature agile approaches (i.e. TDD, Mocking, IoC etc). Also during this time silverlight has moved form version 2.0 to 4.0 which also offers some interesting capabilities, and .Net 4.0 now has support for memory mapped files. I also want to follow a more product management approach, with a proper backlog etc.


TDD Unit test for Strontium using Rhino Mocks
I've started writing new code, especially for the import routine using the full dataset rather than just London. As part of this I'm using PowerShell and the Pscx extensions - there seems to be some issues with handling large files, so hopefully when this gets fixed I can have a constantly updating system.

The prototype code was using the Project Cobalt name, this new effort will go under Project Strontium

Thursday, November 20, 2008

OpenStreetMap rendering in Silverlight

So the other part of OSM I wanted to look at was the feasibility of writing a Silverlight client for the OSM data. So the OSM render of New Malden, UK looks likes:



and my first attempt (mostly guessing what things should look like and be layered) looks like:



which obviously is not as good as the XSLT/SVG renderer for OSM - however I only spent a day on it. A few things I learnt, 1) the OSM renderer is doing some nice joins on street junctions 2) the OSM format is not complex, but its not documented (not to a great detail).

The New Malden data set is 1.2mb, and the silverlight code generates 976 Polylines and 178 Polygons, and it renders in 0.11 seconds.

So what does this all mean? for one, I like the OSM format, and we can build primitive data type into the system based on Node, Way and Relation to makes life easy and consistent with the OSM view. However I need a higher level model to interpret this data. That way the primitives can stay flexible and "dumb", whilst the high level can focus on routes and joins etc.

The method I used to process the data into UI elements is based on the following concept. I create a top level tile to put all the items into, and then I create PolyLines or Polygons using just ways (I don't process relations yet). I use a simple fixed formulae to map the node GPS points into X,Y (not correct or proportional - but close enough to visualize). I use Polygons for ways the end at the same location as its start, and PolyLines for everything else. I use the tag field on the ways to decide the fill or stroke colour, and set the z-index based on the same model.

The effect of creating a top level tile is that I can pan the whole of New Malden but just moving the tile, rather than having to move each item individually. It also means I can use multiple tiles to build the map, and cache them for performance (data retrieve rather than draw as at 0.11 seconds/tile I'm not worried yet)

Once I have abstracted the code into the two clean levels (primitive and map) I will post the code - at the moment it's too much of a hack (and the GPS conversion is very, very wrong)

Sunday, November 16, 2008

OpenStreetMap into SQL Server 2008 first steps

So as I said in my previous post "OpenStreetMap - show me some data" the next step in evaluating the use of the OSM data was to see how SQL Server 2008 Spatial features might help.

The first thing I wanted to look at was how to define the structure in SQL and work with it from C#. This was mainly to get a feeling for the data types involved. In SQL I created a database (UKGeo) and a table:

CREATE TABLE [dbo].[Nodes](
 [id] [int] NOT NULL,
 [location] [geography] NOT NULL,
 CONSTRAINT [PK_Nodes] PRIMARY KEY CLUSTERED 
(
 [id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

The key point is to note the datatype "geography" being used for the location field, this datatype can handle a number of GIS related structures. We also need a stored procedure to load the data:

CREATE PROCEDURE [dbo].[sp_NodeCreate]
 @id int, 
 @location geography
AS
BEGIN
 -- SET NOCOUNT ON added to prevent extra result sets from
 -- interfering with SELECT statements.
 SET NOCOUNT ON;

 INSERT INTO Nodes(id, location) VALUES (@id, @location);
END

Once again it's a simple enough procedure, with the use of "geography" being the only complexity. From C# we just need to create a command pointing to this stored procedure:

   string sql = "sp_NodeCreate";
   SqlCommand command = new SqlCommand(sql, connection);
   command.CommandType = CommandType.StoredProcedure;

and when setting up the parameters we need to specify that the @location parameter is a Udt (user defined type), in this case geography is already registered in SQL, so we can just name it:
   SqlParameter idParam = new SqlParameter("@id", SqlDbType.Int);
   SqlParameter geoParam = new SqlParameter("@location", SqlDbType.Udt);
   geoParam.UdtTypeName = "geography";
   command.Parameters.Add(idParam);
   command.Parameters.Add(geoParam);

and finally a function to call the procedure:
 private void CreateNodeInDatabase(string id, string longtitude, string latitude)
  {
   SqlGeographyBuilder builder = new SqlGeographyBuilder();
   builder.SetSrid(4326);

   builder.BeginGeography(OpenGisGeographyType.Point);

   builder.BeginFigure(double.Parse(longtitude), double.Parse(latitude));
   builder.EndFigure();

   builder.EndGeography();

   SqlGeography geo = builder.ConstructedGeography;

   command.Parameters["@id"].Value = id;
   command.Parameters["@location"].Value = geo;

   command.ExecuteNonQuery();
  }

This code uses the SqlGeographyBuilder to create an instance of type Point, which is what we want location to contain. I'm sure this code is not the best way to do this, but it serves as a starting point for understanding the relationship between SQL and CLR implementations of spatial information.

Thursday, November 13, 2008

OpenStreetMap - show me some data

Project Colbolt requires some understanding of space (actually another project does as well, but one thing at a time!) so I am going to use OpenStreetMap, as it gives me access to the underlying data. I'm not sure I can go the whole way using this - I will have to read the copyright and terms.
 
However, the first part of the plan is to take the OSM data and start to understand it. What I already like is that this is a real sized data set, the UK alone is ~1.2gb of XML, the world is 5.3gb as a zip file. So I'm looking forward to some proper coding. Since I worked in direct marketing a few years ago large geographical datasets are great fun for me (sad git).
 
The stats say that the dataset for the world contains :
  • nodes 278 millon;
  • ways 23 millon;
  • relations 41 thousand.
Node = GPS point (long/lat)
Way = a list of nodes describing a map feature (streets, fields etc)
Relation = a more complex grouping, normally of ways
 
My first step was to play with just the UK data, (always start with a small dataset that you know roughly what it should look like).
 
I wrote a little C# application to read the UK file, which gave me back some stats:
  • nodes 6,441,456;
  • ways 873,054;
  • relations 1,362
So this means we can apply a rough estimate that anything about the UK data can be sized up to the world by multiplying it by 42 (thanks for all the fish!).
Knowing there was no sensible way to try and load the whole XML file into memory (especially when we come back to the world data) I used an XmlReader to process the data. A quick scan which processed all the tags and added up these counts takes less than 30 secs for the UK - so the rule of 42 says it would take about 20 minutes to read the whole world.
 
A stripped down node (removing editing information) looks like:
 
<node id="int" lat="float" long="float">
 
In terms of trying to hold it in memory, stuffing the UK nodes into a List<float[2]> as a pair of floats required 150mb of memory, a sparse array fell over after 1gb and a Dictionary<int, float[2]> used 379 mb.
 
The List<float[2]> approach would lose the node id, which is not really a valid comparison, though I could just use a BitArray to hold the id (as big as the largest ID, a 1 indicating if its in the List<float[2]>, and the number of 1s before it indicating its offset) - this would require another 1mb of memory, but would be slower that the Dictionary approach (not validated this). In either case this is all moot as the rule of 42 shows we would need 7gb just to hold the nodes for the world - and at this stage I'm not doing that!. So we are going to need a storage system...
 
The code so far, is skeletal, but shows what we have to do to process the OSM format - note I could have skipped most of the data, but I wanted to get a fair idea of what reading the data takes:
 
 


static void Main(string[] args)
{
XmlReader reader = XmlReader.Create(@"k:\geo\uk-081015.osm");

Importer importer = new Importer(reader);
}

and the Importer class:


public class Importer
{
int nodes = 0;
int ways = 0;
int relations = 0;

public Importer(XmlReader reader)
{
// skip boring stuff
reader.MoveToContent();

reader.ReadStartElement("osm");

while (reader.IsStartElement())
{
string name = reader.Name;

switch (name)
{
case "bounds":
ReadBound(reader);
break;
case "node":
ReadNode(reader);
break;
case "way":
ReadWay(reader);
break;
case "relation":
ReadRelation(reader);
break;
default:
throw new Exception("Unknown element encounterd " + name);
}
}

reader.ReadEndElement(); // osm

Console.WriteLine("nodes {0} ways {1} relations {2}", nodes, ways, relations);
}

private void ReadBound(XmlReader reader)
{
reader.ReadStartElement();
reader.Skip();
}

private void ReadNode(XmlReader reader)
{
// get attributes
string id = reader.GetAttribute("id");
string latitude = reader.GetAttribute("lat");
string longtitude = reader.GetAttribute("lon");

reader.ReadStartElement(); // node
reader.Skip();
nodes++;

while (reader.Name == "tag")
{
reader.ReadStartElement();
reader.Skip();
}

if (reader.NodeType == XmlNodeType.EndElement)
reader.ReadEndElement(); // node
}

private void ReadWay(XmlReader reader)
{
// get attributes
string id = reader.GetAttribute("id");

reader.ReadStartElement(); // way
reader.Skip();
ways++;

while (reader.Name == "nd")
{
reader.ReadStartElement();
reader.Skip();
}
while (reader.Name == "tag")
{
reader.ReadStartElement();
reader.Skip();
}

if (reader.NodeType == XmlNodeType.EndElement)
reader.ReadEndElement(); // way
}

private void ReadRelation(XmlReader reader)
{
// get attributes
string id = reader.GetAttribute("id");

reader.ReadStartElement(); // relation
reader.Skip();
relations++;

while (reader.Name == "member")
{
reader.ReadStartElement();
reader.Skip();
}
while (reader.Name == "tag")
{
reader.ReadStartElement();
reader.Skip();
}

if (reader.NodeType == XmlNodeType.EndElement)
reader.ReadEndElement(); // relation
}

So as a first pass I'm going to stick it into SQL Server 2008 and see what the spatial features can do...

Project colbalt

Well pentasolve actually seems to work! A project I have been thinking about for a year (colbolt), looks like a goer.

What was interesting about using pentasolve is that my current thinking about the technologies and business model are completely different from what I had originally assumed.

I will post more on colbolt once I have actually done something ;-) my next few posts will be about some of the technologies that I need to build it - but I don't think you can work out what colbolt is from its technologies...