puks1978 puks1978 - 6 months ago 79
Javascript Question

Get lat/lng inside an irregular shape polygon

I am using this function to get centroid of an irregular shape polygon however when the polygon is an L shape the point is outside.

function get_polygon_centroid(pts) {
var first = pts[0], last = pts[pts.length-1];
if (first.x != last.x || first.y != last.y) pts.push(first);
var twicearea=0,
x=0, y=0,
nPts = pts.length,
p1, p2, f;
for ( var i=0, j=nPts-1 ; i<nPts ; j=i++ ) {
p1 = pts[i]; p2 = pts[j];
f = p1.x*p2.y - p2.x*p1.y;
twicearea += f;
x += ( p1.x + p2.x ) * f;
y += ( p1.y + p2.y ) * f;
}
f = twicearea * 3;
return { x:x/f, y:y/f };
}


My points are:

(-37.81418,145.13025000000002),
(-37.814330000000005,145.13022),
(-37.813970000000005,145.12727),
(-37.813750000000006,145.12543000000002),
(-37.813680000000005,145.12478000000002),
(-37.81152,145.12517000000003),
(-37.809380000000004,145.12558),
(-37.80951,145.12675000000002),
(-37.80953,145.12685000000002),
(-37.810590000000005,145.12667000000002),
(-37.812630000000006,145.12631000000002),
(-37.81275,145.12628),
(-37.81324,145.13026000000002),
(-37.81326,145.13044000000002),
(-37.81418,145.13025000000002)


I would like to get a point inside the polygon which is far enough off the boundary if possible.

Answer

One option:

  1. find your centroid, if it is not inside the polygon

    • calculate all the points halfway between the calculated centroid and the vertices of the polygon

    • eliminate any that are not inside the polygon.

With your set of data, this results in 7 candidate points.

proof of concept fiddle

map with markers inside polygon

code snippet:

var geocoder;
var map;

function initialize() {
  var map = new google.maps.Map(
    document.getElementById("map_canvas"), {
      center: new google.maps.LatLng(37.4419, -122.1419),
      zoom: 13,
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });
  var polygon = new google.maps.Polygon({
    map: map,
    paths: data
  });
  var bounds = new google.maps.LatLngBounds();
  for (var i = 0; i < polygon.getPaths().getAt(0).getLength(); i++) {
    bounds.extend(polygon.getPaths().getAt(0).getAt(i));
  }
  map.fitBounds(bounds);
  var marker = new google.maps.Marker({
    map: map,
    position: get_polygon_centroid(data)
  });
  for (var i = 0; i < polygon.getPaths().getAt(0).getLength(); i++) {
    var polyline = new google.maps.Polyline({
      map: map,
      path: [marker.getPosition(), polygon.getPaths().getAt(0).getAt(i)]
    });
    var length = google.maps.geometry.spherical.computeLength(polyline.getPath());
    var pt = google.maps.geometry.spherical.computeOffset(marker.getPosition(), length / 2,
      google.maps.geometry.spherical.computeHeading(marker.getPosition(), polygon.getPaths().getAt(0).getAt(i)));
    if (google.maps.geometry.poly.containsLocation(pt, polygon)) {
      var candidateMarker = new google.maps.Marker({
        map: map,
        position: pt,
        icon: "http://maps.google.com/mapfiles/ms/micons/blue.png"
      });
    }
  }
}
google.maps.event.addDomListener(window, "load", initialize);

function get_polygon_centroid(pts) {
  var first = pts[0],
    last = pts[pts.length - 1];
  if (first.lat != last.lat || first.lng != last.lng) pts.push(first);
  var twicearea = 0,
    x = 0,
    y = 0,
    nPts = pts.length,
    p1, p2, f;
  for (var i = 0, j = nPts - 1; i < nPts; j = i++) {
    p1 = pts[i];
    p2 = pts[j];
    f = p1.lng * p2.lat - p2.lng * p1.lat;
    twicearea += f;
    x += (p1.lng + p2.lng) * f;
    y += (p1.lat + p2.lat) * f;
  }
  f = twicearea * 3;
  return {
    lng: x / f,
    lat: y / f
  };
}

var data = [{
  lat: -37.81418,
  lng: 145.13025000000002
}, {
  lat: -37.814330000000005,
  lng: 145.13022
}, {
  lat: -37.813970000000005,
  lng: 145.12727
}, {
  lat: -37.813750000000006,
  lng: 145.12543000000002
}, {
  lat: -37.813680000000005,
  lng: 145.12478000000002
}, {
  lat: -37.81152,
  lng: 145.12517000000003
}, {
  lat: -37.809380000000004,
  lng: 145.12558
}, {
  lat: -37.80951,
  lng: 145.12675000000002
}, {
  lat: -37.80953,
  lng: 145.12685000000002
}, {
  lat: -37.810590000000005,
  lng: 145.12667000000002
}, {
  lat: -37.812630000000006,
  lng: 145.12631000000002
}, {
  lat: -37.81275,
  lng: 145.12628
}, {
  lat: -37.81324,
  lng: 145.13026000000002
}, {
  lat: -37.81326,
  lng: 145.13044000000002
}, {
  lat: -37.81418,
  lng: 145.13025000000002
}]
html,
body,
#map_canvas {
  height: 100%;
  width: 100%;
  margin: 0px;
  padding: 0px
}
<script src="https://maps.googleapis.com/maps/api/js?libraries=geometry"></script>
<div id="map_canvas"></div>