Saturday, November 29, 2008
OpenStreetMap rendering in Silverlight part III
For the test and dev phase I've created a simple "sketch" renderer that's fast and uses different colours purely for tile differentiation.
Here's a snapshot of the sketch renderer drawing part of new malden:
Thursday, November 27, 2008
OpenStreetMap rendering in Silverlight part II
I've written a data store for project cobalt that allows me to restructure the OSM data into a format more suitable for realtime map generation - I'm calling it a QuadStore as its a geographically clustered XML data model and GCXDM does not sounds as good.
Throwing all 1.2gb of the UK data generates a QuadStore of 365mb which is a compression I get for free due to losing duplicated data in the OSM model. I'm also ignoring OSM "relationship" data at the moment as a) I don't know what it means yet b) I'm having to much fun with just "ways".
I've then updated the silverlight proof of concept to use the QuadStore via a webservice - this seriously kicks ass in performance terms (and the proof of concept just did not scale for multi tile retrieval). Using the QuadStore means that tile filling is 1 (yes) one cost - O(1) rather than O(n) where n=number of points in tile.
So for fun I ask the proof of concept to pull every tile and draw them out as rectangles - which looks something like this (the screen shot is halfway through the draw so you can see the progression)
There's quite a bit of performance to be gained from the webservice, for example by compressing the stream (though compressed streams are not available in silverlight). And also from returning multiple tiles per call rather than one at a time.
So the next step is to change the silverlight UI to manage tiles correctly, once it does this I will release a working version. One of the nice features I should be able to deliver is being able to rotate the map...
Wednesday, November 26, 2008
Movember (the month formerly known as November)
"Movember (the month formerly known as November) is a charity event held during November each year.
At the start of Movember guys register with a clean shaven face. The Movember participants known as Mo Bros then have the remainder of the month to grow and groom their moustache and along the way raise as much money and awareness about male health issues as possible.
Movember culminates at the end of the month at the Gala Partés. These glamorous and groomed events will see Tom Selleck and Ian Botham look-a-likes battle it out on the catwalk for their chance to take home the prestigious Man of Movember title.
While growing a Mo is left to the guys, Mo Sistas (ladies who support their guys or just love Mo's!) form an important part of Movember by recruiting Mo Bros, helping to raise funds and attending the highly anticipated Gala Partés.
But it' s not all fun and games, so why the extreme behavior?
Which ever way we look at it, men are far less healthy than women. The average life expectancy for men is five years less than for women.
Men lack awareness about the very real health issues they face. There is an attitude that they have to be tough - "a real man" - and are reluctant to see a doctor about an illness or go for regular medical checks.
The aim of Movember is to change this attitude, make men's health fun by putting the Mo back on the face of English men and in the process raise some serious funds for key male health issues.
Every year about 35,000 men in the U.K. are diagnosed with prostate cancer and about 10,000 men die from of the disease. A British man has a 1 in 11 lifetime risk of developing prostate cancer . It is now the most common cancer diagnosed in men in the U.K. with at least one man dying every hour from the disease."
Friday, November 21, 2008
Proof Of Concept of OpenStreetMap in Silverlight
I need to revist how I'm going to model this in code, and how I am using MS SQL in the equation.
Thursday, November 20, 2008
OpenStreetMap rendering in Silverlight
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)
Wednesday, November 19, 2008
Finding the Nth open door
If the question is: which door is the nth open door (for example tell me where the 5th open door is) then the answer is: n2 or as per the example 52=25 (the 25th door along is the 5th open door)
private static int NextOpenDoorIsAt(int nthOpenDoor)
{
return (int)Math.Pow(nthOpenDoor, 2d);
}
So in the case where you only need to find the nth door that is open this is a faster method. This of course could be applied to my previous post to give an O(√N) solution for the whole series - the faster being down to the speed of summation vs. product.
Toggle door puzzle, fast solution
You have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.
question: what state are the doors in after the last pass? which are open which are closed?
If the questions is expressed as is door N open, the answer is
bool doorOpen = (Math.Sqrt(doorNumber) % 1) == 0;
However, as part of going through the puzzle I noticed that there seemed to be a sequence in the offset of the open doors (1, 4, 9), which looked suspiciouly like odd number offsets: 1=1, 4=1+3, 9=4+5 i.e. the value of the offset of the next open door is the previous open door offset plus the next odd number.
Which when I applied it to larger doorsets worked as well. Looking at 50 doors, which doors are open (O) vs closed (c):
[OccOccccOccccccOccccccccOccccccccccOccccccccccccOc]
If you are given the problem of find all open doors in the set, then using the square root approach is O(n). So the square root approach would look like:
private static BitArray GenerateDoorTogleSeriesResult(int doors)
{
BitArray result = new BitArray(doors);
for (int door = 1; door <= doors; door++)
result[door - 1] = (Math.Sqrt(door) % 1) == 0;
return result;
}
whilst my approach looks like:
private static BitArray GenerateDoorTogleResult(int doors)
{
BitArray result = new BitArray(doors);
int odd = 1;
for (int door = odd; door <= doors; door += odd)
{
result[door - 1] = true;
odd += 2; // next odd number
}
return result;
}
The difference being that for 1,000 doors the square root apprach requires 1,000 square root calculation, whilst mine requires 31 summations. Or in big-oh O(√n).
The calling code looks like:
static void Main(string[] args)
{
const int DOORS = 10;
BitArray suggestedAnswer = GenerateDoorTogleResult(DOORS);
BitArray fastAnswer = GenerateDoorTogleSeriesResult(DOORS);
Console.WriteLine("suggested:\n{0}", ShowDoors(suggestedAnswer));
Console.WriteLine("fast\n{0}", ShowDoors(fastAnswer));
Debug.Assert(ShowDoors(suggestedAnswer).CompareTo(ShowDoors(fastAnswer)) == 0);
}
private static string ShowDoors(BitArray doors)
{
StringBuilder sb = new StringBuilder(doors.Length+4);
sb.Append("[");
foreach (bool doorOpen in doors)
sb.Append(doorOpen == true ? 'O' : 'c');
sb.Append("]\n");
return sb.ToString();
}
I subsequently found the proof for this by Francesco Maurolico in 1575.
1575: "Arithmeticorum Libri Duo" by Francesco Maurolico is the first book
to prove a theorem by Mathematical Induction. The theorem was known 2000
years earlier by Pythagorus, but they proved it geometrically. The
theorem is that the sum of the first N odd numbers
1 + 3 + 5 + 7 + 9 + 11 + 13 +... + (2N-1) = N x N
Sunday, November 16, 2008
OpenStreetMap into SQL Server 2008 first steps
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.
Friday, November 14, 2008
Blogging, the first 30 days
Anyway the last 30 days look like:

