Vanilla JavaScript Convex Hull неожиданная форма многоугольника на картах Google - PullRequest
Новая
       49

Vanilla JavaScript Convex Hull неожиданная форма многоугольника на картах Google

1 голос
/ 21 февраля 2020

У меня проблемы с созданием сложного выпуклого корпуса. Если я перехожу на простой многоугольник с 10 или около того точками, он прекрасно работает, но когда у меня 20-30 точек на большой площади, это создает «расщепление» в многоугольнике. В то время как математика говорит, что она должна искать все выбросы и использовать их в качестве «точек корпуса». Мне интересно, если моя математика неверна, или это JavaScript случайность?

Для справки, вот сайт, где я почерпнул фрагмент математики и пример кода из: Выпуклая оболочка планарного набора точек

Это настолько урезанный, насколько я могу себе представить, оставаясь при этом функциональным в качестве отдельного фрагмента. -> 

        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 запутывается, а не просто отображает выбросы, почему он входит в многоугольник и возвращается обратно?

1 Ответ

0 голосов
/ 21 февраля 2020

Это достаточно много кода для отладки ...

Возможно, вы захотите взглянуть на эту библиотеку и в этом примере реализации , которая согласно репозиторий является реализацией алгоритма Грэхема Scan Convex Hull в JavaScript.

Похоже, что результат - это то, чего вы хотите достичь.

Я нашел версию 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>
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...