I am new to javascript and working with google maps API for javascript.
This is an asignment for school and we were provided with a working script and some php code to display a map, get the position, update the position and so on.
Our task is to implement a convex hull algorithm.
These are the things I'm having problems with:
Here's the code;
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));
}
}
My main lookslike this;
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 © <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]
Basicly what I want to know first is why var final_list has a structure [Object, Object, Object, Object, Object] (what the console outputs)
Because I get this error: Uncaught TypeError: Cannot read property 'length' of undefined at DrawHull
I think I implemented the algorithm in a correct way, but I can't test it out.
If you need additional info don't hesitate to ask, tips on how to make this question better are also welcome [this is my first question! So take that into consideration and be kind while providing constructive feedback]
I ended up fixing it myself and taught it was a good idea to answer my own question so that if people stumble uppon this they have an answer :)
Here's the code:
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);
}