Archive for ‘Bing Maps’

November 28, 2012

Masking out particular areas of interest on Bing Maps

A recent question on the MSDN Bing Maps forums asked if it was possible to display a Bing Map in which only a particular country was visible, painting out everything else. There’s certainly nothing built into the API to do this – the tiles from which maps are constructed are pre-rendered images and know nothing about country outlines displayed on them.

However, if you have coordinate data representing the area of interest you want to display – be that a country or any other area of interest – I don’t think it should be too hard to achieve the effect desired using a dynamic tilelayer. The principle is exactly the same as if you were creating a raster tilehandler that dynamically drew polygons representing an area of interest. The only difference is that, instead of shading the polygon defined by your data, you invert the graphics to shade everything else, leaving the polygon of interest transparent.

If you’re using .NET to draw your tiles, what you’d do is create a graphics object representing the tile as usual, but instead of calling FillRegion() on the polygon drawn on the tile, you’d create a region covering the whole tile and then use Region.Exclude() to “remove” the area covered by the polygon, before filling the rest of the region.

As an example, I grabbed the coordinates for the island of Corsica from GADM, and put them into an array, as:

PointF[] selectedArea = {
  new PointF(9.17986f, 41.36541f),
  new PointF(9.22097f, 41.36625f),
  new PointF(9.2198...
  ...
}

If drawn using a conventional tile rasteriser, this would look like:

image

However, the addition of the following two lines inverts the region to be shaded:

// Define a new region that spans the whole tile
Region region = new Region(new Rectangle(0, 0, 256, 256));

// Exclude the polygon from the region
region.Exclude(polygonPath);

Re-rendering the map (and changing the fill colour to blue) now gives:

image

And, if you tweak the shading options a bit and draw a line around the region you can create something a bit more aesthetically appealing. I’ve only added the masking layer with opacity 0.7 so that you can see the other countries slightly in the background, but you could make the whole rest of the map opaque if you wanted.

So here’s a Bing Map that masks everything other than Corsica. Although the screenshot below is static, this solution uses a normal tile handler so the map retains all the normal panning/zooming functionality, and only Corsica will remain in clear view:

image

Here’s the code for the HTML page shown above:


<!DOCTYPE HTML PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html  xmlns="http://www.w3.org/1999/xhtml">
<head>
<title></title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<script type="text/javascript" src="http://ecn.dev.virtualearth.net/mapcontrol/mapcontrol.ashx?v=7.0"></script>
<script type="text/javascript">
function GetMap() {

var map = new Microsoft.Maps.Map(document.getElementById("mapDiv"),
{ credentials: "ENTERYOURBINGMAPSKEYHERE",
center: new Microsoft.Maps.Location(42, 9),
mapTypeId: Microsoft.Maps.MapTypeId.road,
zoom: 8
});

// Create the tile layer source
var tileSource = new Microsoft.Maps.TileSource(
{  uriConstructor: 'TileHandler.ashx?q={quadkey}',
width: 256,
height: 256
});

// Construct the layer using the tile source
var tilelayer = new Microsoft.Maps.TileLayer({ mercator: tileSource, opacity: 0.8 });

// Push the tile layer to the map
map.entities.push(tilelayer);
}
</script>
</head>
<body onload="GetMap();">
<div id='mapDiv' style="position:relative; width:800px; height:600px;"></div>
</body>
</html>

And here’s the code for the TileHandler.ashx:


<%@ WebHandler Language="C#" Debug="true" %>

using System;
using System.Web;
using System.Drawing;
using System.Drawing.Drawing2D;
using Microsoft.SqlServer.Types;
using System.Data.SqlClient;

public class Handler : IHttpHandler
{

public void ProcessRequest(HttpContext context)
{

// Retrieve the requested quadkey
string quadKey = context.Request.QueryString["q"];
int zoomLevel;

// Convert quadkey to tile coordinates
int tileX, tileY;
QuadKeyToTileXY(quadKey, out tileX, out tileY, out zoomLevel);

// Calculate the pixel coordinates of the top left corner of this tile
int TLpixelX, TLpixelY;
TileXYToPixelXY(tileX, tileY, out TLpixelX, out TLpixelY);

// Use the map image as a graphics object
Bitmap mapImage = new System.Drawing.Bitmap(256, 256);
System.Drawing.Graphics graphics = System.Drawing.Graphics.FromImage(mapImage);

// Define Long/Lats of an area of interest (Corsica, in this example)
PointF[] selectedArea = {new PointF(9.17986f,41.36541f),new PointF(9.22097f,41.36625f),new PointF(9.21986f,41.37486f),new PointF(9.25958f,41.41347f),new PointF(9.26486f,41.42847f),new PointF(9.21986f,41.40514f),new PointF(9.22902f,41.42624f),new PointF(9.22152f,41.43986f),new PointF(9.21319f,41.44041f),new PointF(9.24347f,41.44652f),new PointF(9.26652f,41.46625f),new PointF(9.27791f,41.46374f),new PointF(9.26625f,41.47041f),new PointF(9.28430f,41.47735f),new PointF(9.28819f,41.49263f),new PointF(9.28347f,41.50069f),new PointF(9.26597f,41.49875f),new PointF(9.28486f,41.51652f),new PointF(9.27236f,41.52319f),new PointF(9.27347f,41.53125f),new PointF(9.28708f,41.52875f),new PointF(9.30291f,41.54569f),new PointF(9.30902f,41.54264f),new PointF(9.30874f,41.54958f),new PointF(9.34402f,41.55902f),new PointF(9.35069f,41.56652f),new PointF(9.34708f,41.57513f),new PointF(9.36763f,41.58930f),new PointF(9.36847f,41.59791f),new PointF(9.34069f,41.59208f),new PointF(9.33736f,41.60152f),new PointF(9.31958f,41.60514f),new PointF(9.29263f,41.58152f),new PointF(9.28152f,41.59791f),new PointF(9.28736f,41.60874f),new PointF(9.30736f,41.61569f),new PointF(9.30763f,41.62847f),new PointF(9.32597f,41.61875f),new PointF(9.32069f,41.61513f),new PointF(9.33402f,41.62152f),new PointF(9.35569f,41.61708f),new PointF(9.34847f,41.63791f),new PointF(9.35646f,41.64070f),new PointF(9.35569f,41.64097f),new PointF(9.36680f,41.64430f),new PointF(9.35646f,41.64070f),new PointF(9.37069f,41.63569f),new PointF(9.37735f,41.64847f),new PointF(9.38624f,41.64541f),new PointF(9.38180f,41.65152f),new PointF(9.38930f,41.65652f),new PointF(9.38125f,41.66402f),new PointF(9.39680f,41.66902f),new PointF(9.37624f,41.67013f),new PointF(9.37236f,41.67930f),new PointF(9.40124f,41.69235f),new PointF(9.39930f,41.70291f),new PointF(9.40819f,41.71374f),new PointF(9.40180f,41.71708f),new PointF(9.40847f,41.76653f),new PointF(9.39569f,41.77485f),new PointF(9.40041f,41.78902f),new PointF(9.39458f,41.79902f),new PointF(9.40652f,41.81708f),new PointF(9.40541f,41.85791f),new PointF(9.39735f,41.86125f),new PointF(9.39680f,41.87541f),new PointF(9.41597f,41.93097f),new PointF(9.40041f,41.94625f),new PointF(9.40708f,41.95152f),new PointF(9.39930f,41.95180f),new PointF(9.41125f,41.95375f),new PointF(9.41236f,41.93930f),new PointF(9.42069f,41.96736f),new PointF(9.54902f,42.10319f),new PointF(9.55486f,42.12430f),new PointF(9.55958f,42.19652f),new PointF(9.55208f,42.23208f),new PointF(9.56041f,42.28263f),new PointF(9.53236f,42.37041f),new PointF(9.54319f,42.42680f),new PointF(9.54180f,42.45902f),new PointF(9.52930f,42.49124f),new PointF(9.53319f,42.54597f),new PointF(9.51097f,42.58930f),new PointF(9.44736f,42.65652f),new PointF(9.44680f,42.68652f),new PointF(9.45819f,42.70264f),new PointF(9.46652f,42.76097f),new PointF(9.49180f,42.79374f),new PointF(9.49319f,42.80736f),new PointF(9.48041f,42.83708f),new PointF(9.48625f,42.85125f),new PointF(9.48208f,42.86680f),new PointF(9.47291f,42.87486f),new PointF(9.47819f,42.88208f),new PointF(9.46930f,42.93624f),new PointF(9.45208f,42.96152f),new PointF(9.46402f,42.98625f),new PointF(9.42013f,43.01208f),new PointF(9.41291f,43.00541f),new PointF(9.35736f,43.00708f),new PointF(9.34013f,42.99430f),new PointF(9.35041f,42.96791f),new PointF(9.34597f,42.95625f),new PointF(9.35875f,42.94541f),new PointF(9.34930f,42.92958f),new PointF(9.35958f,42.92375f),new PointF(9.32180f,42.89902f),new PointF(9.32958f,42.87208f),new PointF(9.34013f,42.86541f),new PointF(9.30958f,42.83319f),new PointF(9.34263f,42.79708f),new PointF(9.33708f,42.76458f),new PointF(9.34513f,42.73513f),new PointF(9.32208f,42.71652f),new PointF(9.32236f,42.69652f),new PointF(9.29791f,42.68152f),new PointF(9.30041f,42.67597f),new PointF(9.28541f,42.67541f),new PointF(9.27069f,42.70041f),new PointF(9.25430f,42.70513f),new PointF(9.25680f,42.71875f),new PointF(9.22902f,42.71819f),new PointF(9.23236f,42.72347f),new PointF(9.22208f,42.73569f),new PointF(9.19986f,42.72513f),new PointF(9.16763f,42.73708f),new PointF(9.13569f,42.72874f),new PointF(9.12347f,42.73263f),new PointF(9.09847f,42.71513f),new PointF(9.08513f,42.71569f),new PointF(9.08458f,42.70486f),new PointF(9.07013f,42.69291f),new PointF(9.05875f,42.69652f),new PointF(9.05986f,42.68291f),new PointF(9.05319f,42.68152f),new PointF(9.06013f,42.66125f),new PointF(9.02902f,42.65375f),new PointF(9.01486f,42.64014f),new PointF(9.00236f,42.64430f),new PointF(8.94652f,42.63319f),new PointF(8.93319f,42.64680f),new PointF(8.93625f,42.64152f),new PointF(8.91263f,42.62930f),new PointF(8.87958f,42.62930f),new PointF(8.86902f,42.60791f),new PointF(8.85041f,42.61236f),new PointF(8.83125f,42.60152f),new PointF(8.82708f,42.60680f),new PointF(8.79847f,42.60263f),new PointF(8.81041f,42.59486f),new PointF(8.79847f,42.58291f),new PointF(8.80513f,42.57208f),new PointF(8.78375f,42.55680f),new PointF(8.75986f,42.55847f),new PointF(8.76319f,42.56902f),new PointF(8.75569f,42.57180f),new PointF(8.72763f,42.56180f),new PointF(8.72430f,42.58458f),new PointF(8.70625f,42.57013f),new PointF(8.71791f,42.57069f),new PointF(8.71569f,42.56013f),new PointF(8.72264f,42.55569f),new PointF(8.71597f,42.55097f),new PointF(8.71874f,42.54013f),new PointF(8.70986f,42.53625f),new PointF(8.71958f,42.52541f),new PointF(8.69847f,42.52736f),new PointF(8.68402f,42.51514f),new PointF(8.66847f,42.51763f),new PointF(8.66430f,42.49319f),new PointF(8.64874f,42.47986f),new PointF(8.65041f,42.47319f),new PointF(8.67652f,42.47625f),new PointF(8.67986f,42.46958f),new PointF(8.66402f,42.45763f),new PointF(8.66764f,42.44569f),new PointF(8.64763f,42.44319f),new PointF(8.66319f,42.43402f),new PointF(8.65597f,42.41708f),new PointF(8.64569f,42.41347f),new PointF(8.62319f,42.42263f),new PointF(8.60791f,42.41764f),new PointF(8.60069f,42.40874f),new PointF(8.61041f,42.40486f),new PointF(8.60152f,42.39902f),new PointF(8.60847f,42.38625f),new PointF(8.57625f,42.38402f),new PointF(8.57819f,42.37486f),new PointF(8.56874f,42.37041f),new PointF(8.55402f,42.37180f),new PointF(8.54736f,42.38124f),new PointF(8.54541f,42.36986f),new PointF(8.53430f,42.37236f),new PointF(8.53847f,42.36458f),new PointF(8.55541f,42.36458f),new PointF(8.55097f,42.34513f),new PointF(8.55930f,42.34319f),new PointF(8.55291f,42.33291f),new PointF(8.57319f,42.33708f),new PointF(8.59152f,42.35291f),new PointF(8.61513f,42.34958f),new PointF(8.61763f,42.34124f),new PointF(8.62847f,42.34013f),new PointF(8.62736f,42.33180f),new PointF(8.60124f,42.32208f),new PointF(8.60124f,42.30875f),new PointF(8.62625f,42.31263f),new PointF(8.63958f,42.29902f),new PointF(8.66097f,42.30208f),new PointF(8.67458f,42.29375f),new PointF(8.67374f,42.28319f),new PointF(8.68874f,42.28013f),new PointF(8.69180f,42.26930f),new PointF(8.63513f,42.25291f),new PointF(8.60986f,42.25402f),new PointF(8.55958f,42.23569f),new PointF(8.53847f,42.23736f),new PointF(8.55125f,42.22680f),new PointF(8.57319f,42.22819f),new PointF(8.56735f,42.21874f),new PointF(8.57708f,42.21402f),new PointF(8.56819f,42.21347f),new PointF(8.56569f,42.20486f),new PointF(8.58180f,42.20680f),new PointF(8.57736f,42.18791f),new PointF(8.58624f,42.18097f),new PointF(8.56069f,42.17180f),new PointF(8.59375f,42.16903f),new PointF(8.55736f,42.14541f),new PointF(8.59097f,42.14902f),new PointF(8.59375f,42.14347f),new PointF(8.57930f,42.12791f),new PointF(8.61569f,42.13347f),new PointF(8.62291f,42.12208f),new PointF(8.65125f,42.11875f),new PointF(8.65819f,42.10069f),new PointF(8.68097f,42.10486f),new PointF(8.68986f,42.11541f),new PointF(8.70041f,42.11291f),new PointF(8.70986f,42.09791f),new PointF(8.70180f,42.08513f),new PointF(8.71069f,42.08708f),new PointF(8.72208f,42.07208f),new PointF(8.71569f,42.06347f),new PointF(8.73597f,42.06597f),new PointF(8.74847f,42.04958f),new PointF(8.74263f,42.04124f),new PointF(8.72486f,42.04319f),new PointF(8.72458f,42.03402f),new PointF(8.68569f,42.02763f),new PointF(8.65541f,42.01013f),new PointF(8.65874f,41.99152f),new PointF(8.67652f,41.98930f),new PointF(8.64958f,41.96930f),new PointF(8.61430f,41.97180f),new PointF(8.59208f,41.96402f),new PointF(8.59847f,41.95208f),new PointF(8.60736f,41.95208f),new PointF(8.60986f,41.93903f),new PointF(8.62347f,41.93569f),new PointF(8.60708f,41.89374f),new PointF(8.64125f,41.90986f),new PointF(8.71847f,41.90736f),new PointF(8.74124f,41.91541f),new PointF(8.74791f,41.93402f),new PointF(8.76458f,41.92180f),new PointF(8.78319f,41.92541f),new PointF(8.80430f,41.89569f),new PointF(8.79097f,41.88430f),new PointF(8.77847f,41.88430f),new PointF(8.78513f,41.87958f),new PointF(8.78069f,41.87319f),new PointF(8.79125f,41.86819f),new PointF(8.78902f,41.85097f),new PointF(8.74875f,41.84541f),new PointF(8.78402f,41.83263f),new PointF(8.77236f,41.82291f),new PointF(8.77430f,41.81236f),new PointF(8.74764f,41.81124f),new PointF(8.73736f,41.79680f),new PointF(8.71180f,41.80263f),new PointF(8.71013f,41.79458f),new PointF(8.73235f,41.77958f),new PointF(8.69569f,41.75152f),new PointF(8.66124f,41.75041f),new PointF(8.65930f,41.73847f),new PointF(8.70680f,41.73874f),new PointF(8.70236f,41.72569f),new PointF(8.70930f,41.72180f),new PointF(8.77597f,41.74125f),new PointF(8.78430f,41.73180f),new PointF(8.77097f,41.71347f),new PointF(8.78736f,41.70875f),new PointF(8.78125f,41.69930f),new PointF(8.81235f,41.71458f),new PointF(8.84319f,41.69652f),new PointF(8.91458f,41.69097f),new PointF(8.91375f,41.67986f),new PointF(8.88180f,41.67096f),new PointF(8.87208f,41.64625f),new PointF(8.85124f,41.64819f),new PointF(8.82041f,41.62958f),new PointF(8.80569f,41.64208f),new PointF(8.79402f,41.63263f),new PointF(8.79513f,41.62347f),new PointF(8.78513f,41.61791f),new PointF(8.79125f,41.61069f),new PointF(8.78652f,41.59708f),new PointF(8.77374f,41.59152f),new PointF(8.80402f,41.57541f),new PointF(8.78291f,41.56708f),new PointF(8.78736f,41.55680f),new PointF(8.81069f,41.55652f),new PointF(8.82097f,41.54375f),new PointF(8.84458f,41.54680f),new PointF(8.84541f,41.54013f),new PointF(8.85347f,41.54680f),new PointF(8.85597f,41.53513f),new PointF(8.84208f,41.52597f),new PointF(8.84236f,41.51819f),new PointF(8.87652f,41.52485f),new PointF(8.89069f,41.51597f),new PointF(8.88319f,41.50485f),new PointF(8.91930f,41.50541f),new PointF(8.92041f,41.48847f),new PointF(8.93264f,41.49624f),new PointF(8.93847f,41.48875f),new PointF(8.96041f,41.49180f),new PointF(8.96763f,41.48875f),new PointF(8.96513f,41.48208f),new PointF(8.97791f,41.48291f),new PointF(8.98097f,41.47347f),new PointF(8.99402f,41.48764f),new PointF(9.00263f,41.47486f),new PointF(9.01930f,41.47986f),new PointF(9.01402f,41.47208f),new PointF(9.02402f,41.46125f),new PointF(9.03791f,41.47152f),new PointF(9.04041f,41.45624f),new PointF(9.07902f,41.47652f),new PointF(9.06541f,41.45430f),new PointF(9.07347f,41.44374f),new PointF(9.09430f,41.44930f),new PointF(9.10847f,41.44013f),new PointF(9.12458f,41.44374f),new PointF(9.10541f,41.42847f),new PointF(9.10958f,41.42069f),new PointF(9.09458f,41.41236f),new PointF(9.09347f,41.39375f),new PointF(9.13347f,41.39930f),new PointF(9.12652f,41.39430f),new PointF(9.16958f,41.38375f),new PointF(9.17986f,41.36541f)};

// Convert shape from Lat/Lngs to pixel coordinates relative to this tile
Point[] points = new Point[selectedArea.Length];
for (int k = 0; k < selectedArea.Length; k++)
{
int x = LongitudeToXAtZoom(selectedArea[k].X, zoomLevel);
int y = LatitudeToYAtZoom(selectedArea[k].Y, zoomLevel);
points[k] = new Point(x-TLpixelX, y-TLpixelY);
}

// Create a polygon from these points
GraphicsPath polygonPath = new GraphicsPath();
polygonPath.AddPolygon(points);

// Define a new region that spans this tile
Region region = new Region(new Rectangle(0, 0, 256, 256));

// Exclude the polygon from the region
region.Exclude(polygonPath);

// Now fill everything but the polygon
graphics.FillRegion(Brushes.Black, region);

graphics.SmoothingMode = SmoothingMode.AntiAlias;
graphics.DrawLines(
new System.Drawing.Pen(System.Drawing.Color.FromArgb(255, 255, 255, 255), 4),
points);

// Send the tile image back to the client
context.Response.ContentType = "image/png";
System.IO.MemoryStream memStream = new System.IO.MemoryStream();
mapImage.Save(memStream, System.Drawing.Imaging.ImageFormat.Png);
memStream.WriteTo(context.Response.OutputStream);

}

///
/// COMMON UTILITY FUNCTIONS
/// See http://msdn.microsoft.com/en-us/library/bb259689.aspx
///

private const double earthRadius = 6378137; //The radius of the earth - should never change!
private const double earthCircum = earthRadius * 2.0 * Math.PI; //calulated circumference of the earth
private const double earthHalfCirc = earthCircum / 2; //calulated half circumference of the earth
private const int pixelsPerTile = 256;

public static void QuadKeyToTileXY(string quadKey, out int tileX, out int tileY, out int levelOfDetail)
{
tileX = tileY = 0;
levelOfDetail = quadKey.Length;
for (int i = levelOfDetail; i > 0; i--)
{
int mask = 1 << (i - 1);
switch (quadKey[levelOfDetail - i])
{
case '0':
break;
case '1':
tileX |= mask;
break;
case '2':
tileY |= mask;
break;
case '3':
tileX |= mask;
tileY |= mask;
break;
default:
throw new ArgumentException("Invalid QuadKey digit sequence.");
}
}
}

public static void TileXYToPixelXY(int tileX, int tileY, out int pixelX, out int pixelY)
{
pixelX = tileX * 256;
pixelY = tileY * 256;
}

public static int LatitudeToYAtZoom(double lat, int zoom)
{
int y;
double arc = earthCircum / ((1 << zoom) * pixelsPerTile);
double sinLat = Math.Sin(DegToRad(lat));
double metersY = earthRadius / 2 * Math.Log((1 + sinLat) / (1 - sinLat));
y = (int)Math.Round((earthHalfCirc - metersY) / arc);
return y;
}

public static int LongitudeToXAtZoom(double lon, int zoom)
{
int x;
double arc = earthCircum / ((1 << zoom) * pixelsPerTile);
double metersX = earthRadius * DegToRad(lon);
x = (int)Math.Round((earthHalfCirc + metersX) / arc);
return x;
}

private static double DegToRad(double d)
{
return d * Math.PI / 180.0;
}

public bool IsReusable
{
get
{
return false;
}
}

}
October 22, 2012

Machine Learning and the Bing Maps Perceptron

Wow, has it really been that long since I last did a blog post? <checks calendar> Yes, yes, it appears it has been that long. Sorry about that – normal excuses apply: work, kids, moving house, the dog’s been ill etc.

What’s more, pretty much all my spare time in the last few months has been spent studying. “Studying? What for?”, I hear you ask. Well, I’ve been rather bitten by the whole MOOC explosion that’s been happening recently, which potentially threatens to make a really big shakeup in higher education. Distance learning via the internet is hardly a new concept, but the resources available from Coursera, Udacity, and EdX (amongst others) feel that they’ve just suddenly leapt forward in terms of quality, content and accessibility.

So far this year I’ve taken courses including Artificial Intelligence, Cryptography, Logic, Algorithms, Gamification, Theoretical Computer Science, and Machine Learning, taught by world-class teachers from Stanford, Princeton, Harvard, California Institute of Technology, and Google. Although they’re using the same material as taught in those institutions, the unregulated nature on the internet means that these courses don’t come with any official accreditation from the institution concerned but that’s not important to me – I’m doing it because they’re so interesting, well-taught, and fun to learn.

Anyway, one of the homeworks in the CalTech Learning from Data course was to come up with an implementation of a Perceptron. If you’ve never studied Machine Learning before, you’d be forgiven for thinking, as I did, that a perceptron was some sort of alien weaponry from an episode of Star Trek. In fact, it’s an algorithm for classifying data into categories – a primitive kind of machine learning and forerunner to more modern techniques such as neural networks. The course specified that you could implement a perceptron using whatever language you liked – most students chose Python, Java, or Octave, a few chose C. Just to add a bit of variety, I thought I’d create one using Javascript. Since this was to be a perceptron based on only two feature classes of a dataset, I could then plot the resulting classification function in two-dimensional space such as, ooh, I don’t know, a polyline on a Bing Map. (A perceptron can operate in any number of dimensions, in which case the decision boundary becomes a hyperplane, but they’re a bit tricky to draw on a map…).

I’m not saying that this is a particularly efficient way to implement a perceptron, but I just thought it would be fun. So here it is.

Create some training data

A perceptron is a supervised learning algorithm. You provide a training data set which has already been “labelled” – i.e. the individual data points have already been correctly classified. I created an artificial training dataset by first creating an arbitrary straight line drawn between two random points in the range –1 to +1:

fx1 = 1-(Math.random()*2); 
fy1 = 1-(Math.random()*2);
fx2 = 1-(Math.random()*2);
fy2 = 1-(Math.random()*2);

/**
 * Returns the value of x2 for a given x1 such that the point lies on the target function line
 */
function targetline(x) {
  return fy1 + (fy2 - fy1) / (fx2 - fx1) * (x - fx1);
}

I then created a set of 30 random points. The points were assigned a label based on whether they lay to the left (-1) or right (1) of the target line defined above:

/**
 * Returns the result of the target function, f, for a given x
 */
function f(x) {
  if (x[2] > targetline(x[1])) {
    return 1;
  }
  else {
    return -1;
  }
}

// Training dataset array
var data = [];
    
for(i=0; i<30; i++){
  var x = [];
  x[0] = 1.0;                       // Constant
  x[1] = 1.0 - (Math.random() * 2); // Feature between -1 and +1
  x[2] = 1.0 - (Math.random() * 2); // Feature between -1 and +1
  var y = f(x);         // Correct label for this point
    
  data.push([x,y]);
}

And then, if I plot what I’ve done so far on Bing Maps, I get something a bit like this – points to the left of the target function line are labelled –1 and coloured white; points to the right are labelled +1 and coloured black:

image

Now, what’s important to understand is that, in a real machine-learning application, you don’t ever know the true target function (the green line) – all your algorithm gets to work with is the labelled points in the training set, like this:

image

The role of the perceptron is to try to determine a hypothesis function that separates the features in the dataset based on their label (in machine learning-speak, it shatters the data), so that all the black points lie on one side and all the white points on the other. This will be an approximation to the true, unknown target function.

The perceptron works by first initialising a vector of weights corresponding to each feature (dimension). The vector contains one more element than the number of dimensions, as their is additional “zeroeth” weight to represent the offset from the origin. For a 2d Bing Map, I initialised a weight vector containing three elements as follows:

w = [0, 0, 0];

Then, loop through the dataset of training points, multiplying each feature by the corresponding weight, and determining the sign of the output compared to the sign of the correct labelled output for this point. In doing so, keep track of any misclassified points – that is, points that, based on the values in the current weight vector, produce the incorrect output compared to the known correct label:

// Find points that are misclassified under the current hypothesis/weights
misclassified = [];


// Identify misclassified points
for (var i = 0; i < data.length; i++) {
  value = 0;
  for (var j = 0; j < w.length; j++) {
    value += w[j] * data[i][0][j];
  }
  // Compare to correct output for this point
  if (sign(value) != sign(data[i][1])) {
    misclassified.push(data[i]);
  }
}

If no points get misclassified, then the current weight vector can be used as the final hypothesis function. If any points get misclassified, then an arbitrary misclassified point is chosen and its output is used to update the weight vector. Then the process starts again.

It’s a fairly primitive algorithm, and it can take lots of iterations to determine a hypothesis function that correctly labels all the points in the training set, so I moved the logic for the perceptron calculation into a webworker which could run in the background and only sent the results back to the page when they were finished. This means that the page stays responsive and the UI doesn’t hang while the perceptron runs. When it’s finished you should get a result as follows:

  • The green dotted line represents the true, unknown target function
  • The black and white dots represent training examples which have been classified based on the target function
  • The blue solid line is the hypothesis function suggested by the perceptron which shatters the dataset – it classifies all the training examples correctly (although note that it does not match the true target function exactly, so its performance out-of-sample will not be perfect).

image

Now, this has been a fairly trivial example, and I’ve only been using a Bing Map with the blank “Mercator” background as a 2d canvas on which to draw points and lines in arbitrary 2-dimensional space, but hopefully you can see the potential applications for this sort of algorithm to separate spatial features into multiple classifications:

Here’s the HTML Code:



Bing Maps 2D Perceptron

  .blacktext div{
    color:red !important; /*Make Pushpin text black*/  
  } 




  var MM = Microsoft.Maps;

  // Declare the points through which the target function line will pass
  var fx1, fy1, fx2, fy2 = null;

  /**
  * Returns the value of x2 for a given x1 such that the point lies on the target function line
  */
  function targetline(x) {
    return fy1 + (fy2 - fy1) / (fx2 - fx1) * (x - fx1);
  }

  /**
  * Returns the result of the target function, f, for a given x
  */
  function f(x) {
    if (x[2] &gt; targetline(x[1])) {
      return 1;
    }
    else {
      return -1;
    }
  }

/**
    The final hypothesis

    params:
        x : data point
        w : weight vector

    returns:
        The result of executing the hypothesis, given by the weights, on the
        given data point
*/
function h(x, w) {
  var val = 0.0;
  for (i = x.length - 2; i &gt;= 0; i--) {
    val += -w[i] * x[i];
  }
  return val / w[x.length-1];
}

  // Map instance
  var map = null;

  // Weight array
  var w = [];
  

  /**
  * Display the target function in the plane between [-1,-1] and [1,1]
  */
  function drawTargetFunction() {
    var line = new MM.Polyline([new MM.Location(targetline(-1), -1), new MM.Location(targetline(1), 1)], { 

      dashArray: new Array('1', '3'),
      strokeDashArray: "5,3",
      strokeColor: new Microsoft.Maps.Color(220, 20, 125, 20),
      strokeThickness: 5
    });
    map.entities.push(line);
  }

  /**
  * Display the hypothesis function returned by the perceptron in the plane between [-1,-1] and [1,1]
  */
  function drawHypothesisFunction(w, hypothesis) {
    var line = new MM.Polyline([new MM.Location(h([1, -1, 1], w), -1), new MM.Location(h([1,1,1], w), 1)], { 

      dashArray: new Array('1', '3'),
      strokeDashArray: "3,3",
      strokeColor: new Microsoft.Maps.Color(150, 20, 20, 125),
      strokeThickness: 5
    });

    // Draw intermediate hypotheses in black
    if (hypothesis == 'h') {
      line.setOptions({ strokeColor: new Microsoft.Maps.Color(20, 20, 20, 20) });
    }
    // Draw final hypothesis in blue
    else if (hypothesis == 'g') {
      line.setOptions({ strokeDashArray: "0", strokeColor: new Microsoft.Maps.Color(220, 20, 20, 125) });
    }
    
    map.entities.push(line);
  }


  /**
  * Create an array containing n random data points
  */
  function generateData(n) {
    
    var data = []
    
    for(i=0; i&lt;n; i++){
      var x = [];
      x[0] = 1.0;                       // Constant
      x[1] = 1.0 - (Math.random() * 2); // Between -1 and +1
      x[2] = 1.0 - (Math.random() * 2); // Between -1 and +1
      var y = f(x);         // Correct output for this point
    
      data.push([x,y]);
    }
    return data;
  }

  /**
   * Plot (first 2-dimensions only) of supplied data point, and style according
   * to correct output, y
   */
  function plotData(data) {   
  
    for(var i=0; i 0) {
        point.setOptions({ /* text: "1", */ icon: "blank-button-round-black.png" });
      }
      else {
        point.setOptions({ /* text: "-1", */ icon: "blank-button-round-white.png", typeName: "blacktext" });
      }
    map.entities.push(point);
    }
  }


  function initialise() {
  
    // Create the target line function
    fx1 = 1-(Math.random()*2); 
    fy1 = 1-(Math.random()*2);
    fx2 = 1-(Math.random()*2);
    fy2 = 1-(Math.random()*2);
  
    drawTargetFunction()
    
    trainingdata = generateData(30);
    
    plotData(trainingdata);
     
    // Initialise weight vector at zeros
    w = [0, 0, 0];

    // Find the right weights by running the perceptron
    w = run_perceptron(trainingdata);

    // Draw the final hypothesis (g) given by the calculated weights
    //drawHypothesisFunction(w);
    
  }


  function sign(x) {
    if(x&gt;0) {
      return 1;
    }
    else {
      return -1;
    }
  }


  function run_perceptron(data) {

    // Creates a Web Worker
    var worker = new Worker("perceptron_worker.js");

    // Posts a message to the Web Worker
    worker.postMessage({'cmd': 'start', 'data': data, 'w': w});
    
    // Triggered by postMessage in the Web Worker
    worker.onmessage = function(evt) {
      data = evt.data;
      switch (data.result) {

        case 'h':
          drawHypothesisFunction(data.w, 'h');
          document.getElementById('iterations').innerHTML = data.iteration;
          break;

        case 'g':
          drawHypothesisFunction(data.w, 'g');
          document.getElementById('iterations').innerHTML = data.iteration;
          break;
      }
    };
    
    // If the Web Worker throws an error
    worker.onerror = function(evt) {
    alert('problem with the webworker:' + evt.data);
    };  
  }

  function GetMap() {
     map = new Microsoft.Maps.Map(document.getElementById("mapDiv"),
                     { credentials: "PUTYOURCREDENTIALSHERE",
                       center: new Microsoft.Maps.Location(0, 0),
                       mapTypeId: Microsoft.Maps.MapTypeId.mercator,
                       labelOverlay: Microsoft.Maps.LabelOverlay.hidden,
                       showDashboard: false,
                       showScalebar: false,
                       zoom: 9,
                       enableSearchLogo: false,
                       enableClickableLogo: false
                     }
     );
     initialise();
                     
    }
   
   
   
      <div id='mapDiv' style="position:relative;width:768px;height:768px;"></div>    
      <div id="iterations"></div>
      <div id="infoDiv">
        <div><span style="color:#00DD00;">&#x2588;&nbsp;&#x2588;&nbsp;&#x2588;</span><span>Target Function (f)</span></div>
        <div><span style="color:#202020;">&#x2588;&nbsp;&#x2588;&nbsp;&#x2588;</span><span>Hypothesis (h)</span></div>    
        <div><span style="color:#0000DD;">&#x2588;&#x2588;&#x2588;&#x2588;</span><span>Final Hypothesis (g)</span></div>
      </div>
   

