I’ve been taking a break from my usual work in C#/WinForms to improve my web development skills. As such, i’ve been learning PHP, HTML5, jQuery and CSS3, among other things.

I recently had an opportunity to work with the Google Maps API to create a map that shows the locations of a large set of users. In doing so, I discovered some useful extensions that improve the appearance, functionality and performance of the user map. In this post, i’ll share some of those with you as I walk through the process of creating such a map.

Example of a map of users

Google Maps API

The Google Maps API is available on a few different platforms, but the one we’ll be using is the JavaScript version. This allows us to create the map and add the markers after the page loads, using a script. To use the Maps API, load the script in the <head> section of your page:

<script type="text/javascript" src="https://maps.googleapis.com/maps/api/js?sensor=true&v=3.exp"></script>

Step 1: The location data

The first step is to assemble the data that will populate the markers on the map. For the purposes of this post, i’m going to limit this data to:

  • The name of the user
  • A URL to the user’s avatar (a small image file)
  • The user’s location – latitude (+ve = North, -ve = South) and longitude (+ve = East, -ve = West), ideally stored in separate fields

The source and representation of this data will be application-specific (e.g. PHP/MySQL, C#/MS-SQL, etc), so it must first be transformed into a useful format that can be read using JavaScript. JSON is by far the simplest option for this. In my case, working with PHP, all I need do is query the data from the database and encode the resulting associative array using the json_encode() method. In .NET, JSON support can be added using a library like Json.NET.

A neat way of loading your data so it can be accessed by the user map script is to wrap the JSON in an assignment statement, effectively turning it into an executable script itself:

var external_data = [ {"username":"user1", "url":"user1.png", "lat":"-31.94", "lng":"115.87"}, {...} ];

If this script is dynamically generated, all you need do is add it to your <head> element after the Maps API:

<script type="text/javascript" src="my_data_source_url.json"></script>

Step 2: Embedding a map

It’s almost fiendishly simple to embed a Google Map on a page. The only markup required is a <div> with a class/ID that you can reference in the script. It’s a good idea to wrap this inside another <div> to give you more flexibility when applying styles:

<div id="google-map-container">
   <div id="google-map"></div>
</div>

Everything else is done in JavaScript. To initialise the map, we need to pass a few parameters to its constructor; the coordinates the map is centered on, the zoom level and the type of map (road/satellite/etc):

var center = new google.maps.LatLng(-31.9554, 115.8585);

var map = new google.maps.Map(document.getElementById('google-map'), {
    zoom: 9,
    center: center,
    mapTypeId: google.maps.MapTypeId.ROADMAP
});

The above code runs after the page has loaded (in jQuery, you can use the $(document).ready() function for this).

Step 3: Creating map markers

The conventional way to create a map marker is to instantiate the google.maps.Marker class and pass the map, coordinates and other properties to its constructor. While you can customise the appearance of a marker to some degree (including by replacing the icon with a custom image), they do not offer as much flexibility as I would like. For my user map, I want to be able to control the style of the markers using CSS – which means I need to be able to apply classes to them.

Thankfully, there is an extension to the API which builds on the basic marker, giving you the choice of specifying the content using HTML markup instead. To use the RichMarker class, add the following to your <head> tag:

<script type="text/javascript" src="https://google-maps-utility-library-v3.googlecode.com/svn/trunk/richmarker/src/richmarker-compiled.js"></script>

You can then create a marker using the following code (assume the variable user is an element taken from the location data):

var marker = new RichMarker({
    map: map,
    position: new google.maps.LatLng(user.lat, user.lng),
    content: '<img src="' + user.url + '" title="' + user.username + '" class="my-map-marker" />'
});

You can then apply a style to the my-map-marker class in a stylesheet.

However, there is a problem associated with this approach; performance degrades when you add a large number of markers to the map. Since we want to display a large number of users on our map, this is highly undesirable.

Thankfully, there is another very useful extension to the Maps API that addresses this problem: MarkerCluster dynamically reduces markers in close proximity to each other into ‘cluster’ markers, which display the number of markers contained within them. As you zoom in, clusters are replaced by smaller clusters, and finally by the markers themselves. You can click on a cluster to zoom in to the appropriate level required to display all included markers. To use this extension, add the following to your <head> tag:

<script type="text/javascript" src="https://google-maps-utility-library-v3.googlecode.com/svn/trunk/markerclusterer/src/markerclusterer_compiled.js"></script>

Instead of directly associating the markers with the map object, we add them to an array and pass this to the MarkerCluster class:

var markers = [];
for (var i = 0; i < external_data.length; i++) {
    var user = external_data[i];

    var marker = new RichMarker({
        position: new google.maps.LatLng(user.lat, user.lng),
        content: '<img src="' + user.url + '" title="' + user.username + '" class="my-map-marker" />'
    });

    markers.push(marker);
}

var cluster = new MarkerClusterer(map, markers);

This object now becomes responsible for controlling which markers are displayed on the map at any given time. Its behaviour can be customised, but the defaults are quite sensible for our scenario.

…and that’s it – everything you need to create a map showing the locations of your users.

Next steps

Now that we’ve got our user map up and running, we can start building additional functionality, such as interactivity. To capture when the user clicks on a map marker, attach an event handler using the following syntax:

google.maps.event.addListener(marker, 'click', my_click_handler_function);

The event handler function has a single parameter containing a MouseEvent object, which has a latLng property describing the location on the map that was clicked (i.e. the location of the marker).

The Maps API provides a built-in InfoWindow class, which you can use to display a ‘speech bubble’ callout containing the HTML markup of your choice. It works like this:

function my_click_handler_function(evt) {
    infoWindow = new google.maps.InfoWindow({
        position: evt.latLng,
        content: 'Show information about the user here'
    });
}

By setting the marker’s draggable property to true, you can allow the user to move the marker around on the map. You can handle this using the dragstart and dragend events. For example, you could update the current user’s location by making an AJAX call when the user finishes dragging the point.

I’ve shown how to create markers from a simple data source, but you might derive marker locations from other sources that are available at run-time. If the browser supports geolocation (most modern browsers do), you can create a marker from the user’s current location:

if (navigator.geolocation) {
    navigator.geolocation.getCurrentPosition(
        function (position) {
            // called if the location is found
            var latLng = new google.maps.LatLng(position.coords.latitude, position.coords.longitude);

            /* create a marker here */
        },
        function () {
            // called if an error occurs
            alert('Unable to determine your location.');
        }
    );
}

If you don’t have exact map coordinates for a marker, you can use the Google Places API to obtain the coordinates given a place name (or search term). To do this, you must add &libraries=places to the URL for the main API script. See the Places API documentation for more on how to transform a place name into map coordinates.

Final words

Integrating Google Maps into a web application is much simpler than you might think. By adding your own data to the map (in this case, locations of users) in the form of markers, you can combine the power of both systems and create genuinely useful features for your site. Hopefully, my suggestions and pointers in this area will help to make your Maps integration faster, smoother and more elegant.

I recently attempted to transform a boring, alphabetical list of tags into a more visually-appealing (and more informational) tag cloud. No doubt you’ve seen tag clouds on blogs and other websites (there’s even one on here!) but for the uninformed:

A tag cloud is a form of ‘weighted list’ where reusable tags (keywords, categories, etc) are arranged on a diagram in such a way that more frequently-used tags appear in a larger font. The arrangement of the tags themselves can be ordered (usually alphabetically) or a more organic layout can be used (e.g. a force-based algorithm). Their purpose is to show an extra dimension of information (i.e. frequency) and thus draw attention to more popular tags.

This blog has already dedicated a lot of time to the generation and layout of diagrams, so this article will focus on another important part of any tag cloud algorithm: how to assign a suitable font size to each tag. This is a somewhat tricky problem in that:

  • The total number of tags and upper bound of each tag’s frequency are unknown
  • We obviously want to constrain the font size so that it falls within a sensible range
  • Regardless of the distribution of the frequencies, we want to have strong variation in font sizes

Before I settled on a solution, I tried a number of other approaches:

Proportional sizing

Given a query to determine the frequency of use for tags, such as:

SELECT Tag, COUNT(*) as [Frequency]
FROM PostsTags
GROUP BY Tag

We can use a formula like this to assign font sizes:

size = minSize + ((maxSize-minSize) * (frequency / maxFrequency))
Proportional sizing
Results using proportional sizing

This formula scales each tag according to its proportion to the maximum value, ensuring the font size is between minSize and maxSize. The problem is that it is adversely affected by outliers; e.g. if 90% of tags vary by only 10^1 and 10% vary by 10^3, there will be one or two enormous tags and lots of very small ones (with not much variance between them).

Sizing by random sample

In this approach, n tags are randomly selected and their frequencies become the threshold values for each font size (where n is the number of different font sizes that can be used). This takes advantage of the fact that psuedo-random numbers are uniformly-distributed, so querying for the number of frequency levels we want (instead of all values) will give a good indication of the different values in the set.

The SQL query for a random sample (in this case, of size 10) is of the form:

SELECT TOP(10) Tag, COUNT(*) as [Frequency]
FROM PostsTags
GROUP BY Tag
ORDER BY newid()
Sizing by random sample
Results using sizing by random sample

The result, however, is less-than ideal; the resulting font sizes are random (since we are working with a random sample) and outliers are likely to be ignored (in particular the minimum and maximum, e.g. the most frequent tag will appear as large as the second most-frequent).

Sizing by order using ROW_NUMBER()

This approach uses the T-SQL ROW_NUMBER() windowing function to assign a sequential number to each tag, sorted according to frequency; so, the least-used tag will be numbered as 1, the most-used tag as n (total number of tags). This means that, regardless of the gap between each tag’s frequency, we will get a uniform increase in font size.

The SQL query would look something like this:

SELECT Tag, COUNT(*) as [Frequency], ROW_NUMBER() OVER (ORDER BY COUNT(*)) as [Order]
FROM PostsTags
GROUP BY Tag

Then, sizes would be assigned using the following formula:

size = minSize + ((maxSize - minSize) * ((order - 1) / maxOrder)))

