0

I have been given a requirement to set the center and zoom to the state level on the state in which I have laid the most markers on a Google Map. All the data I am working with is a collection of points (latitude/longitude).

I realize that I can make a geolocation call (http://code.google.com/apis/maps/documentation/geocoding/index.html#GeocodingRequests - See: Reverse Geocoding) for each point and then count the states to determine which I should show but, since there will be hundreds to thousands of points per map, this is not practical.

Is there anything else I can do achieve this? Is there anything possible that would be similar (ex/ center of high concentration of markers)?

smp7d
  • 4,947
  • 2
  • 26
  • 48
  • I feel like you're going to get tripped up in anything mathematical because of the different sizes of states...imagine that your markers were laid out in a perfect grid...you couldn't do anything to determine the right state without knowing which state each marker is in. Perhaps your source could supply that piece so you don't have to reverse geocode each point? – Robot Woods Dec 13 '11 at 19:23
  • The source cannot provide that data. I would be willing to push back if I can find a way to zoom to the general area with the highest concentration of marker (ignoring the state designation). I realize this is not a very well thought out request, but I have to give them something. – smp7d Dec 13 '11 at 19:30
  • what about a pseudo-reverse? Take the max and min lat (same with longitude), divide by X, and, as you place each marker, increment some counter for each 'slice'...then you'll get a general idea without having to call out to Google every time – Robot Woods Dec 13 '11 at 19:54
  • Can you elaborate? I'm not sure exactly how this will solve the issue. – smp7d Dec 13 '11 at 19:57

2 Answers2

1

Here is an idea. Refer to this SO Question. The first answer has a link to an XML file with the polygon coordinates for all the state boundaries. You could also simplify the polygons so there are not so many vertices.

When a marker is added to the map you can check to see if it exists in one of the 50 point arrays using an algorithm like this:

UPDATE: the original function I posted was not in javascript. Here is a Javascript one and a fiddle of it working:

/*
* state == array of Google LatLng objects.
* lat == latitude to test
* lng == longitude to test
*/
function pointInPolygon(state, lat, lng) {
    var polyCount = state.length;
    var oddNodes = false;
    var j = 0;
    for (var i = 0; i < polyCount; i++) {
        j++;
        if (j == polyCount) {
            j = 0;
        }
        latitudeBoundry = state[i].lat();
        longitudeBoundry = state[i].lng();
        latitudeBoundry2 = state[j].lat();
        longitudeBoundry2 = state[j].lng();
        if ((latitudeBoundry > lat && latitudeBoundry <= lat 
             || latitudeBoundry2 > lat && latitudeBoundry <= lat)) {
            if (longitudeBoundry + (lat - latitudeBoundry)
                / (latitudeBoundry2 - latitudeBoundry) 
                * (longitudeBoundry2 - longitudeBoundry) > lng) {
                oddNodes = !oddNodes
            }
        }
    }
    return oddNodes;
}

If it exists increment a counter.

Once you have found the state with the most markers you can set the zoom by creating a bounds object.

//the polyArray is the array of points for the target state.
var bounds = new google.maps.LatLngBounds();
for ( var i = 0; i < polyArray.length; i++ )
{
  bounds.extend( polyArray[ i ] );
}

//set the map viewport
map.fitBounds(bounds)

I have no idea about how this will pan out performance wise, but it should be much faster than reverse geocoding.

Community
  • 1
  • 1
Bryan Weaver
  • 4,455
  • 1
  • 29
  • 39
  • If that pointInPolygon function works this may actually be the answer. However, I would venture to guess that there would be no way that this can be practical. I will be running through that algorithm potentially 50 times for each of thousands of markers. I may give it a shot though, thanks. – smp7d Dec 13 '11 at 21:06
  • 1
    I agree it may not be practical, but it is all I can think of off the top of my head. You may want to head over to http://gis.stackexchange.com/ and see if any of the GIS pros have any ideas. – Bryan Weaver Dec 13 '11 at 21:21
1

Here is a sample page that implements the grid method I mentioned earlier. It's similar in concept to Bryans, but, because it just is a simple division to determine which sector in the grid, it may be a little faster on large data sets (but you do lose the state specificity):

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Auto Center</title>
<script type="text/javascript" src="http://maps.googleapis.com/maps/api/js?sensor=false"></script>
<style>
#wrap {width:960px;margin-right:auto;margin-left:auto;position:relative;}
#map_canvas {width:100%;height:700px;}
table,td {border-collapse:collapse;border:thin #000 solid;}
</style>
</head>
<body>
<div id="wrap">
<div id="map_canvas"></div>
<div id="tabular"></div>
<script type="text/javascript">
function randomFromTo(from, to){
    return Math.floor(Math.random() * (to - from + 1) + from);
}
    var map;
    var placesToFilter=Array();
    var myOptions = {zoom: 6,mapTypeControl: false,mapTypeId: google.maps.MapTypeId.ROADMAP};
    //---Creating random data
    for(i=0;i<500;i++){
        var a=new Object();
        a.lat=randomFromTo(2600,4900)/100;
        a.lng=-randomFromTo(6600,12500)/100;
        placesToFilter.push(a);
    }
    //---Get max and min latitude
    var maxLat=placesToFilter[0].lat*1;
    var minLat=placesToFilter[0].lat*1;
    for (i=1;i<placesToFilter.length;i++) {
        if (placesToFilter[i].lat*1>maxLat) {maxLat=placesToFilter[i].lat*1;}
        if (placesToFilter[i].lat*1<minLat) {minLat=placesToFilter[i].lat*1;}
    }
    //---Get max and min longitude
    var maxLng=placesToFilter[0].lng*1;
    var minLng=placesToFilter[0].lng*1;
    for (i=1;i<placesToFilter.length;i++) {
        if (placesToFilter[i].lng*1>maxLng) {maxLng=placesToFilter[i].lng*1;}
        if (placesToFilter[i].lng*1<minLng) {minLng=placesToFilter[i].lng*1;}
    }
    var s=8;//--------------------How many rows/columns the area gets gridded into
    var latDelta=maxLat-minLat;
    var lngDelta=maxLng-minLng;
    var latStep=latDelta/s;
    var lngStep=lngDelta/s;
    var latBands=Array();
    for(i=1;i<=s;i++){latBands.push(i*latStep);}
    var lngBands=Array();
    for(i=1;i<=s;i++){lngBands.push(i*lngStep);}
    //---Keeping score in these arrays
    var gridCount=new Array();
    for(var x=0;x<s;x++){
        for(var y=0;y<s;y++){
            var cell=[x,y];
            gridCount.push(cell);
        }
    }
    for(var lt=0;lt<s;lt++){
        for(var lg=0;lg<s;lg++){
            gridCount[lt][lg]=0;
        }
    }

    map = new google.maps.Map(document.getElementById('map_canvas'),myOptions);

    for(p=0;p<placesToFilter.length;p++){
        //---Keeping track of which grid sector 
        var whichLat=Math.floor((placesToFilter[p].lat-minLat)/latStep);
        var whichLng=Math.floor((placesToFilter[p].lng-minLng)/lngStep);
        gridCount[whichLat][whichLng]++;
        //---And placing the marker
        var point=new google.maps.LatLng(placesToFilter[p].lat,placesToFilter[p].lng);
        var marker = new google.maps.Marker({position: point,map: map});
    }
    //---Figuring out which cell 'won'
    var checking=gridCount[0][0];
    var rightLat;
    var rightLng;
    for(lt=0;lt<s;lt++){
        for(lg=0;lg<s;lg++){
            if(gridCount[lt][lg]>checking){
                checking=gridCount[lt][lg];
                rightLat=lt;
                rightLng=lg;
            }
        }
    }
    //convert grid sector to lat/lng (center of sector)
    var winningLat=maxLat-(rightLat*latStep)-(latStep/2);
    var winningLng=minLng+(rightLng*lngStep)+(lngStep/2);
    var newCenter=new google.maps.LatLng(winningLat,winningLng);
    map.setCenter(newCenter);
    showTable=true; //--------------this will display the table of data so you can see how many markers are in each sector
    if(showTable){
        var table='<table>';
        for(row=0;row<s;row++){
            table+='<tr>';
            for(td=0;td<s;td++){
                table+='<td>'+gridCount[row][td]+'</td>';
            }
            table+='</tr>';
        }
        table+='</table>';
        document.getElementById('tabular').innerHTML=table;
    }
</script>
</div>
</body>
</html>
Robot Woods
  • 5,677
  • 2
  • 21
  • 30