在 google 地图上画一个凸包

Question

我是 javascript 的新手，正在为 javascript 使用 google 地图 API。

这是学校的作业，我们得到了一个工作脚本和一些 php 代码来显示地图、获取位置、更新位置等。

我们的任务是实现一个凸包算法。

这些是我遇到的问题：

一些对象的数据结构
如何在我计算出船体线后在地图上显示它们

这是代码；

function convexHull(){
    console.log("convexHull()");
    console.log(obj.length);
    //check if there are more than one user, otherwise convex hull calculation would be useless
    if(obj.length > 0){
        //lists with x-positions and y-positions
        var pos_x = [];
        var pos_y = [];
        //fill the lists
        for(var i = 0;i < obj.length; i++){
            pos_y.push(parseFloat(obj[i][1]));
            pos_x.push(parseFloat(obj[i][2]));
            console.log("point " + i + ": lat = " + pos_y[i] + ", lon = " + pos_x[i]);
        }
        //find lowest point index
        var low_index = 0
        for(var i = 1;i < obj.length; i++){
            if(pos_y[i] < pos_y[low_index]){
                low_index = i
            }
        }
        var angle_list = []
        //make list of angles linked to index, the lowest point will not be in this list
        for(var i = 0;i < obj.length; i++){
            if(i != low_index){
                var opos = pos_y[i] - pos_y[low_index];
                var adj = pos_x[i] - pos_x[low_index];
                //opos will always be positive, since the point with index low_index is the lowest point
                if(adj > 0){
                    var new_angle = Math.atan(opos/adj);
                    var list_item = {index:i, angle:new_angle};
                    angle_list.push(list_item);
                }
                if(adj < 0){
                    var new_angle = Math.atan(opos/adj)+ Math.PI;
                    var list_item = {index:i, angle:new_angle};
                    angle_list.push(list_item);
                }
                if(adj == 0){ //if adj = 0, angle is 90 degrees
                    var new_angle = 90;
                    var list_item = {index:i, angle:new_angle};
                    angle_list.push(list_item);
                }
            }
        }
        //sort angle_list by ascending angles
        angle_list = angle_list.sort(function(a,b){return a.angle - b.angle;});
        for(var i=0;i< angle_list.length;i++){
            console.log("angle = " + angle_list[i].angle + ", index = " + angle_list[i].index);
        }
        //GRAHAM ALGORITHM STARTS HERE
        //this list will hold all indexes of convex points
        var final_list  = [];
        //put the lowest point in the angle_list
        var list_item = {index:low_index, angle:0};
        angle_list.unshift(list_item);

        //NEW STUFF HERE
        //eerst het beginpunt met laagste y-coor invoegen
        //english: inserting the starting point [lowest y coordinate]
        final_list.unshift(angle_list[0]);
        for(var i=2;i<angle_list.length;i++){
            var value = (((pos_x[angle_list[i-1].index]-pos_x[angle_list[i-2].index])*(pos_y[angle_list[(i)].index]-pos_y[angle_list[i-2].index]))-((pos_y[angle_list[i-1].index]-pos_y[angle_list[i-2].index])*(pos_x[angle_list[(i)].index]-pos_x[angle_list[i-2].index])));
            //left turn, this is good
            if(value > 0){
                console.log("left turn");
                final_list.push(angle_list[i-1]);
            }
            //right turn, this is not good
            if(value < 0){
                console.log("right turn");
                continue;
            }
            //points lie on a line
            if(value == 0){
                final_list.push(angle_list[i-1]);
                console.log("colinear");
            }
        }
    }       
    setTimeout(function(){convexHull();}, 5000);
    console.log(final_list);//this is what the console outputs: [Object, Object, Object, Object, Object] I don't understand why it has this structure!
    return final_list;
}
function DrawHull(final_list){
    for(var i = 0; i < final_list.length-1; i++){
        console.log(parseFloat(obj[final_list[i]]));
        var p1 = new L.LatLng(parseFloat(obj[final_list[i]][1]),parseFloat(obj[final_list[i]][2]));
        var p2 = new L.LatLng(parseFloat(obj[final_list[i+1]][1]),parseFloat(obj[final_list[i+1]][2]));
        var pointList = [p1, p2];
        polylines.push(new L.polyline(pointList, {
            color: 'yellow',
            weight: 10,
            opacity: 0.5,
            smoothFactor: 1
        }).addTo(mymap));
    }
}

我的主图是这样的；

getLocation();


var mymap = L.map('mapid').setView([51.0336851,3.7019778], 13);
L.tileLayer('https://api.tiles.mapbox.com/v4/{id}/{z}/{x}/{y}.png?access_token={accessToken}', {
    attribution: 'Map data &copy; <a href="http://openstreetmap.org">OpenStreetMap</a> contributors, <a href="http://creativecommons.org/licenses/by-sa/2.0/">CC-BY-SA</a>, Imagery © <a href="http://mapbox.com">Mapbox</a>',
    maxZoom: 18,
    id: 'mapbox.streets',
    accessToken: //I deleted this, I figured it should stay private
}).addTo(mymap);

  DrawHull(convexHull()); //These two funcions and this line are the only things I wrote with my classmate [and his code is based on some code he found on the web and adjusted to our needs]

基本上我首先想知道的是为什么 var final_list 有一个结构 [Object, Object, Object, Object, Object] （控制台输出的内容）