(Since order starts at 1, we subtract 1 because we want the right-hand size of the expression to evaluate to zero, i.e. size = minSize)

Sizing using ROW_NUMBER()
Results using sizing by ROW_NUMBER()

The problem with this approach is that tags with equal frequencies will not be assigned the same font size; rather, they will increase in font size according to table-order. Since a large number of tags are likely to have been used between 0 and 1 times, the result will be unsatisfactory.

The solution: sizing using DENSE_RANK()

The approach above is based on a good premise, but isn’t quite right. If only there was some way of sizing according to order where equal frequencies were assigned the same value… oh wait, there is! The T-SQL DENSE_RANK() windowing function behaves much like ROW_NUMBER(), except that it assigns the same value when there are ties in the set. (We could have used the normal RANK() function, but this leaves gaps in the numbering)

The SQL looks something like this:

SELECT Tag, COUNT(*) as [Frequency], DENSE_RANK() OVER (ORDER BY COUNT(*)) as [Rank]
FROM PostsTags
GROUP BY Tag

Then, sizes are assigned using the following formula:

size = minSize + ((maxSize - minSize) * ((rank - 1) / maxRank))

(I’ve opted to make maxSize an exclusive boundary, to avoid a situation where maxRank is 1 and we risk dividing by zero)

Sizing using DENSE_RANK()
Results using sizing by DENSE_RANK()