And here’s the script for the webworker, perceptron_worker.js:

// Simple helper function to determine the +ve/-ve sign of a value
function sign(x) {
  if (x > 0) {
    return 1;
  }
  else {
    return -1;
  }
}

// Triggered by postMessage in the page
onmessage = function(evt) {

  switch (evt.data.cmd) {

    // Start the perceptron
    case 'start':

      var iters = 1;

      // Hard-coded maximum number of iterations
      while (iters < 50000) {

        // Receive the set of training points and initial weight vector
        var data = evt.data.data;
        var w = evt.data.w;

        // Array of points that are misclassified under the current hypothesis/weights
        misclassified = [];

        // Identify misclassified points
        for (var i = 0; i < data.length; i++) {
          value = 0;
          for (var j = 0; j < w.length; j++) {
            value += w[j] * data[i][0][j];
          }
          // Compare to correct output for this point
          if (sign(value) != sign(data[i][1])) {
            misclassified.push(data[i]);
          }
        }

        // If all training points are classified correctly, we've finished
        if (misclassified.length == 0) { break; }

        else {

          // Choose a random misclassified point
          var mispoint = data[Math.floor(Math.random() * data.length)];

          // Update weight vector based on this point
          for (var j = 0; j < w.length; j++) {
            w[j] += mispoint[1] * mispoint[0][j];
          }
        }

        // Uncomment the following line to plot every suggested hypothesis, h, that gets produced
        // postMessage({ 'result': 'h', 'iteration': iters, 'w': w });
        iters += 1;
      }

      // Send back the final hypothesis, g
      postMessage({ 'result': 'g', 'iteration': iters, 'w': w });
      self.close(); // Terminates the worker.
      break;

    // Stop the perceptron
    case 'stop':
      self.close(); // Terminates the worker.
      break;

    // Shouldn't get this
    default:
      self.postMessage('Unknown command: ' + data.msg);
  };
};
June 19, 2012

