Ok it is not the best method for finding the convex hull but given it is really simple idea that results in a small amount of code it can be quite useful.
The basic idea is you find the left most point from the collection of points. If two are equal you take the lowest y value.
Set this to be the end point of the lines that form the convex hull
Then we loop round all the points attempting to find a line segment from the end point to another point that has all the other points to the left of it. This forms the next point of the convex hull and we add it to our convex hull collection as well as setting it as the end point.
Just keep going until the end point that we find is the equal to the first point in our convex hull collection.
Code is often clearer than a written description of it so here's the code.
// Gift wrap method function convex_hull(pnts){ var out = []; var startIdx = findLeftMostLowestPoint(pnts); var hull = startIdx; var npts = pnts.length; var endpt = 0; do { out.push(pnts[hull]); endpt = 0; for (var j = 1; j < npts; ++j) { if (hull == endpt || isToLeft(pnts[hull], pnts[endpt], pnts[j])) endpt = j; } hull = endpt; } while (endpt != startIdx); out.push(pnts[endpt]); // close the poly return out; }and here are the helper functions you need.
function findLeftMostLowestPoint(pnts){ var idx = 0; var npts = pnts.length; for (var i = 1; i < npts; ++i) { var a = pnts[i]; var b = pnts[idx]; if(a.x < b.x || (a.x == b.x && a.y < b.y)) idx = i; } return idx; } function isToLeft(a, b, c){ var u1 = b.x - a.x; var v1 = b.y - a.y; var u2 = c.x - a.x; var v2 = c.y - a.y; return u1 * v2 - v1 * u2 < 0; }That is all you really need.
hello, may i know how the pnts array structure is? i am referring to your code for a homework, but does not know how to create the sample input points to the function, do you have any sample of the data used for the code?
ReplyDeletepnts is just an array of objects, each object must have an x and y value in them. I think I just created a random array of them when checking it worked. So to create an array of them this should do it
ReplyDeletevar pnts = [ {x:10, y:20}, {x:5, y:10}, {x:8, y:57}, {x:100, y:87} ];
convex_hull(pnts);
Thanks a lot! it works!!! Really fast algorithm!
ReplyDeleteWell fast for small collections of points, not really suited for larger data sets. It is very easy to implement and that is what I like about it.
ReplyDelete