brian3kb / graham_scan_js Goto Github PK
View Code? Open in Web Editor NEWAn implementation of the Graham's Scan Convex Hull algorithm in JavaScript.
Home Page: http://brian3kb.github.io/graham_scan_js
License: Other
An implementation of the Graham's Scan Convex Hull algorithm in JavaScript.
Home Page: http://brian3kb.github.io/graham_scan_js
License: Other
I provide the following input to the implementation:
{{466, 231}, {469, 228}, {472, 226}, {476, 223}, {479, 221}, {483, 219}, {486, 216}, {489, 214},
{492, 211}, {495, 209}, {499, 207}, {503, 205}, {506, 203}, {510, 201}, {513, 200},
{517, 199}, {521, 197}, {525, 196}, {529, 194}, {532, 193}, {536,191}, {540, 190},
{544, 189}, {548, 188}, {552, 187}, {556, 187}, {563, 185}, {567, 184}, {571, 184},
{575, 183}, {579, 183}, {583, 183}, {587, 183}, {591, 183}, {595, 184}, {599, 185},
{602, 187}, {606, 189}, {610, 191}, {613, 193}, {617,195}, {620, 198}, {623, 200},
{627, 202}, {629, 205}, {633, 207}, {636, 210}, {639, 213}, {642, 215}, {647, 219},
{650, 222}, {653, 225}, {656, 228}, {658, 231}, {661, 234}, {663, 237}, {666, 240},
{667, 244}, {669, 248}, {671, 251}, {673, 252}, {674, 256}, {675, 258}}
which is a noisy (but recognizable) trace of an arc.
The output is as follows:
{{466, 231}, {469, 228}, {492, 211}, {489, 214}, {483, 219}, {503, 205}, {506, 203}, {510, 201},
{536, 191}, {552, 187}, {556, 187}, {563, 185}, {567, 184}, {571, 184}, {575, 183}, {591,183},
{599, 185}, {610, 191}, {617, 195}, {627, 202}, {633, 207}, {647, 219}, {656, 228}, {666, 240},
{673, 252}, {675, 258}}
which is not convex and moreover contains some "weird" points. See the picture below: black dashed line is the trace constituting the set of point to enclose, blue solid --- the hull
I'm getting incorrect results when I have the following input:
var coords = [
{x: -3.1312142384552426, y: -59.98758316040039},
{x: -3.1192346653000658, y: -59.99200478196144},
{x: -3.1373816234054686, y: -59.97942924499512},
{x: -3.129282748966514, y: -59.99665975570679}
];
This comes as result:
x: -3.1373816234054686,
y: -59.97942924499512
x: -3.129282748966514,
y: -59.99665975570679
This is how it looks like in a map:
And this is the expected result:
I'm using version 1.0.5
I ran the following sample data through the library:
var graham_scan = require('graham_scan');
var gscan = new graham_scan();
gscan.addPoint(2, 2);
gscan.addPoint(2, -2);
gscan.addPoint(-2, -2);
gscan.addPoint(-2, 2);
gscan.addPoint(3, 3);
gscan.addPoint(3, -3);
gscan.addPoint(-3, -3);
gscan.addPoint(-3, 3);
gscan.addPoint(4, 4);
gscan.addPoint(4, -4);
gscan.addPoint(-4, -4);
gscan.addPoint(-4, 4);
gscan.addPoint(5, 5);
gscan.addPoint(-5, 5);
gscan.addPoint(-5, -5);
gscan.addPoint(5, -5);
var hull = gscan.getHull();
for (var i = 0; i < hull.length; i++)
{
console.log(i, hull[i]);
};
I expected the hull to contain only the four green points as depicted below and was surprised to the see the four additional points in red and a non-ccw ordering:
Hull Results
After a small amount of research it seems plausible that this occurs because these points are collinear and share the same polar angle with the anchor point but part of me worries that with such a simple failing case I'm just confused with the setup, limitations or use of the library or problem space. If the later is the issue, please close and disregard.
Hi,
I was using your code to test convex hull for some points and got it wrong.
I change L66 on graham_scan from
"if (angle > 0) {" to "if (angle < 0) {"
and them it works.
I'm sending my points for you to test.
-19.909134,-43.951838;
-19.909453,-43.951822;
-19.909564,-43.952082;
-19.909923,-43.952578;
-19.909723,-43.952738;
-19.909943,-43.952844;
-19.91011,-43.953016;
-19.910004,-43.953185;
-19.91009,-43.953567;
-19.91042,-43.953295;
-19.910397,-43.952985;
-19.910472,-43.952794;
-19.910648,-43.953102;
-19.910807,-43.952894;
-19.91116,-43.952878;
-19.911679,-43.952534;
-19.911509,-43.952155;
-19.911337,-43.95231;
-19.911167,-43.952136;
-19.911099,-43.952459;
-19.910926,-43.952563;
-19.910733,-43.952234;
-19.910537,-43.95229;
-19.910503,-43.95251;
-19.910335,-43.952121;
-19.909931,-43.952002
:)
Could you publish you package on npm?
Please publish the project to Bower as I'm currently using it in FreeDraw for gutting the polygons.
Your code is not working correctly for rectangle shapes with 4 points.
Try first this coordinates
var coords = [
{'lat' : '50.157913235507706', 'lon' : '29.900512524414125'},
{'lat' : '50.74029471119741', 'lon' : '31.146087475586'},
{'lat' : '50.74029471119741', 'lon' : '29.900512524414125'},
{'lat' : '50.15791323550770611', 'lon' : '31.146087475586'}
];
var centrePoint = new google.maps.LatLng(50.5, 30.0);
This example works incorrectly
And than change a little last point lat. F.e.
{'lat' : '50.17791323550770611', 'lon' : '31.146087475586'}
This one is good
Hi.. I'm having some problems with the resulting convex hull points returned by getHull()
.
These are the points after adding with addPoint(x, y)
:
0:ConvexHullGrahamScan.Point
x:8.48206
y:52.45522
1:ConvexHullGrahamScan.Point
x:8.2489553
y:52.67141
2:ConvexHullGrahamScan.Point
x:8.28255
y:52.6787
3:ConvexHullGrahamScan.Point
x:8.2718435
y:52.7555779
4:ConvexHullGrahamScan.Point
x:7.41582
y:53.11456
5:ConvexHullGrahamScan.Point
x:11.62771
y:52.08609
And the resulting hull points:
0:ConvexHullGrahamScan.Point
x:8.2489553
y:52.67141
1:ConvexHullGrahamScan.Point
x:8.48206
y:52.45522
2:ConvexHullGrahamScan.Point
x:8.2718435
y:52.7555779
3:ConvexHullGrahamScan.Point
x:7.41582
y:53.11456
but it must be like this (green line):
I hope you can fix it soon.
Thanks in advance.
[
{
"lng": -89.04826539999999,
"lat": 40.4572814
},
{
"lng": -89.04826539999999,
"lat": 40.4572814
},
{
"lng": -89.04632170000001,
"lat": 40.4528266
},
{
"lng": -89.0462646,
"lat": 40.4524364
},
{
"lng": -89.0462652,
"lat": 40.4521928
},
{
"lng": -89.0461206,
"lat": 40.45196019999999
},
{
"lng": -89.0460007,
"lat": 40.4516839
},
{
"lng": -89.045872,
"lat": 40.4514006
},
{
"lng": -89.0460978,
"lat": 40.4530237
},
{
"lng": -89.04557539999999,
"lat": 40.4529
},
{
"lng": -89.045594,
"lat": 40.4526814
},
{
"lng": -89.04566489999999,
"lat": 40.4523262
},
{
"lng": -89.04552729999999,
"lat": 40.4520635
},
{
"lng": -89.0454006,
"lat": 40.4518228
},
{
"lng": -89.04035069999999,
"lat": 40.4511462
},
{
"lng": -89.03999619999999,
"lat": 40.4512826
},
{
"lng": -89.04089189999999,
"lat": 40.4515287
},
{
"lng": -89.0401569,
"lat": 40.4516308
},
{
"lng": -89.0410225,
"lat": 40.4512711
},
{
"lng": -89.0440267,
"lat": 40.4530663
},
{
"lng": -89.0434483,
"lat": 40.4528427
},
{
"lng": -89.04296169999999,
"lat": 40.45276339999999
},
{
"lng": -89.04245619999999,
"lat": 40.4526677
},
{
"lng": -89.0419369,
"lat": 40.4525717
},
{
"lng": -89.0410412,
"lat": 40.452246
},
{
"lng": -89.04081719999999,
"lat": 40.4520054
},
{
"lng": -89.0440267,
"lat": 40.4533845
},
{
"lng": -89.0426086,
"lat": 40.4532137
},
{
"lng": -89.0422354,
"lat": 40.4531311
},
{
"lng": -89.04178759999999,
"lat": 40.4530478
},
{
"lng": -89.0413397,
"lat": 40.45296460000001
},
{
"lng": -89.0409852,
"lat": 40.452902
},
{
"lng": -89.0406493,
"lat": 40.45274
},
{
"lng": -89.04029469999999,
"lat": 40.4524785
},
{
"lng": -89.0401455,
"lat": 40.4522386
},
{
"lng": -89.0452517,
"lat": 40.4514698
},
{
"lng": -89.04486209999999,
"lat": 40.4510384
},
{
"lng": -89.04441849999999,
"lat": 40.4511798
},
{
"lng": -89.044176,
"lat": 40.4510784
},
{
"lng": -89.0440423,
"lat": 40.4506969
},
{
"lng": -89.04353669999999,
"lat": 40.4507898
},
{
"lng": -89.0432398,
"lat": 40.4506543
},
{
"lng": -89.04353669999999,
"lat": 40.4507898
},
{
"lng": -89.0435677,
"lat": 40.4504348
},
{
"lng": -89.04395799999999,
"lat": 40.4502574
},
{
"lng": -89.045814,
"lat": 40.4511397
},
{
"lng": -89.04547749999999,
"lat": 40.4508854
},
{
"lng": -89.0456906,
"lat": 40.4505941
},
{
"lng": -89.0456572,
"lat": 40.4503141
},
{
"lng": -89.0456143,
"lat": 40.4500338
},
{
"lng": -89.0451496,
"lat": 40.4508172
},
{
"lng": -89.0451136,
"lat": 40.4505815
},
{
"lng": -89.0450795,
"lat": 40.4503586
},
{
"lng": -89.0442044,
"lat": 40.4504944
},
{
"lng": -89.044265,
"lat": 40.4503412
},
{
"lng": -89.0481501,
"lat": 40.4509718
},
{
"lng": -89.04124639999999,
"lat": 40.4504773
},
{
"lng": -89.041433,
"lat": 40.45024009999999
},
{
"lng": -89.0416383,
"lat": 40.450023
},
{
"lng": -89.0417129,
"lat": 40.4497054
},
{
"lng": -89.04178759999999,
"lat": 40.44946729999999
},
{
"lng": -89.0418622,
"lat": 40.4491496
},
{
"lng": -89.0409852,
"lat": 40.4507536
},
{
"lng": -89.0404476,
"lat": 40.4502308
},
{
"lng": -89.04081719999999,
"lat": 40.4500162
},
{
"lng": -89.04094789999999,
"lat": 40.4497587
},
{
"lng": -89.0410971,
"lat": 40.4495212
},
{
"lng": -89.0411158,
"lat": 40.449223
},
{
"lng": -89.0411904,
"lat": 40.4489849
},
{
"lng": -89.0411904,
"lat": 40.4486666
},
{
"lng": -89.0392497,
"lat": 40.4488893
},
{
"lng": -89.039399,
"lat": 40.4485722
},
{
"lng": -89.0393244,
"lat": 40.4483329
},
{
"lng": -89.0394737,
"lat": 40.4480159
},
{
"lng": -89.0395297,
"lat": 40.4477577
},
{
"lng": -89.0391751,
"lat": 40.4494457
},
{
"lng": -89.0392262,
"lat": 40.4491256
},
{
"lng": -89.0392497,
"lat": 40.4488893
},
{
"lng": -89.039399,
"lat": 40.4485722
},
{
"lng": -89.0393244,
"lat": 40.4483329
},
{
"lng": -89.0394737,
"lat": 40.4480159
},
{
"lng": -89.0395297,
"lat": 40.4474792
},
{
"lng": -89.03857789999999,
"lat": 40.4496794
},
{
"lng": -89.0391751,
"lat": 40.4494457
}
]
[
{
"x": -89.04826539999999,
"y": 40.4572814
},
{
"x": -89.0481501,
"y": 40.4509718
},
{
"x": -89.0456143,
"y": 40.4500338
},
{
"x": -89.0456906,
"y": 40.4505941
},
{
"x": -89.045872,
"y": 40.4514006
},
{
"x": -89.04632170000001,
"y": 40.4528266
},
{
"x": -89.0450795,
"y": 40.4503586
},
{
"x": -89.0451496,
"y": 40.4508172
},
{
"x": -89.0452517,
"y": 40.4514698
},
{
"x": -89.045594,
"y": 40.4526814
},
{
"x": -89.0442044,
"y": 40.4504944
},
{
"x": -89.0440423,
"y": 40.4506969
},
{
"x": -89.044176,
"y": 40.4510784
},
{
"x": -89.0435677,
"y": 40.4504348
},
{
"x": -89.0432398,
"y": 40.4506543
},
{
"x": -89.0418622,
"y": 40.4491496
},
{
"x": -89.0417129,
"y": 40.4497054
},
{
"x": -89.0416383,
"y": 40.450023
},
{
"x": -89.0395297,
"y": 40.4477577
},
{
"x": -89.0393244,
"y": 40.4483329
},
{
"x": -89.0392497,
"y": 40.4488893
},
{
"x": -89.0434483,
"y": 40.4528427
},
{
"x": -89.0440267,
"y": 40.4533845
},
{
"x": -89.0392262,
"y": 40.4491256
},
{
"x": -89.0391751,
"y": 40.4494457
},
{
"x": -89.0410225,
"y": 40.4512711
},
{
"x": -89.04245619999999,
"y": 40.4526677
},
{
"x": -89.03857789999999,
"y": 40.4496794
},
{
"x": -89.0401455,
"y": 40.4522386
},
{
"x": -89.04029469999999,
"y": 40.4524785
},
{
"x": -89.0406493,
"y": 40.45274
}
]
function ConvexHull(markers) {
// Functions
this.pointArrayToLatLng = function(points) {
var output = [];
for (var i = 0; i < points.length; i++) {
output.push(new google.maps.LatLng(points[i].y, points[i].x));
}
return output;
}
this.getConvexHull = function() {
return hull;
}
// Convenience wrapper
this.setMap = function(map) {
hull.setMap(map);
}
// Set up
var convexHull = new ConvexHullGrahamScan();
for (var i = 0; i < markers.length; i++) {
convexHull.addPoint(markers[i].position.lng(), markers[i].position.lat());
}
var hullPoints = convexHull.getHull();
// Create polygon
var hull = new google.maps.Polygon({
paths: this.pointArrayToLatLng(hullPoints),
strokeColor: '#4285F4',
strokeWeight: 1,
fillColor: '#4285F4',
fillOpacity: 0.4
});
}
Here's another example of the string behavior. The first image is using numbers, and the second uses strings.
I have more extreme examples of unexpected results. The provided example contains a relatively smaller set of data and I wanted to keep the issue simple. Here are some other results I'm seeing. Let me know if having input data for any of these would also be helpful.
It feels like ~50% of the results I'm getting are like this.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.