Like most problems, it turns out that plotting points on a map is quite easy if the data is perfect.  However, if the data is imperfect then things get a whole lot trickier.  Below is a description of the problem and how I solved it.

The Data

The data I used was a table of driving distances (in miles) between major US cities.  The US highway system isn’t straight lines from point to point, so this introduces a certain amount of discrepancy into the numbers and ensures that we can’t just plot them out mathematically.  For example, the distance between Miami and New Orleans listed below is 892 miles because the road goes around the cost, however, the straight line distance between the cities across the water is closer to 670 miles.

The Solution

Since we cannot just plot the points out mathematically the next easiest solution is to use a force directed graph approach.  The basic approach is as follows:

1. Lay the points out randomly in 2D space
2. If two points are too far apart, move them a little closer together
   If two points are too close together, move them slightly further apart
3. Repeat step two until the points stop moving or until you get bored of waiting

You can see a working copy of my solution below.  Full source code is available here

Note that the “Total Error” is calculated by comparing the current distance between each pair of cities with the target distance.  If this are going well then this number should get smaller with each iteration of the algorithm.  The smallest total error possible with the highway data above appears to be about 3680 due to the discrepancies in the data mentioned above.

If you need help figuring out what the map should look like you can check here

The Interesting Stuff

This solution is easy to code and gives pretty good results.  However there are a few interesting things that result from this algorithm:

The orientation of the map is random and map is often flipped left to right
The source data is only distances with no direction, so the algorithm can’t tell which way around things should be.

The solution is very sensitive to local minima
Roughly 50% of the time Seattle of Miami will get stuck on the wrong side of the map and because the points repel each other they can’t pass through to be on the correct side.  This is similar in concept to a blind man trying to get to the top of a mountain by always walking uphill.  He will always find a high point, but he may not find the highest point.  A possible solution to this problem would be to run the map simulation several times and then take the best answer found.

It’s hard to know when to stop the simulation
Force directed graphs are generally slow compared to other algorithms so we generally don’t want to run the simulation longer than we have to.  However, knowing when things have stopped and wont get any better can be quite hard.  Often, during the simulation things can seem to become static for a while with very little change between iterations before suddenly two points pop past each other and things begin rapidly improving again.  Knowing when to stop the solution (without having a human watching it) is key to success.

I learnt a lot putting this little app together.  All in all, it was an afternoon well wasted.

In an effort remedy the problem the owners of the building hired an engineer to come in and recommend ways to speed up the elevator service.  The engineer reviewed the existing elevator system and all compatible upgrade options.  Eventually the engineer came back with his recommendation:

The most cost effective way to improve the elevator service was to cover the elevator doors with mirrors.

The idea was unconventional to say the least, but it was so much cheaper than replacing the existing elevators that the building owners decided to try it.  The employees did not realize that no further modifications had been made, and everyone agreed that the new ‘upgraded’ elevators were much faster than the old ones.

The moral of the story is that sometimes it’s easier to simply distract the user while they are waiting than speed up the thing they are waiting for.  In the elevator story the people were distracted by having something to look at while they were waiting (themselves!) and this was enough to make the wait not feel as long.  This story has always stuck with me and I am always on the look out for places where I can use this principle within my applications.

With this goal in mind I created an animating progress bar skin.  The progress bar fills up at the same speed as any other, but as it does so the texture occasionally slides from left to right. This gives the impression that the bar is moving faster than it is and the whole wait feels much more positive

Check out the example below to see the principle in action.  The top progress bar has a regular skin applied and moves painfully slowly.  The bottom progress bar moves at the same speed but has an animating skin applied.  It’s easy to see that it feels like things are progressing much faster.

The full source code is available here.  Feel free to take it and use it in any way which us useful to you.  This skin has been built using Degrafa so you can easily change the colour scheme and use it in other applications.

The below example is something I created while playing with Degrafa Paths (using my movable components library again).  Paths were a huge revelation for me because they allow you to create skins (buttons etc) with arbitrarily complex shapes.  Now able to create speech bubbles and starbursts without having to embed a PNG asset.  That’s really cool

Try it Out:

The full source code is available here.  Feel free to take it and use it in any way which us useful to you.

Recently I have been playing around with the source code some more and in particular have been trying to see if I could reuse the movable component libraries I wrote.  As part of this I have tidied the code up a bit and have extracted it from the rest of the application.  Check out the demo below.

How it Works:
The movable component framework is based on the MovableCanvas class.  This class can contain movable components and is responsible for managing selections and copy/paste etc.  Into the MovableCanvas we can place any component we wish as long as it extends the class MovableComponent.  In the example below the image components are MovableComponents which contain an Image.

Try it Out:

The full source code is available here. Feel free to take it and use it in any way which us useful to you.

Things to Look Out For:

• The MovableComponent class contains a public function called clone().  You must override this function in order for the copy/paste functionality to work.
• It is also possible to force MovableComponents to maintain their aspect ratio using the maintainAspectRation property.

The challenge this week was to accurately simulate the movements of a car in 2D.  Most people don’t realize this, but when a car turns it is rotating about a point outside itself, and that point is perpendicular to the wheels.  It’s a little hard to explain, but if you check out the demo below then it all should become clear.

This app was challenging mainly due to the geometry involved, and I definitely had to scratch my head for a while before I remembered how to rotate one point around another.  I’m pretty happy with how it turned out however.  It was definitely an afternoon well spent.

Try it Out:

The full source code is available here. Feel free to take it and use it in any way which us useful to you.

A few people have me why I didn’t allow you to control the car using the arrow keys.  The answer is simply that this demo is more impressive when you can appreciate the analogue nature of car steering.

The strength of being a developer however is in the custom functionality we can add.  Recently I have put together a DrawableOverlay Flex component which can be used to allow the user to annotate/draw on any part of the application.

The example application below shows how this component works in practice.  The DrawableOverlay component can be placed over any other components in the application (in this case a Image and a Container) and the user is then able to annotate anywhere within the DrawableOverlay area.

Try it Out:

The full source code is available here.  Feel free to take it and use it in any way which us useful to you.  Come back soon to see me extend this simple example to show off some of the things which are possible.