What is the best algorithm to visually separate overlapping vehicles in close proximity on a map?

Question

I am looking for an algorithm that will allow me to visually separate any two to four vehicles within a large list of vehicles that are close enough together on a map such that they obscure one another. I need to filter out instances where there are more than four vehicles as the vehicles will congregate in certain areas in large quantities and it is unimportant to separate them in those cases. The algorithm should also mark vehicles that have already been processed.

In my problem space, it is more important to know that the vehicles are present and to be able to see information about them, than to have absolutely accurate information as to where they are.

The idea is to add approximately 10 yards (given the map scale that is being used) so individual vehicles can be seen instead of being obscured by other vehicles in close proximity.

I have thought of several ways to do this, but given the quality of the answers here and the fact that somebody might have already done this, I thought I would post the question.

I am adding an image of what is currently shown in order to help clarify as one of the comments suggested (OK, it is not a diagram but this is what is actually shown to the user).

Several of the answers require changing the visual queues used to indicate how many vehicles (golf cars) are in a given location. I don't want to change what the users are expecting visually and have to explain to the users what the meaning is. The answer using a square is closest to what I was looking for but that is just the visual part. I am also looking for the algorithm for how to best traverse the list finding groups of 2 to 4 golf cars that are within n (lets say 5) yards of each other while ignoring larger groupings (cart barn, snack shack, etc). The numbers on the icons correspond to the cart numbers.

This application also allows the user to zoom the map in/out so the further zoomed out the map the more separation is needed between the cars so that they do not visually overlap.

Note in the picture that cars 78 and 62 are obscuring the cars that are behind them.

Answer 1

A square seems like a good candidate since you are not worried about instances with more than four vehicles.

I would take the average location of all vehicles in "overlapping" proximity, and set this as the "center" of the square, with length and width sufficently large that putting a vehicle on each corner will not result in any overlap.

Then I would start with vehicle 0 at the top left and work my way around the corners of the square counter clockwise, adding the next vehicle to the next corner.

Simple, and effective, you lose some accuracy, assuming thats OK (from your post it seems it is?) this is what I woul do.

Answer 2

I think I would be tempted to render each vehicle as a dot (irrespective of whether they are in close proximity or not). Above the dot I would draw the vehicle name label (for legibility you could draw an opaque or semi-transparent background behind the labl, or else border the label in the contrasting colour).

For vehicles in close proximity I would plot a single, larger dot and have either the list of names above or else, if this obscures the map or other vehicles, have a line emanating from the dot to a breakout box in a less obtrusive part of the map with the list of names.

E.g.:

                             V66
               V12           V07
V23             ·            V22
 ·                            •
          V78             •
           ·              |
                       +-----+
                       | V09 |
                       | V34 |
                       +-----+

Answer 3

A common way to do this is with alternate markers. If your usual marker is a push-pin image use a push-pin with a 2 on its top for two items in the same spot. Another way is to put the first marker on the exact spot and put later markers "next" to it for some definition of "next". For your example of vehicles: put the second at some distance down the road that, given the current scale, ensures visual separation. The exclusion rectangle used for testing whether to use the alternate placement is now elongated to cover the second marker so that when a third vehicle is placed it will be placed behind the first two markers.

Answer 4

The Google term is label placement. In general this is a complete research area itself and there are no really good general solutions, but for specific scenarios like this there are several suitable implementations. Wikipedia/Automatic label placement is also a good starting point.

According to your image you expect very few overlapping labels, then you can go for a simple greedy algorithm optimized for speed.