The result is a tag cloud where:

  • Font sizes increase uniformly from the least-used tag to the most-used tag
  • Outliers are not ignored, nor do they result in hugely disproportionate font sizes
  • Tags with a frequency of zero are always assigned minSize
  • Upon first use, a tag immediately stands apart from the unused tags

Keeping font sizes low until tags reach maturity

If you don’t want the maximum font size to be assigned until a certain frequency is reached, you can apply a transformation to the ratio:

size = minSize + ((maxSize - minSize) * ((rank - 1) / maxRank) * Math.Min(1, maxFrequency / threshold))

This will allow font sizes to gradually approach maxSize as the most-used tag’s frequency approaches threshold.

Final words

Hopefully this article gives you an idea of some of the complexities involved in producing good-looking tag clouds, and allows you to avoid some of the common pitfalls associated with this.

This is just a quick announcement that i’ve enabled comment voting on my blog. I often get interesting and thoughtful comments from people, and i’d like to be able to show my appreciation – and allow other users to do so as well. I’m not going to retrospectively vote on old comments, but from now on, i’ll be upvoting comments that are insightful and constructive. I encourage my readers to do so as well!

Animation of force-based tessellation algorithm

When I first blogged about force-based algorithms, my focus was firmly on charting and graphing; specifically, producing aesthetically-pleasing diagrams consisting of nodes and connectors. Force-based algorithms have many other applications in computer science, from graphics to simulations to problem-solving and beyond. In this post, i’m going to look at the application of a force-based algorithm to the task of arranging images in a tessellating pattern.