因为我得到这个错误：Uncaught TypeError: Cannot read 属性 'length' of undefined at DrawHull

我认为我以正确的方式实现了算法，但我无法对其进行测试。

如果您需要更多信息，请随时提出，也欢迎提供有关如何更好地解决此问题的提示[这是我的第一个问题！因此，请在提供建设性反馈的同时考虑到这一点并保持友善]

Answer 1

我最终自己修复了它，并告诉我回答我自己的问题是个好主意，这样如果人们偶然发现这个问题，他们就会得到答案:)

代码如下：

function convexHull(){
    console.log("convexHull()");
    console.log(obj.length);
    //check if there are more than one user, otherwise convex hull calculation would be useless
    if(obj.length > 0){
        //lists with x-positions and y-positions
        var pos_x = [];
        var pos_y = [];
        //fill the lists
        for(var i = 0;i < obj.length; i++){
            pos_y.push(parseFloat(obj[i][1]));
            pos_x.push(parseFloat(obj[i][2]));
            console.log("point " + i + ": lat = " + pos_y[i] + ", lon = " + pos_x[i]);
        }
        //find lowest point index
        var low_index = 0
        for(var i = 1;i < obj.length; i++){
            if(pos_y[i] < pos_y[low_index]){
                low_index = i
            }
        }
        var angle_list = []
        //make list of angles linked to index, the lowest point will not be in this list
        for(var i = 0;i < obj.length; i++){
            if(i != low_index){
                var opos = pos_y[i] - pos_y[low_index];
                var adj = pos_x[i] - pos_x[low_index];
                //opos will always be positive, since the point with index low_index is the lowest point
                if(adj > 0){
                    var new_angle = Math.atan(opos/adj);
                    var list_item = {index:i, angle:new_angle};
                    angle_list.push(list_item);
                }
                if(adj < 0){
                    var new_angle = Math.atan(opos/adj)+ Math.PI;
                    var list_item = {index:i, angle:new_angle};
                    angle_list.push(list_item);
                }
                if(adj == 0){ //if adj = 0, angle is 90 degrees
                    var new_angle = 90;
                    var list_item = {index:i, angle:new_angle};
                    angle_list.push(list_item);
                }
            }
        }
        //sort angle_list bij ascending angles
        angle_list = angle_list.sort(function(a,b){return a.angle - b.angle;});
        for(var i=0;i< angle_list.length;i++){
            console.log("angle = " + angle_list[i].angle + ", index = " + angle_list[i].index);
        }
        //GRAHAM ALGORITHM STARTS HERE
        //this list will hold all indexes of convex points
        var final_list  = [];
        //put the lowest point in the angle_list
        var list_item = {index:low_index, angle:0};
        angle_list.unshift(list_item);

        //NEW STUFF HERE
        //eerst het beginpunt met laagste y-coor invoegen
        final_list.unshift(angle_list[0]);
        for(var i=2;i<angle_list.length;i++){
            var value = (((pos_x[angle_list[i-1].index]-pos_x[angle_list[i-2].index])*(pos_y[angle_list[(i)].index]-pos_y[angle_list[i-2].index]))-((pos_y[angle_list[i-1].index]-pos_y[angle_list[i-2].index])*(pos_x[angle_list[(i)].index]-pos_x[angle_list[i-2].index])));
            //left turn, this is good
            if(value > 0){
                console.log("left turn");
                final_list.push(angle_list[i-1]);
                if(i==angle_list.length-1)final_list.push(angle_list[i]);
            }
            //right turn, this is not good
            if(value < 0){
                console.log("right turn");
                continue;
            }
            //points lie on a line
            if(value == 0){
                final_list.push(angle_list[i-1]);
                console.log("colinear");
            }
        }
    }       
    console.log(final_list);//dit is de output: [Object, Object, Object, Object, Object]
    console.log("final_list length: " + Object.keys(final_list).length);
    console.log("Drawing the hull now\n");
    //console.log("obj:" + obj + "\n");
    for(var i = 0; i < Object.keys(final_list).length-1; i++){
        //console.log("obj[final_list[i].index]\n" + parseFloat(obj[final_list[i].index]));
        var p1 = new L.LatLng(parseFloat(obj[final_list[i].index][1]),parseFloat(obj[final_list[i].index][2]));
        var p2 = new L.LatLng(parseFloat(obj[final_list[i+1].index][1]),parseFloat(obj[final_list[i+1].index][2]));
        var pointList = [p1, p2];
        //adding the last line to close the hull
        if(i == Object.keys(final_list).length-2){
            console.log("laatste punt bereikt");
            var p1 = new L.LatLng(parseFloat(obj[final_list[i+1].index][1]),parseFloat(obj[final_list[i+1].index][2]));
            var p2 = new L.LatLng(parseFloat(obj[final_list[0].index][1]),parseFloat(obj[final_list[0].index][2]));//start
            var pointList = [p1, p2];
        }
        polylines.push(new L.polyline(pointList, {
            color: 'yellow',
            weight: 5,
            opacity: 0.5,
            smoothFactor: 1
        }).addTo(mymap));
    }
    setTimeout(function(){convexHull();}, 5000);
    //L.polyline.setMap(null);
}

在 google 地图上画一个凸包

Draw a convex hull on a google map

javascript

php

grahams-scan