I am having issues creating a complex Convex Hull. If I change to s simple polygon with 10 points or so, it works great, but when I have 20-30 points over a large area, it creates a "split" in the polygon. Whereas the math says it should be looking for all the outliers, and using them as "hull points". I am wondering if my math is incorrect, or if this is a JavaScript fluke?
As a reference, here is the site where I gleaned the mathematics and sample code snippet from: The Convex Hull of a Planar Point Set
This is as stripped-down as I can get it while still being functional as a stand alone 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: 10,
center: new google.maps.LatLng( 41.024767, -74.122642),
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);
points = [
new google.maps.LatLng(41.0247669,-74.1226425),
new google.maps.LatLng(41.0410868,-74.13484609999999),
new google.maps.LatLng(41.0238951,-74.13282749999999),
new google.maps.LatLng(41.0309834,-74.1264094),
new google.maps.LatLng(41.0252598,-74.155237),
new google.maps.LatLng(40.9419984,-73.9405831),
new google.maps.LatLng(40.9518704,-73.9264803),
new google.maps.LatLng(40.9530188,-73.9344715),
new google.maps.LatLng(40.6771541,-74.1165864),
new google.maps.LatLng(40.6586571,-74.12123179999999),
new google.maps.LatLng(40.8025724,-74.1505466),
new google.maps.LatLng(40.78835,-74.17700169999999),
new google.maps.LatLng(40.8024772,-74.1492507),
new google.maps.LatLng(40.7995324,-74.1508104),
new google.maps.LatLng(40.7954599,-74.1443422),
new google.maps.LatLng(40.917345,-73.9939529),
new google.maps.LatLng(40.9256096,-74.0012066),
new google.maps.LatLng(40.9114334,-74.0070829),
new google.maps.LatLng(40.9251857,-73.99491619999999),
new google.maps.LatLng(40.923538,-73.9888347),
new google.maps.LatLng(40.9356149,-74.0044661),
new google.maps.LatLng(40.9336639,-74.0126835),
new google.maps.LatLng(40.9168748,-74.0047416),
new google.maps.LatLng(40.9235845,-73.99615659999999),
new google.maps.LatLng(40.9346191,-73.9895914),
new google.maps.LatLng(40.9169838,-74.0046957),
new google.maps.LatLng(40.9319544,-74.0109391),
new google.maps.LatLng(40.924245,-74.00189530000002),
new google.maps.LatLng(40.9247537,-74.0057516),
new google.maps.LatLng(40.936268,-73.99291699999999),
new google.maps.LatLng(40.9354675,-74.00451199999999),
new google.maps.LatLng(40.9336023,-73.9827045),
new google.maps.LatLng(40.9173526,-73.9930577),
new google.maps.LatLng(40.9249738,-73.9951007),
new google.maps.LatLng(40.9114631,-74.0059352),
new google.maps.LatLng(40.9197391,-74.0056024),
new google.maps.LatLng(40.9147328,-74.0110768),
new google.maps.LatLng(40.9357446,-74.0051089),
new google.maps.LatLng(40.9206033,-74.002538),
new google.maps.LatLng(40.9247956,-74.0014362),
new google.maps.LatLng(40.9302183,-73.9943661),
new google.maps.LatLng(40.9320254,-74.0052007),
new google.maps.LatLng(40.6714401,-74.5352054),
new google.maps.LatLng(40.9356751,-73.9807761),
new google.maps.LatLng(40.922373,-73.9908769),
new google.maps.LatLng(40.9317953,-73.9832555),
new google.maps.LatLng(40.9337966,-74.0087355)
];
for (var i = 0; i < points.length; i++) {
console.log ( points[i] + ", " + i);
var marker = createMarker(points[i], i);
gmarkers.push(marker);
}
calculateConvexHull();
});
google.maps.event.addListener(map, "click", function (evt) {
if (evt.latLng) {
var latlng = evt.latLng;
// alert("latlng:"+latlng.toUrlValue());
var marker = createMarker(latlng, gmarkers.length - 1);
points.push(latlng);
gmarkers.push(marker);
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
});
return marker;
}
function calculateConvexHull() {
if (polyline) polyline.setMap(null);
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() {
for (var i = 0; i < hullPoints.length; i++) {
document.getElementById("hull_points").innerHTML += hullPoints[i].toUrlValue() + "<br>";
}
}
function sortPointX(a, b) {
return a.lng() - b.lng();
}
function sortPointY(a, b) {
return a.lat() - b.lat();
}
function isLeft(P0, P1, P2) {
return (P1.lng() - P0.lng()) * (P2.lat() - P0.lat()) - (P2.lng() - P0.lng()) * (P1.lat() - P0.lat());
}
function chainHull_2D(P, n, H) {
// the output array H[] will be used as the stack
var bot = 0,
top = (-1); // indices for bottom and top of the stack
var i; // array scan index
// Get the indices of points with min x-coord and min|max y-coord
var minmin = 0,
minmax;
var xmin = P[0].lng();
for (i = 1; i < n; i++) {
if (P[i].lng() !== xmin) {
break;
}
}
minmax = i - 1;
if (minmax === n - 1) { // degenerate case: all x-coords == xmin
H[++top] = P[minmin];
if (P[minmax].lat() !== P[minmin].lat()) { // a nontrivial segment
H[++top] = P[minmax];
H[++top] = P[minmin]; // add polygon endpoint
}
return top + 1;
}
// Get the indices of points with max x-coord and min|max y-coord
var maxmin, maxmax = n - 1;
var xmax = P[n - 1].lng();
for (i = n - 2; i >= 0; i--) {
if (P[i].lng() !== xmax) {
break;
}
}
maxmin = i + 1;
// Compute the lower hull on the stack H
H[++top] = P[minmin]; // push minmin point onto stack
i = minmax;
while (++i <= maxmin) {
// the lower line joins P[minmin] with P[maxmin]
if (isLeft(P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin) {
continue; // ignore P[i] above or on the lower line
}
while (top > 0) { // there are at least 2 points on the stack
// test if P[i] is left of the line at the stack top
if (isLeft(H[top - 1], H[top], P[i]) > 0) {
break; // P[i] is a new hull vertex
}
else {
top--; // pop top point off stack
}
}
H[++top] = P[i]; // push P[i] onto stack
}
// Next, compute the upper hull on the stack H above the bottom hull
if (maxmax !== maxmin) { // if distinct xmax points
H[++top] = P[maxmax]; // push maxmax point onto stack
}
bot = top; // the bottom point of the upper hull stack
i = maxmin;
while (--i >= minmax) {
// the upper line joins P[maxmax] with P[minmax]
if (isLeft(P[maxmax], P[minmax], P[i]) >= 0 && i > minmax) {
continue; // ignore P[i] below or on the upper line
}
while (top > bot) { // at least 2 points on the upper stack
// test if P[i] is left of the line at the stack top
if (isLeft(H[top - 1], H[top], P[i]) > 0) {
break; // P[i] is a new hull vertex
}
else {
top--; // pop top point off stack
}
}
H[++top] = P[i]; // push P[i] onto stack
}
if (minmax !== minmin) {
H[++top] = P[minmin]; // push joining endpoint onto stack
}
return top + 1;
}<script src="https://maps.googleapis.com/maps/api/js"></script>
<body onload="initialize()">
<div id="map_canvas" style="width: 100%; height: 500px"></div>
<div id="hull_points" style="float:left; padding:10px; height:200px; overflow-y:scroll">
HULL POINTS <hr>
</div>As you can see, the points will work with a small group of plot points, but why is JavaScript getting confused and not just plotting the outliers, why is it going into the polygon and back out again?
That's quite a lot of code to debug...
You might want to have a look at this library and this example implementation which as per the repository is an implementation of the Graham's Scan Convex Hull algorithm in JavaScript.
It looks like the result is what you want to achieve.
I found version 1.0.4 available here: https://cdn.jsdelivr.net/npm/graham_scan@1.0.4/graham_scan.min.js and the repo has version 1.0.5 so it might be better to use a local copy.
Working code snippet below, with the coords provided in your question:
function initialize() {
var coords = [{
'lat': 41.0247669,
'lon': -74.1226425
},
{
'lat': 41.0410868,
'lon': -74.13484609999999
},
{
'lat': 41.0238951,
'lon': -74.13282749999999
},
{
'lat': 41.0309834,
'lon': -74.1264094
},
{
'lat': 41.0252598,
'lon': -74.155237
},
{
'lat': 40.9419984,
'lon': -73.9405831
},
{
'lat': 40.9518704,
'lon': -73.9264803
},
{
'lat': 40.9530188,
'lon': -73.9344715
},
{
'lat': 40.6771541,
'lon': -74.1165864
},
{
'lat': 40.6586571,
'lon': -74.12123179999999
},
{
'lat': 40.8025724,
'lon': -74.1505466
},
{
'lat': 40.78835,
'lon': -74.17700169999999
},
{
'lat': 40.8024772,
'lon': -74.1492507
},
{
'lat': 40.7995324,
'lon': -74.1508104
},
{
'lat': 40.7954599,
'lon': -74.1443422
},
{
'lat': 40.917345,
'lon': -73.9939529
},
{
'lat': 40.9256096,
'lon': -74.0012066
},
{
'lat': 40.9114334,
'lon': -74.0070829
},
{
'lat': 40.9251857,
'lon': -73.99491619999999
},
{
'lat': 40.923538,
'lon': -73.9888347
},
{
'lat': 40.9356149,
'lon': -74.0044661
},
{
'lat': 40.9336639,
'lon': -74.0126835
},
{
'lat': 40.9168748,
'lon': -74.0047416
},
{
'lat': 40.9235845,
'lon': -73.99615659999999
},
{
'lat': 40.9346191,
'lon': -73.9895914
},
{
'lat': 40.9169838,
'lon': -74.0046957
},
{
'lat': 40.9319544,
'lon': -74.0109391
},
{
'lat': 40.924245,
'lon': -74.00189530000002
},
{
'lat': 40.9247537,
'lon': -74.0057516
},
{
'lat': 40.936268,
'lon': -73.99291699999999
},
{
'lat': 40.9354675,
'lon': -74.00451199999999
},
{
'lat': 40.9336023,
'lon': -73.9827045
},
{
'lat': 40.9173526,
'lon': -73.9930577
},
{
'lat': 40.9249738,
'lon': -73.9951007
},
{
'lat': 40.9114631,
'lon': -74.0059352
},
{
'lat': 40.9197391,
'lon': -74.0056024
},
{
'lat': 40.9147328,
'lon': -74.0110768
},
{
'lat': 40.9357446,
'lon': -74.0051089
},
{
'lat': 40.9206033,
'lon': -74.002538
},
{
'lat': 40.9247956,
'lon': -74.0014362
},
{
'lat': 40.9302183,
'lon': -73.9943661
},
{
'lat': 40.9320254,
'lon': -74.0052007
},
{
'lat': 40.6714401,
'lon': -74.5352054
},
{
'lat': 40.9356751,
'lon': -73.9807761
},
{
'lat': 40.922373,
'lon': -73.9908769
},
{
'lat': 40.9317953,
'lon': -73.9832555
},
];
var centrePoint = new google.maps.LatLng(0,0);
var mapOptions = {
zoom: 9,
center: centrePoint,
mapTypeId: google.maps.MapTypeId.ROADMAP
};
var map = new google.maps.Map(document.getElementById('map-canvas'), mapOptions);
var poly;
var polyHull;
var convexHull = new ConvexHullGrahamScan();
poly = new google.maps.Polygon({
paths: coords.map(function(item) {
return new google.maps.LatLng(item.lat, item.lon);
}),
strokeColor: '#000',
strokeOpacity: 0.2,
strokeWeight: 2,
fillColor: '#000',
fillOpacity: 0.1
});
var bounds = new google.maps.LatLngBounds();
coords.forEach(function(item) {
var marker = new google.maps.Marker({
position: new google.maps.LatLng(item.lat, item.lon),
map: map
});
convexHull.addPoint(item.lon, item.lat);
bounds.extend(new google.maps.LatLng(item.lat, item.lon));
});
if (convexHull.points.length > 0) {
var hullPoints = convexHull.getHull();
//Convert to google latlng objects
hullPoints = hullPoints.map(function(item) {
return new google.maps.LatLng(item.y, item.x);
});
console.log(hullPoints);
polyHull = new google.maps.Polygon({
paths: hullPoints,
strokeColor: '#000',
strokeOpacity: 0.8,
strokeWeight: 2,
fillColor: '#000',
fillOpacity: 0.35
});
polyHull.setMap(map);
map.fitBounds(bounds);
}
}#map-canvas {
height: 180px;
}<div id="map-canvas"></div>
<script src="https://cdn.jsdelivr.net/npm/graham_scan@1.0.4/graham_scan.min.js"></script>
<!-- Replace the value of the key parameter with your own API key. -->
<script async defer src="//maps.googleapis.com/maps/api/js?key=AIzaSyCkUOdZ5y7hMm0yrcCQoCvLwzdM6M8s5qk&callback=initialize">
</script>