Plotting points so that they do not overlap if they have the same co-ordinates

Question

Hi everyone,

I have a function that takes longitude and latitude and converts it to x and y to be plotted. The conversion to X and Y is working fine and that is not what I have the problem with.

I want to ensure that two points are not plotted in the same place. In one set of results there are about 30 on top of each other (because they have the same latitude and longitude), this number could be a lot larger.

At the moment I am trying to achieve this by moving points to the left, right, top or bottom of the point to make a square. Once a square made up of points has been drawn, then moving to the next row on and drawing another square of points around the previous square.

The code is Javascript but it is very generic so I guess it's slightly irrelevant.

My code is as follows:

var prevLong, prevLat, rand = 1, line = 1, spread = 8, i = 0;

function plot_points(long, lat){

    // CODE HERE TO CONVERT long and lat into x and y

    // System to not overlap the points 
    if((prevLat == lat) &&  (prevLong == long)) {

        if(rand==1) {
            x += spread*line;
        } else if(rand==2) {
            x -= spread*line;
        }   else if(rand==3) {
            y += spread*line;
        }   else if(rand==4) {
            y -= spread*line;
        }   else if(rand==5) {
            x += spread*line;
            y += spread*line;
        }   else if(rand==6) {
            x -= spread*line;
            y -= spread*line;
        }   else if(rand==7) {
            x += spread*line;
            y -= spread*line;
        }   else if(rand==8) {
            x -= spread*line;
            y += spread*line;
        // x = double
        }   else if(rand==9) {
            x += spread*line;
            y += spread;
        }   else if(rand==10) {
            x += spread;
            y += spread*line;
        }   else if(rand==11) {
            x -= spread*line;
            y -= spread;
        }   else if(rand==12) {
            x -= spread;
            y -= spread*line;
        }   else if(rand==13) {
            x += spread*line;
            y -= spread;
        }   else if(rand==14) {
            x += spread;
            y -= spread*line;
        }   else if(rand==15) {
            x += spread*line;
            y -= spread;
        }   else if(rand==16) {
            x += spread;
            y -= spread*line;
        } else if(rand==17) {
            x -= spread*line;
            y += spread;
        }   else if(rand==18) {
            x -= spread;
            y += spread*line;
        }   else if(rand==19) {
            x -= spread*line;
            y += spread;
        }   else if(rand==20) {
            x -= spread;
            y += spread*line;
        }

        if(rand == 20) {rand = 1; line++; } else { rand++;  }
        i++
    } else {

        line = 1;
        i = 0; 

    }

    prevLat = latitude;
    prevLong = longitude;

    return [x,y];

}

This is the output:

It isn't working correctly and I don't even know if I am approaching the problem in a correct way at all.

Has anyone had to do this before? What method would you suggest?

Answer 1

Start by grouping your coordinates. Your long,lat -> x,y conversion might not be necessary until the last step. One method is to create a hash map where you store each long/lat position and a count for each position.

Then you convert each long,lat position into a x,y coordinate and use the count to decide how to render the points centered around x,y position but with a size according to the number of points.

A working algorithm to render a square is:

var count = 30; // example
result = [];

var width = count/Math.sqrt(count);
width = Math.floor(width);
height = Math.floor(count/width);
var remain = count % width;

var i,j;

for(i = 0; i < width; i++)
  for(j = 0; j < height; j++)
    result.push([x-Math.floor(width/2)+i, y-Math.floor(height/2)+j]; 
for(i = 0; i < remain; i++)
  result.push([x-Math.floor(width/2)+i, y-Math.floor(height/2)+j];

Input is count of of dots, x,y center coordinate, output is an array of points to render.

The last line is the remaining dots, e.g a 15 dot square renders:

OOOO
OOOO
OOOO
OOO

Answer 2

Using Ernelli's solution as an example, I have managed to get the plotting working correctly. It seems a bit long winded, but it works and it is not slow.

Ernelli's solution has a mistake in the second for loop:

for(j = 0; i < height; i++)

Should be:

for(j = 0; j < height; j++)

Anyway, this is my code that I am using and that is working. pointArray is an array of all the elements that are to be plotted:

var countArray = new Array();

// Go through every point and group same co-ordinates together 
for (var i = pointArray.length-1; i > -1; i--) {
    if(pointArray[i] != undefined) 
    { 
        var found = 0;

        // Check if this point is already in array
        for (var j = countArray.length-1; j > -1; j--)
        {
            if(countArray[j] != undefined)
            {
                if((pointArray[i].getBBox().x == countArray[j]["x"]) && (pointArray[i].getBBox().y == countArray[j]["y"]))
                {
                    countArray[j]["points"].push(pointArray[i]);
                    found = 1;
                }
            } 
        }

        // The point is not in the array, so add it
        if(found != 1) 
        {
            var index = countArray.length;
            countArray[index] = new Array();
            countArray[index]["x"] = pointArray[i].getBBox().x;
            countArray[index]["y"] = pointArray[i].getBBox().y;
            countArray[index]["points"] = new Array();
            countArray[index]["points"].push(pointArray[i]);
        }

    }
}

// For each co-ordinate
for (var j = countArray.length-1; j > -1; j--)
{
    if(countArray[j] != undefined)
    {   
        // If there is more than one point
        if(countArray[j]["points"].length > 1) {

            // Calculate the square points
            var count = countArray[j]["points"].length;
            var x = countArray[j]["x"];
            var y = countArray[j]["x"];
            result = [];

            var width = count/Math.sqrt(count);
            width = Math.floor(width);
            height = Math.floor(count/width);
            var remain = count % width;


            var i2,j2, xx, yy;
            var space = 8;
            for(i2 = 0; i2 < width*space; i2+=space)
            {
              for(j2 = 0; j2 < height*space; j2+=space)
                {
                result.push([(Math.floor(width/2)+i2), (Math.floor(height/2)+j2)]); 
                }   
            }
            for(i2 = 0; i2 < remain*space; i2+=space)
            {
              result.push([(Math.floor(width/2)+i2), (Math.floor(height/2)+j2)]);
            }

            // Go through each point and then translate it to it's new position
            for (var jj = countArray[j]["points"].length-1; jj > -1; jj--)
            {
                if(countArray[j]["points"][jj] != undefined)
                {
                    if(result[jj] != undefined)
                    {   
                        countArray[j]["points"][jj].translate(result[jj][0]-((width*8)/2), result[jj][1]-((height*8)/2))
                    }
                }
            }
        } // End if count more than 1
    } // End if undefined
}

Note that this uses many raphael.js functions (such as getBBox and translate)