How to avoid hidden objects on a map

Mike George · 2013-12-19 17:46:36

Hello, it's been a couple of years since the last conundrum you very kindly helped me solve (actually you solved it for me), and now I've got a nice little problem that I can't help feeling should have a fairly simple algorithmic answer if only I knew what I was doing

I'm placing markers at points on a map. The map is redrawn every minute and the number and position of the points can change each time, and I have the x,y coordinates (representing pixel distances) for each point in an array after each refresh of the map. Usually the array is fairly sparse with big gaps between the points, but it is common for clusters of up to 4 or 5 markers to occur at the same point, and I want the markers to be displayed on the map with their anchor points at least 10 pixels apart. The common approach of 'clustering' the markers and springing them apart when the cluster is selected isn't appropriate, they have to be drawn separately (but it doesn't matter if they overlap as long as the 10 pixel rule is applied).

What I think I need to do is find any clashing pairs of x,y coordinates (where x AND y are less than 10 away from its nearest neighbour) and adjust them accordingly. If it helps I can sort the array of coordinates in order of x or y, or the points' distance from the origin.

In my mind's eye I can see all the points as little bar magnets standing on end on the map, free to move in any direction along the surface of the map until their mutual repulsion has pushed them a sufficient distance apart. How to translate that into an algorithm to make it happen I have no idea.

The best I can come up with is to sort them all into distance order (from the origin), start at the beginning of the array and when I find a point that is within 10 pixels of its predecessor's distance from the origin, check the distance between the two points and if that is less than 10 move them apart. Then re-sort the array on distance and repeat, until I make a complete pass without moving any points (ignoring for now the possibility that the map might be so crowded that a solution is impossible).

Can anybody suggest a quicker and simpler way to do this please?

Last edited by Mike George (2013-12-19 18:34:03)

bobbym · 2013-12-20 04:22:29

Hi Mike George;

Do you have a picture of your final best result?

Mike George · 2013-12-20 04:58:10

bobbym wrote:

Hi Mike George;
Do you have a picture of your final best result?

No, I haven't implemented it yet, I was hoping somebody could suggest an elegant nutcracker before I get my sledgehammer out. I've got pictures of the current results but it's not very helpful because you can't see the hidden markers!

I am experimenting with a cruder approach, where I (conceptually) divide the map canvas into 10-pixel squares and set a flag in the appropriate square when I add a marker to the map. Before I add each marker I check to see if there is already one anchored in that square and if there is I try the next adjoining square, and so on until I find an unclaimed one, adjust the lat and long for the marker accordingly and add it. As the markers are added in random order and the average density on the map is fairly low this approach could work but I would be happier with a more robust solution.

bobbym · 2013-12-20 05:26:25

Hi;

Sounds like you are trying to implement some scheme that places points equidistant from each other? Maybe it does not sound like that at first but when you try any of your ideas will that be the result?

Mike George · 2013-12-21 03:40:50

They don't need to be equidistant from each other, just moved the minimum amount to stop them obscuring each other on the map.

I've implemented the simple version described above and I've attached before and after pictures showing the result.

bobbym · 2013-12-21 04:25:21

Hi;

Looking at it now, I think I would go with your cruder approach. Searching for a more elegant solution might take a lot of time and might only achieve a minor speed improvement. So unless you are doing this millions of times, I would go with the approach you outlined in post #3.

Math Is Fun Forum

#1 2013-12-19 17:46:36

How to avoid hidden objects on a map

#2 2013-12-20 04:22:29

Re: How to avoid hidden objects on a map

#3 2013-12-20 04:58:10

Re: How to avoid hidden objects on a map

#4 2013-12-20 05:26:25

Re: How to avoid hidden objects on a map

#5 2013-12-21 03:40:50

Re: How to avoid hidden objects on a map

#6 2013-12-21 04:25:21

Re: How to avoid hidden objects on a map

Board footer