URL Parameters for the Bing Maps website

The Bing Maps AJAX v7 API lets you create and embed a custom Bing Map in your own webpage containing Pushpins, LineStrings, and Polygons, custom overlays and specified map styles etc.

However, on many occasions you might not want, or need, to embed a map in your own site – you might be quite happy for your application to direct users to the webpage at www.bing.com/maps instead. In such cases, you generally want to load the www.bing.com/maps site to be centred on a particular location, with one or more locations highlighted on the map, or with a particular route highlighted.

Fortunately, all these can all be achieved by supplying parameters after the URL.

Unfortunately, the parameters that can be specified don’t seem to be documented anywhere. (Update: they are documented at http://onlinehelp.microsoft.com/en-us/bing/ff808440.aspx, but it seems pretty hard to find that page)

There are several old forum posts that refer to a page at http://help.live.com/Help.aspx?market=en-US&project=WL_Local&querytype=topic&query=WL_LOCAL_PROC_BuildURL.htm which apparently provided this information, but that page no longer seems to be available and I can’t find where, if at all, the information it used to contain is now published.

So, from my own memory, here’s a list of some useful parameters you can try passing to the page at http://www.bing.com/maps/default.aspx:

Parameter Example Description
cp cp=52.62~1.2 Centres the map on the specified latitude/longitude. Format for coordinates is lat~long
where1 where1=10 Downing Street, London, United Kingdom Centres the map on the specified address, and adds a default pushpin and infobox at that location.
sty sty=a Sets the map style. Valid values are:
r (road),
a (aerial),
h (hybrid = aerial with labels),
b (birdseye),
s (Ordnance Survey),
c (London Street Map)
lvl lvl=6 Sets the zoom level of the map (from 1, most zoomed out to 20 most zoomed in)
rtp rtp=pos.50_2~pos.48_5~pos.45_10~pos.52_14rtp=adr.Norwich,Norfolk~adr.Oxford,%20Oxon Sets the list of waypoints for a route to be displayed on the map. Each waypoint can either be specified as a latitude/longitude coordinate using the syntax pos.latitude_longitude, or an address using the syntax adr.street address.Individual waypoints are separated from each other with ~.

 

and here’s some examples:

Highlighting the address at 10 Downing Street, London on a London Street Map

http://www.bing.com/maps/default.aspx?where1=10 Downing Street, London&sty=c

image

Displaying the route from Norwich to Edinburgh via Oxford

http://www.bing.com/maps/default.aspx?rtp=adr.Norwich,Norfolk~adr.Oxford,%20Oxon~adr.Edinburgh,%20Scotland

image

 

Calculating a route between a set of lat/long coordinates and displaying that route on an aerial map

(route starts at (50,2), then goes through (48,5) and (45, 10) before ending at (52,14))

http://www.bing.com/maps/default.aspx?rtp=pos.50_2~pos.48_5~pos.45_10~pos.52_14&sty=a

image

 

Hope that helps someone!

Tags:
May 27, 2012

Routing Sans Frontières

I noticed a question on StackOverflow recently, concerning the ability of various web-mapping services (Google Maps, Bing Map et al.) to plan routes across national borders. I have to say that it’s a question I’ve never really considered before – all the trans-national routes I’ve ever tried to calculate have worked as expected, just the same as those contained within a single country. However, having given it some thought, it certainly is an interesting issue.

Even across contiguous land masses such as mainland Europe, most mapping services manage their datasets on a country-by-country basis. This makes sense, because the providers of that data are often governments or other national agencies, and the quality, completeness, and timeliness of data available will therefore vary between countries.

Bing and Google both offer similar country coverage for their mapping services:

  • Google publishes this spreadsheet detailing the features it offers in different countries.
  • Microsoft does the same for Bing Maps, on this MSDN page.

So far, so good, but what about situations where you plan a route that passes through more than one country? Even though the dataset may internally be partitioned into separate countries, you’d still expect those national datasets to be “connected” where appropriate, at the points where a road crosses the boundary between two countries. However, it seems that, as a by-product of managing datasets at a national level, some mapping providers don’t consider certain routes to be valid because they don’t regard roads as contiguous when they cross a national boundary.

For example, Google will plot a route between Ipiales and Pasto, in Colombia, or between Tulcan and Quito, in Ecuador, say, but it cannot calculate a route between Tulcan, Ecuador and Ipiales, Colombia… despite the fact that they lie only a few miles from each other, connected by the Pan-American Highway:

image

Bing Maps, however, does calculate this route:

image

There are other examples; Google Maps, for example, doesn’t appear to calculate any route that crosses into or out of China:

image

Which, again, Bing Maps does without complaint via the international border crossing between Zamyn-Üüd and Erenhot:

image

Of course, there are some other routes where it perhaps makes sense to be slightly cautious of crossing national borders. Bing Maps suggests that travelling from Cairo to Damascus is a “simple” 10 hour drive into Israel, Jordan, and then into Syria…:

image

Whether it makes sense to even attempt to complete this journey, Google Maps opts to send you the long way round via the Turkey/Syria border instead:

image

In practice, I’m certain I probably wouldn’t attempt to drive either of these routes…

Follow

Get every new post delivered to your Inbox.

Join 53 other followers