The forces in play

As with my force-directed diagram algorithm, this force-based algorithm requires at least two forces to be in play; if there is no opposing force, then the layout would either collapse or ‘fly away’ from the viewport. In this case, the dominant force is a pulling force that acts towards the middle of the screen; regardless of where an image tile is situated, it will be dragged towards the center point. In this way, the force is much like a localised gravitational field (although it does not strengthen as objects approach the point). The opposing force is that of collision; when one image tile would otherwise cross into the bounds of another, a reaction force is applied in the opposite direction (some of the energy is absorbed during the collision, making it only partially elastic).

Furthermore, when a collision occurs, image tiles are not permitted to overlap. Instead, one of three things will happen:

  • The tile will slide against the horizontal edge of the colliding tile (towards the center)
  • The tile will slide against the vertical edge of the colliding tile (towards the center)
  • The tile will remain in its original position

The choice of action will be determined according to whether the tile’s path is unobstructed.

Together, these forces encourage the image tiles to reach a stable configuration, in which they are clustered together with minimal gaps between them.

The algorithm

LET center_screen represent the middle of the screen
LET damping represent the factor by which velocity decreases between iterations
LET absorbance represent the factor by which energy is absorbed during a collision

INITIALISE the each image tile with a random (or uniformly-distributed) placement

REPEAT
    FOR EACH image tile:
        LET net_force equal zero
        LET pulling_force act at the angle formed between the image tile and center_screen

        SET net_force = net_force + pulling_force
        SET velocity{i} = (velocity{i-1} * damping) + net_force
        SET position{i} = position{i-1} + velocity{i}

        IF a collision occurs
            LET reaction_force act at the angle formed between the colliding image tiles

            SET net_force = (net_force * absorbance) + reaction_force
            SET velocity{i} = (velocity{i-1} * damping) + net_force

            LET proposed_horizontal represent the coordinate (position{i}.x, position{i-1}.y)
            LET proposed_vertical represent the coordinate (position{i-1}.x, position{i}.y)

            IF proposed_horizontal collides with no other image tile
                SET position{i} = proposed_horizontal
            ELSE IF proposed_vertical collides with no other image tile
                SET position{i} = proposed_vertical
            ELSE
                SET position{i} = position{i-1}
            END IF
        END IF
    END FOR EACH
UNTIL (total displacement drops below threshold) OR (maximum iterations reached)

The force, velocity and position variables are represented using vectors. Collisions take into account the entire bounds of each tile (implemented using Rectangle.IntersectsWith() in .NET).

The initial placement of the image tiles is significant; they must be placed in such a manner that they do not overlap. The implementation offers two initial arrangement types; random (in which positions are completely randomised), or uniform (where image tiles are assigned to positions on a uniform grid).

The implementation

The algorithm is implemented in the ImageCollage class. Each instance of ImageCollage holds a collection of ImageInfo objects, which represent the image tiles.

ImageCollage:

  • Images – Collection of ImageInfo objects.
  • Arrange() – Runs the force-based algorithm.
  • Distribute() – Responsible for the initial placement of image tiles.
  • Render() – Renders the montage using the image files and resulting layout.