So on an average day I was getting about 30 people looking at my blog - in the last few days my seyes entry has gone on the silverlight gallery which has generated a relatively large increase in traffic.
I've also made a killing on the revenue front - £3.82 from selling computer books and $0.37 from advertising. I think I can retire now ;-)
The most suprising thing is how much I'm using my own blog - it works very well as an aide-memoire, especially for code snippets, tools or links.. I used to think that blogging was a bit of a wierd thing to do, but now I understand the atraction. Its also made me learn and interact with a whole new set of tools and technologies.
So in summary, its been good so far!
Thursday, November 13, 2008
OpenStreetMap - show me some data
- nodes 278 millon;
- ways 23 millon;
- relations 41 thousand.
- nodes 6,441,456;
- ways 873,054;
- relations 1,362
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
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...
Monday, November 10, 2008
Dynamic tag cloud v1.2
A small update to the tag cloud to fix an issue with cross domain requests. The issue is caused by some RSS servers not having a crossdomain.xml file which is used by Flash and Silverlight to check if cross domain requests are allowed.
As a short term fix this version now proxies the request via figmentengine.com - in a later version we may need to be able to disable this (in the case where you want to host the silverlight app on your server)
So this now allows me to create tag cloud from other sites, such as the Guardian's Comment is free:
To insert into your blog use (under dashboard, layout, edit html, ensure that expand widget templates is checked).
Find the following:
<div id='sidebar-wrapper'>
<b:section class='sidebar' id='sidebar' preferred='yes'>
insert widget here
<b:widget id='Label2' locked='false' title='Dynamic Tag Cloud' type='Label'>
<b:includable id='main'>
<b:if cond='data:title'>
<h2><data:title/></h2>
</b:if>
<div class='widget-content' id='feCloud' style='text-align: center;'/>
<script src='http://www.figmentengine.com/tagCloud/feCloudv1.2.js' type='text/javascript'/>
<script type='text/javascript'>
var feCloudElementId = 'feCloud';
var feCloudFeedAddress = 'http://feedproxy.google.com/FigmentEngine';
var feCloudNavigateFormat = 'http://blog.figmentengine.com/search/label/{0}';
var feCloudSize = 400;
feTagCloudLoad(feCloudElementId, feCloudFeedAddress, feCloudNavigateFormat, feCloudSize, feCloudSize);
</script>
</b:includable>
</b:widget>
In order to start using this version, you need to change your javascript to reference v1.2 of the js file
XML Explorer
The most common case for me is that I want to visually inspect the file because the tags are not heavily constrained and the relationships are complex.
XML Explorer can handle medium sized files (300mb according to the site) and allows XPath querying - one nice feature being able to have the output from queries to multi-tabs. This makes the process of understanding a particular file much quicker.
Note this is not an editing tools, its just for viewing
Friday, November 7, 2008
Silverlight tag cloud
changes are:
- have made the id of the element that the cloud is created parameter driven (see feCloudElementId) below in Javascript
- click on a label now shows a simple pop-up selections of posts, clicking on the first item will show all posts with that label, other entries take you direct to the post
- Changed the background sphere to be silver rather than yellow - big change ;-)
- mousing over a label now shows its co-occurances visually with lines
To insert into your blog use (under dashboard, layout, edit html, ensure that expand widget templates is checked).
Find the following:
<div id='sidebar-wrapper'>
<b:section class='sidebar' id='sidebar' preferred='yes'>
insert widget here
<b:widget id='Label2' locked='false' title='Dynamic Tag Cloud' type='Label'>
<b:includable id='main'>
<b:if cond='data:title'>
<h2><data:title/></h2>
</b:if>
<div class='widget-content' id='feCloud' style='text-align: center;'/>
<script src='http://www.figmentengine.com/tagCloud/feCloudv1.1.js' type='text/javascript'/>
<script type='text/javascript'>
var feCloudElementId = 'feCloud';
var feCloudFeedAddress = 'http://feedproxy.google.com/FigmentEngine';
var feCloudNavigateFormat = 'http://blog.figmentengine.com/search/label/{0}';
var feCloudSize = 400;
feTagCloudLoad(feCloudElementId, feCloudFeedAddress, feCloudNavigateFormat, feCloudSize, feCloudSize);
</script>
</b:includable>
</b:widget>
In order to start using this version, you need to change your javascript to reference v1.1 of the js file, and add an additional parameter of the id of cloud element. This should allow you to host multiple clouds on the same page, or at least give more flexibility about the cloud id.
Thursday, November 6, 2008
Exception: The DOM/scripting bridge is disabled
My calling code in C# looked like this:
HtmlPage.Window.Navigate(new Uri(url), "_top");
Stopping this exception can be done according to MSDN by setting the correct flags.
I was doing this in javascript, using the silverlight.js functions - I just had to add it to the calling code:
var properties = { width: slWidth, height: slHeight, version: "2.0.31005.0", enableHtmlAccess: "true" };
var events = { };
var initParams = params;
Silverlight.createObject(source, parentElement,
callbackId, properties, events, initParams);
In the above excerpt I had to add the "enableHtmlAccess" to "true", note that setting it to true without quotes does not work!
Silverlight tag cloud for blogger
To insert into your blog use (under dashboard, layout, edit html, ensure that expand widget templates is checked).
Find the following:
<div id='sidebar-wrapper'>
<b:section class='sidebar' id='sidebar' preferred='yes'>
insert widget here
<b:widget id='Label2' locked='false' title='Dynamic Tag Cloud' type='Label'>
<b:includable id='main'>
<b:if cond='data:title'>
<h2><data:title/></h2>
</b:if>
<div class='widget-content' id='feCloud' style='text-align: center;'/>
<script src='http://www.figmentengine.com/tagCloud/feCloudv1.js' type='text/javascript'/>
<script type='text/javascript'>
var feCloudFeedAddress = 'http://feedproxy.google.com/FigmentEngine';
var feCloudNavigateFormat = 'http://blog.figmentengine.com/search/label/{0}';
var feCloudSize = 400;
feTagCloudLoad(feCloudFeedAddress, feCloudNavigateFormat, feCloudSize, feCloudSize);
</script>
</b:includable>
</b:widget>
changing
var feCloudFeedAddress = 'http://feedproxy.google.com/FigmentEngine';
to your feed address, note that I am using feedburner so I need to put my feedburner address here
and change
var feCloudNavigateFormat = 'http://blog.figmentengine.com/search/label/{0}';
to the url that pulls up all items that have a particular label, the widget will replace the "{0}" with the label name dynamically.
the size of the widget is controlled by:
var feCloudSize = 400;
which is the size in pixels.
common problems:
- no labels appear - do your feed entries have labels - check the address of the feed and see what you get when you open it in your browser. Also check ensure you give the syndicated address, so if you are using feedburner etc then you need to give that address, not always the address you get from feed button on the browser.
- all labels link to the same place - ensure you have put the "{0}" in the format string in the correct place.
I will update the control to allow individuals posts to be selected (by expanding the label on click)
In terms of security, you can copy the javascript files onto your server. The silverlight widget runs in a sandbox, so you can run it from my server, or hsot it on your own.
Note you should be able to use this on other blogging sites apart from blogger - the code between (and including) the DIV tag is all you need.
any problems drop a comment below!
Wednesday, November 5, 2008
Silverlight tag/label cloud for blogger
not fun :-( Blogger documentation is minimal, and I wasted too much time try to get blogger to tell me the feed address.
Have stopped at the hard-coded version for now - will move it forward later.
This latest version allows you to click on labels and see visually what the co-occurred with. Next steps will be to be able to see the list of posts for a label and to be able to open that post...
This representation does more that just look at how many times a label has been used (as per the blogger widget) - it looks at when the labels where used with other labels - which hopefully give a better "view" of what you are bloggin about.
more later, however the intention is to wrap this up into a widget that anyone can use on their blogger blog..
Saturday, November 1, 2008
Dynamic tag cloud in silverlight with colour
I've added the ability to use other RSS feeds, however there are some security issues that mean for lots of feeds this code will just fall over..
Two feeds that work apart from mine are:
http://feeds.feedburner.com/PolymathProgrammer?format=xml
http://feeds.feedburner.com/programmableweb
see if you can work out their topics by the tag cloud!
