Does anyone know an efficient algorithm to find the edge of a point cloud? Hopefully the picture in the link can illustrate what I mean. It's a plus if the algorithm can handle point clouds that are distinctly separated in space. The algorithm only needs to work in 2D.
Many thanks!!
http://uploadpic.org/storage/2011/4n68m1OYLSYIGt8vfuJrK1LnA.png
You want to compute the convex hull of your point data: http://en.wikipedia.org/wiki/Convex_hull
I'd recommend the qhull software written in C: http://www.qhull.org/
Here is their licensing info: http://www.qhull.org/COPYING.txt
Discounting the fact that your image shows two point clouds not one, I'm going to assume that you don't want to do cluster analysis to find 'blobs' of points. If you do, just do that first.
The primary part of the problem (the boundary polygon) needs more definition. If you just want a convex hull, then the gift-wrapping algorithm works fine. If you want a tighter fit (as shown in your image), then you need to alter the criteria by which points are rejected.
In the basic gift-wrapping algorithm, you start at a point known to be on the boundary (the left-most point), and pick points such that for each new point you pick, every other point in the set is to the right of the line formed between the new point and the previous point.
To get a tighter fit, all you need to do is modify the rejection criteria. Instead of rejecting points which have any points 'to the left', you reject points which have others which fall within the area bounded by a line extending out to the left, perpendicular to the boundary line. Hard to describe accurately, so see these examples. The black dotted line denotes the area within which any points would cause the line to be rejected.
So to test a line segment, you iterate the other points in the cloud. Make a line between the test point and the endpoint of the line, and calculate the angle between the boundary line and that new line. If the angle is less than 90 degrees, the point lies in the problem area.
NB: this is the exact same check the standard gift-wrapping algorithm uses, except the usual limit is 180 degrees. As you reduce that angle, more and more points will be allowable, and as you tend to 0 degrees, eventually any point will be valid (and your boundary will look more and more spiky).
It's worth noting that with an angle less than 180, you also have to test all points rather than just dropping out with the first one you find. That's because the standard convex hull finding is looking for a minimal number of points, and either a point is on the convex hull or it isn't. With this modification, there will potentially be multiple points which satisfy the conditions, and so multiple choices for where your boundary line goes next. Which you choose is up to you - the one furthest away will give you a boundary with minimal line segments, and the one closest to you is more likely to give you a tighter fit to the points.