ImageInfo:

  • Path – Path to the image file.
  • OriginalWidth, OriginalHeight – Dimensions of the image, used to preserve the aspect ratio.
  • Bounds – The bounds of the image tile (will change during layout).
  • Velocity – The velocity of the image tile during the layout algorithm.
  • RelativeSize – Controls the size of the image tile with respect to the others on the canvas.

The full implementation can be found on the project page for the Image Collage Generator, where I have developed a complete Windows Forms application around this concept.

The results

The implementation of the force-based algorithm for image tessellation appears to work well. It copes with small numbers of images as well as larger counts (150+ images) without significant degradation in performance or the quality of layout. Further enhancements would be required to cope with very large number of images (500+) – this algorithm was designed with fewer number of images in mind.

In general, uniform initialisation seems to produce fewer gaps than random initialisation; however, the random positioning tends to produce more organic-looking layouts. Depending on the variation in aspect ratio between the images used, one approach may produce better results than the other.

Final words

Be sure to check out the Image Collage Generator to see this force-based algorithm in action. Once again, the force-based approach lends itself well to a task which would otherwise require manual placement. Genetic algorithms may also be an alternative to the force-based approach; tessellation is a problem for which fitness criteria can be clearly evaluated – however, I would wager than a genetic algorithm would take longer to find a solution and would be more computationally-intensive than the force-based approach.

I hope you find this application of force-based algorithms useful. Perhaps you can think of other problems that could be solved in this manner?

Okay, so batch scripting may be regarded as a bit of a computing dinosaur these days (particularly following the rise of PowerShell)… but I argue that it still has legitimacy on the developer/power-user’s workstation. Batch scripts are still well-suited to:

  • Startup scripts
  • Scheduled tasks
  • Macros
  • …and they even function well as small utilities, installers, configuration wizards, etc

Of course, batch files have come a long way since their first appearance in MS-DOS and OS/2; Windows NT (and later versions) expanded the range of built-in commands that were available, as well as offering a set of console programs to broaden what could be done from the command prompt. There are still a lot of operations (e.g. various shell commands, system configuration, etc) that cannot be included in batch files, but it is possible – sometimes requiring a bit of creativity – to do some very useful things in batch scripts.

This post focuses on a few practical examples relating to the management of desktop applications; including ClickOnce apps, mutual exclusivity, running programs as Administrator, etc

Mutually exclusive applications

I keep several batch scripts on my desktop that each start a set of programs; for example, I have a developer script that launches Visual Studio, SQL Management Studio and a few third-party tools. I also have a social script that launches my twitter client, instant messenger, etc. Some of these scripts overlap (i.e. the same program is included in different scripts) and, also, I may already have one or two of these applications open when I run the batch file.

In light of these requirements, I need to start the programs on my list only if they are not already running. Thankfully, this is not too difficult to do in batch scripts:

tasklist /FI "IMAGENAME eq [process name]" 2>NUL | find /I /N "[process name]">NUL
if "%ERRORLEVEL%" NEQ "0" {cmd /c} start [path to executable]

Where [process name] is the name of the process as it appears in the Windows Task Manager; e.g. firefox.exe – and [path to executable] is either the name of the executable to run (if it falls within the PATH variable) or the full path to the program you want to run. Note that the ‘cmd /c’ is optional (see the explanation below).

So, how does this work?

  • The tasklist command is the command-line equivalent of the Windows Task Manager. By invoking it with the /FI switch, you can apply a filter. You can filter according to a range of criteria, such as the process name, user, window title, etc – here, we just want to get an exact match (using the eq operator) on the name of the process.

The output of the tasklist command looks like this:

C:\Windows\system32>tasklist /FI "IMAGENAME eq firefox.exe"

