Programmatically drawing polygons on a map by joining the outermost markers

Question

I have a sample map layer in this fiddle where the map layer is drawn using fusion table as,

var Layer = new google.maps.FusionTablesLayer({
    query: {
       select: 'lat',
       from: '1BLPDF4n0sW0i0BfD9Yo0DqbshyTH1s5Iuu_1IeU'
    },
    map: map,
    suppressInfoWindows: true
});

How can I draw a polygon programmatically by joining the outermost markers in the map so that if someone add new marker and if it is falling outside the drawn polygon then automatically the polygon should redraw to include the newly added marker too.

Answer 1

You want to do a Convex Hull of your points.

Example using the Google Maps API v3 on a random set of points

jsfiddle

code snippet:

var gmarkers = [];
var points = [];
var hullPoints = [];
var map = null;
var polyline;

var infowindow = new google.maps.InfoWindow({
  size: new google.maps.Size(150, 50)
});

function initialize() {
  var myOptions = {
    zoom: 13,
    center: new google.maps.LatLng(37.4419, -122.1419),
    mapTypeControl: true,
    mapTypeControlOptions: {
      style: google.maps.MapTypeControlStyle.DROPDOWN_MENU
    },
    navigationControl: true,
    mapTypeId: google.maps.MapTypeId.ROADMAP
  }
  map = new google.maps.Map(document.getElementById("map_canvas"),
    myOptions);

  google.maps.event.addListener(map, 'click', function() {
    infowindow.close();
  });

  google.maps.event.addListenerOnce(map, 'bounds_changed', function() {
    // Add 10 markers to the map at random locations
    var bounds = map.getBounds();
    var southWest = bounds.getSouthWest();
    var northEast = bounds.getNorthEast();
    var lngSpan = northEast.lng() - southWest.lng();
    var latSpan = northEast.lat() - southWest.lat();
    map.setCenter(map.getCenter());
    map.setZoom(map.getZoom() - 1);
    for (var i = 0; i < 10; i++) {
      var point = new google.maps.LatLng(southWest.lat() + latSpan * Math.random(),
        southWest.lng() + lngSpan * Math.random());
      points.push(point);
      var marker = createMarker(point, i);
      gmarkers.push(marker);
    }
    for (var i = 0; i < points.length; i++) {
      document.getElementById("input_points").innerHTML += i + ": " + points[i].toUrlValue() + "<br>";
    }
    calculateConvexHull();
  });
  google.maps.event.addListener(map, "click", function(evt) {
    if (evt.latLng) {
      var latlng = evt.latLng;
      var marker = createMarker(latlng, gmarkers.length - 1);
      points.push(latlng);
      gmarkers.push(marker);
      calculateConvexHull();
    }
  });
}

function removeMarker(latlng) {
  for (var i = 0; i < gmarkers.length; i++) {
    if (google.maps.geometry.spherical.computeDistanceBetween(
        latlng, gmarkers[i].getPosition()) < 0.1) {
      gmarkers[i].setMap(null);
      gmarkers.splice(i, 1);
    }
  }
  calculateConvexHull();
}

function createMarker(latlng, marker_number) {
  var html = "marker " + marker_number;
  var marker = new google.maps.Marker({
    position: latlng,
    map: map,
    zIndex: Math.round(latlng.lat() * -100000) << 5
  });

  google.maps.event.addListener(marker, 'click', function() {
    var contentString = html + "<br>" + marker.getPosition().toUrlValue() + "<br><a href='javascript:removeMarker(new google.maps.LatLng(" + marker.getPosition().toUrlValue() + "));'>Remove Marker</a>";
    infowindow.setContent(contentString);
    infowindow.open(map, marker);
  });
  return marker;
}

function calculateConvexHull() {
  if (polyline) polyline.setMap(null);
  document.getElementById("hull_points").innerHTML = "";
  points = [];
  for (var i = 0; i < gmarkers.length; i++) {
    points.push(gmarkers[i].getPosition());
  }
  points.sort(sortPointY);
  points.sort(sortPointX);
  DrawHull();
}

function sortPointX(a, b) {
  return a.lng() - b.lng();
}

function sortPointY(a, b) {
  return a.lat() - b.lat();
}

function DrawHull() {
  hullPoints = [];
  chainHull_2D(points, points.length, hullPoints);
  polyline = new google.maps.Polygon({
    map: map,
    paths: hullPoints,
    fillColor: "#FF0000",
    strokeWidth: 2,
    fillOpacity: 0.5,
    strokeColor: "#0000FF",
    strokeOpacity: 0.5
  });
  displayHullPts();
}

function displayHullPts() {
  document.getElementById("hull_points").innerHTML = "";
  for (var i = 0; i < hullPoints.length; i++) {
    document.getElementById("hull_points").innerHTML += hullPoints[i].toUrlValue() + "<br>";
  }
}

google.maps.event.addDomListener(window, "load", initialize);

html,
body,
#map_canvas {
  height: 100%;
  width: 100%;
  margin: 0px;
  padding: 0px
}

<script src="https://maps.googleapis.com/maps/api/js?libraries=geometry"></script>
<script src="http://www.geocodezip.com/scripts/convex_hull.js"></script>
<h2>Convex Hull of random set of points</h2>
<table border="0">
  <tr>
    <td>
      <button onclick="polyline.setMap(null);">hide polygon</button>
      <button onclick="calculateConvexHull();">calculate Convex Hull</button>
      <button onclick="displayHullPts();">display Hull Points</button>
    </td>
  </tr>

  <tr>
    <td valign="top">
      <div id="map_canvas" style="width: 500px; height: 300px"></div>
      <table border="1" width="100%">
        <tr>
          <th>random pts</th>
          <th>hull points</th>
        </tr>
        <tr>
          <td valign="top">
            <div id="input_points"></div>
          </td>
          <td valign="top">
            <div id="hull_points"></div>
          </td>
        </tr>
      </table>
    </td>
    <td>
    </td>
  </tr>
  <tr>
    <td></td>
  </tr>
</table>
<div id="info"></div>