brian3kb / graham_scan_js Goto Github PK

View Code? Open in Web Editor NEW

113.0 113.0 24.0 51 KB

An implementation of the Graham's Scan Convex Hull algorithm in JavaScript.

Home Page: http://brian3kb.github.io/graham_scan_js

License: Other

JavaScript 94.48% CSS 0.46% HTML 5.06%

graham_scan_js's People

Contributors

Stargazers

Watchers

graham_scan_js's Issues

Unexpected results

Input Data In LatLng - Actual data is google maps markers.

[
    {
        "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
    }
]

Hull results

[
    {
        "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
    }
]

Visual Results

Implementation

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
    });
}

What I've tried

Remove duplicates from input data.
Convert points to strings per #11; seemed to improve the issue in some areas, but make it worst in others. The following image is the same input data using strings.

Here's another example of the string behavior. The first image is using numbers, and the second uses strings.

Notes

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.

Publish on npm

Could you publish you package on npm?

incorrect hull for four points

These four points
[[223.25,30],[214.66796875,53.6015625],[213.79296875,38.6015625],[211.41796875,29.2265625]]
are not reduced to three, which they should be.

Note that the pointer indicates the fourth point, but it does not have a marker in my usecase

Wrong convex hull results

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

the result is this:

but it must be like this (green line):

I hope you can fix it soon.
Thanks in advance.

Unexpected results on inset squares

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

{ x: -5, y: -5 }
{ x: 5, y: -5 }
{ x: 3, y: 3 } *
{ x: 2, y: 2 } *
{ x: -4, y: -4 } *
{ x: -3, y: -3 } *
{ x: 5, y: 5 }
{ x: -5, y: 5 }

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.

Incorrect results when using four points

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

Rectangle shapes

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

Computed hull is not convex

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

Wrong polar angle calculation

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

Publish to Bower

Please publish the project to Bower as I'm currently using it in FreeDraw for gutting the polygons.