-
Notifications
You must be signed in to change notification settings - Fork 18
/
graham_scan.js
161 lines (125 loc) · 4.05 KB
/
graham_scan.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
/**
* Graham's Scan Convex Hull Algorithm
* @desc An implementation of the Graham's Scan Convex Hull algorithm in Javascript.
* @author Brian Barnett, [email protected], http://brianbar.net/ || http://3kb.co.uk/
* @version 1.0.2
*/
function ConvexHullGrahamScan() {
this.anchorPoint = undefined;
this.reverse = false;
this.points = [];
}
ConvexHullGrahamScan.prototype = {
constructor: ConvexHullGrahamScan,
Point: function (x, y) {
this.x = x;
this.y = y;
},
_findPolarAngle: function (a, b) {
var ONE_RADIAN = 57.295779513082;
var deltaX = (b.x - a.x);
var deltaY = (b.y - a.y);
if (deltaX == 0 && deltaY == 0) {
return 0;
}
var angle = Math.atan2(deltaY, deltaX) * ONE_RADIAN;
if (this.reverse){
if (angle <= 0) {
angle = 360;
}
}else{
if (angle >= 0) {
angle = 360;
}
}
return angle;
},
addPoint: function (x, y) {
//Check to see if anchorPoint has been defined yet.
if (this.anchorPoint === undefined) {
//Create new anchorPoint.
this.anchorPoint = new this.Point(x, y);
// Sets anchorPoint if point being added is further left.
} else if (this.anchorPoint.y > y || (this.anchorPoint.y == y && this.anchorPoint.x > x)) {
this.anchorPoint.y = y;
this.anchorPoint.x = x;
this.points.unshift(new this.Point(x, y));
return;
}
this.points.push(new this.Point(x, y));
},
_sortPoints: function () {
var self = this;
return this.points.sort(function (a, b) {
var polarA = self._findPolarAngle(self.anchorPoint, a);
var polarB = self._findPolarAngle(self.anchorPoint, b);
if (polarA < polarB) {
return -1;
}
if (polarA > polarB) {
return 1;
}
return 0;
});
},
_checkPoints: function (p0, p1, p2) {
var difAngle;
var cwAngle = this._findPolarAngle(p0, p1);
var ccwAngle = this._findPolarAngle(p0, p2);
if (cwAngle > ccwAngle) {
difAngle = cwAngle - ccwAngle;
return !(difAngle > 180);
} else if (cwAngle < ccwAngle) {
difAngle = ccwAngle - cwAngle;
return (difAngle > 180);
}
return false;
},
getHull: function () {
var hullPoints = [],
points,
pointsLength;
this.reverse = this.points.every(function(point){
return (point.x < 0 && point.y < 0);
});
points = this._sortPoints();
pointsLength = points.length;
//If there are less than 4 points, joining these points creates a correct hull.
if (pointsLength < 4) {
return points;
}
//move first two points to output array
hullPoints.push(points.shift(), points.shift());
//scan is repeated until no concave points are present.
while (true) {
var p0,
p1,
p2;
hullPoints.push(points.shift());
p0 = hullPoints[hullPoints.length - 3];
p1 = hullPoints[hullPoints.length - 2];
p2 = hullPoints[hullPoints.length - 1];
if (this._checkPoints(p0, p1, p2)) {
hullPoints.splice(hullPoints.length - 2, 1);
}
if (points.length == 0) {
if (pointsLength == hullPoints.length) {
return hullPoints;
}
points = hullPoints;
pointsLength = points.length;
hullPoints = [];
hullPoints.push(points.shift(), points.shift());
}
}
}
};
// EXPORTS
if (typeof define === 'function' && define.amd) {
define(function() {
return ConvexHullGrahamScan;
});
}
if (typeof module !== 'undefined') {
module.exports = ConvexHullGrahamScan;
}