Vanilla JavaScript Convex Hull 在 Google 地图上意外的多边形形状
Vanilla JavaScript Convex Hull unexpected polygon shape on Google maps
我在创建复杂的凸包时遇到问题。如果我更改为具有 10 个左右点的简单多边形,效果很好,但是当我在大面积上有 20-30 个点时,它会在多边形中创建一个“拆分”。而数学表明它应该寻找所有异常值,并将它们用作“船体点”。我想知道我的数学是否不正确,或者这是 JavaScript 侥幸?
作为参考,这是我从中收集数学和示例代码片段的网站:The Convex Hull of a Planar Point Set
这是我所能得到的最精简的内容,同时仍可作为独立的代码段使用。
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>
如您所见,这些点将与一小组绘图点一起使用,但为什么 JavaScript 变得困惑而不仅仅是绘制异常值,为什么它会 进入 多边形并再次退出?
要调试的代码太多了...
您可能想看看 this library and this example implementation,根据存储库,它是 JavaScript 中 Graham 扫描凸包算法的一个实现。
看起来结果就是你想要达到的结果。
我在此处找到了 1.0.4
版本:https://cdn.jsdelivr.net/npm/graham_scan@1.0.4/graham_scan.min.js 并且该存储库具有 1.0.5
版本,因此最好使用本地副本。
下面的工作代码片段,以及您问题中提供的坐标:
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>
我在创建复杂的凸包时遇到问题。如果我更改为具有 10 个左右点的简单多边形,效果很好,但是当我在大面积上有 20-30 个点时,它会在多边形中创建一个“拆分”。而数学表明它应该寻找所有异常值,并将它们用作“船体点”。我想知道我的数学是否不正确,或者这是 JavaScript 侥幸?
作为参考,这是我从中收集数学和示例代码片段的网站:The Convex Hull of a Planar Point Set
这是我所能得到的最精简的内容,同时仍可作为独立的代码段使用。
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>
如您所见,这些点将与一小组绘图点一起使用,但为什么 JavaScript 变得困惑而不仅仅是绘制异常值,为什么它会 进入 多边形并再次退出?
要调试的代码太多了...
您可能想看看 this library and this example implementation,根据存储库,它是 JavaScript 中 Graham 扫描凸包算法的一个实现。
看起来结果就是你想要达到的结果。
我在此处找到了 1.0.4
版本:https://cdn.jsdelivr.net/npm/graham_scan@1.0.4/graham_scan.min.js 并且该存储库具有 1.0.5
版本,因此最好使用本地副本。
下面的工作代码片段,以及您问题中提供的坐标:
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>