Image Name                     PID Session Name        Session#    Mem Usage
========================= ======== ================ =========== ============
firefox.exe                   2404 Console                    1    434,096 K
  • By piping the output of the tasklist command into the find command, we can determine whether there was a match; by using the /I and /N switches, we perform a case-insensitive match and place the success/failure in the ERRORLEVEL variable (which is used by most command-line tools for this purpose).
  • We don’t want to output the results of the find command to the console, so we redirect it to NUL (i.e. nowhere).
  • If the find command returns a match, the ERRORLEVEL will be zero; therefore, we only need to run the program if its value is non-zero, i.e. NEQ “0”.
  • Running a command with cmd /c ensures that the script will go on running without waiting for the operation to complete. Some programs (e.g. Firefox) will tie up the console window if started from the command line, and we want to avoid this.
  • The start command is the preferred way to run GUI applications, and can also be used to open documents and URLs – we use it here because it supports the widest variety of targets.

Starting ClickOnce applications

Unlike normal executables, applications deployed using ClickOnce are started using a bootstrapper (which is normally handled by the shell). This includes applications written in Windows Forms, WPF or Silverlight. Shortcuts to ClickOnce apps have the extension .appref-ms (rather than .lnk for regular shortcuts), and these files are not recognised by the start command (as in the previous example).

Thankfully, they can be run using the following syntax:

rundll32.exe dfshim.dll,ShOpenVerbShortcut [path to appref-ms file]

Where [path to appref-ms file] is the full path to the ClickOnce shortcut file. The path may include environment variables such as %USERPROFILE% if, for example, you want to point to a shortcut on the user’s desktop.

How does this work?

  • The rundll32 command executes a function in a Win32 DLL as if it were an executable file. You might want to use this when you have a function which is predominantly called from code (but still operates independently), if you want to avoid creating many executables when a single DLL will suffice, or to deliberately obfuscate a command that users are not intended to start.
  • dfshim.dll is responsible for much of the functionality in ClickOnce; it contains functions to install, remove, start and update applications, and is distributed as part of the .NET Framework.
  • The name of the function we want is ShOpenVerbShortcut, which is the same function that the windows shell uses to run .appref-ms shortcut files. You simply pass a path to the function and it takes care of the rest.

Running processes as Administrator

Unfortunately, when Microsoft designed User Account Control (UAC) in Windows Vista and beyond, they did not provide a convenient way to start processes with elevated permissions from the command line. This may be partly due to the anticipation that PowerShell would take over from batch scripting, however I still think it is a bit of an oversight.

The way that you would normally go about running a program with elevated permissions is to use the ShellExecute function in Win32. Instead of using a conventional verb like ‘Open’ or ‘Print’, you use the special runas verb. Unfortunately, this part of the API is not exposed to the command line, and its complex argument list prevents it from being called using rundll32 (as in the previous example).

Thankfully, there is a handy command-line tool called ShelExec, which you can download and place alongside batch scripts that need to run programs with elevated permissions. Using ShelExec, you can run a program as Administrator using the following syntax:

shelexec /verb:runas [path to exe]

Where [path to exe] is either the name of the process to execute (if in the PATH variable) or the full path to the executable file.

Putting it all together

Okay, so what if I want a script that starts my web browser, e-mail client, Visual Studio (which I need to run with elevated permissions) and my twitter client? Here’s the script:

@ECHO OFF

tasklist /FI "IMAGENAME eq firefox.exe" 2>NUL | find /I /N "firefox.exe">NUL
if "%ERRORLEVEL%" NEQ "0" cmd /c start firefox

tasklist /FI "IMAGENAME eq outlook.exe" 2>NUL | find /I /N "outlook.exe">NUL
if "%ERRORLEVEL%" NEQ "0" start outlook

tasklist /FI "IMAGENAME eq devenv.exe" 2>NUL | find /I /N "devenv.exe">NUL
if "%ERRORLEVEL%" NEQ "0" shelexec /verb:runas devenv

rundll32.exe dfshim.dll,ShOpenVerbShortcut %USERPROFILE%\Desktop\MetroTwit.appref-ms
  • We need the ‘cmd /c’ prefix in the case of Firefox, because it does ugly stuff with the console window if we allow it to use the same instance of cmd.exe that the script runs from.
  • Outlook can be started without having to specify the full path to the exe.
  • We need to use ShelExec to start Visual Studio as Administrator.
  • MetroTwit is a ClickOnce application, so we must run it using the bootstrapper.

I hope you find these tricks useful, and can apply them to save yourself a bit of time and effort.