# Source: extras/ConvexHull.js

``````/**
* Utility class used to compute a **convex hull**. Based on algorithm from Chapter 1 in {@link http://www.amazon.com/dp/3540779736/?tag=stackoverfl08-20|this book}.
*
* - {@link http://www.travellermap.com/tmp/delaunay.js}
* - {@link https://github.com/ironwallaby/delaunay/blob/master/delaunay.js}
* - {@link http://paulbourke.net/papers/triangulate/}
*
*  @class ConvexHull
*  @memberof SQR
*/
SQR.ConvexHull = (function() {

var upper = [], lower = [], hull = [];

var sortXY = function(a, b) {
if(a.x == b.x) return a.y - b.y;
else return a.x - b.x;
}

var isRight = function(a, b, c){
return (
(c.x * a.y - c.y * a.x) -
(b.x * a.y - b.y * a.x) +
(b.x * c.y - b.y * c.x)) < 0;
}

var upperHull = function(p, u) {

u.push(p[0]);
u.push(p[1]);

for(var i = 2, l = p.length; i < l; i++) {

u.push(p[i]);

while(u.length > 2 &&
!isRight(
u[u.length-3],
u[u.length-1],
u[u.length-2]
)
) {
u.splice(
u.indexOf(u[u.length-2]),
1
);
}
}

return u;
}

var lowerhull = function(p, u){

u.push(p[p.length-1]);
u.push(p[p.length-2]);

for(var i = p.length-3; i >= 0; i--) {
u.push(p[i]);

while(u.length > 2 &&
!isRight(
u[u.length-3],
u[u.length-1],
u[u.length-2]
)
) {
u.splice(
u.indexOf(u[u.length-2]),
1
);
}
}

return u;
}

return {
/**
*	@method compute
*	@memberof SQR.ConvexHull
*
*	@desription computes the convexhull for a give set of points
*
*	@param {Array} p - array of {@link SQR.V2} or any objects that have a `x` and `y` property.
*	@param {Array} h - the array to store the result in. If omitted, new one is created.
*
*	@returns {Array} array of {@link SQR.V2} containing ordered points that make the convexhull.
*/
compute: function(p, h) {

if(!h) h = hull;

upper.length = 0, lower.length = 0, h.length = 0;

p.sort(sortXY);

upperHull(p, upper);
lowerhull(p, lower);

h = h.concat(upper, lower);

return h;
}
}

})();

``````