Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
1  
Unclear question: your image shows two distinct point clouds with their own boundaries. The algorithm to find a polygon which describes the cloud boundary is different from one which can identify clusters of points. Basically it seems like you want to do cluster analysis first (to identify distinct areas of the point cloud), and then within a cloud find a boundary polygon. But your question doesn't make this clear. –  MrCranky Feb 27 '12 at 13:11
    
Maybe something BFS-like? –  akled Feb 29 '12 at 13:34
add comment

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
1  
I dont think, that lines on picture create convex hull. If you look at the left side, it's definitely not convex. But if Cato112 really wants to compute convex hull, he can use Jarvis algorithm or Graham scan. Which are two easy-enough algorithms. –  zacharmarz Feb 27 '12 at 12:19
    
No, they don't create a convex hull, but it will do for my purposes. –  Majd Feb 27 '12 at 12:27
    
@Cato112, if you don't want the convex hull then you'll need to specify what you mean more precisely, because a priori there's no reason not to form a polynomial which has all of the points as vertices. –  Peter Taylor Feb 27 '12 at 12:31
    
Well, I guess the question is somewhat diffuse because I don't quite know what I want until I see it. I'll try with the convex hull approach. I also find that the line can be drawn in several ways depending on what points you choose to include. Maybe it becomes more clear if I say that I want to visualize an SPH fluid simulation in 2D. –  Majd Feb 27 '12 at 12:53
add comment

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.

Passing and failing cases for the boundary check - red dots are ones which cause the line to fail the test.

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.

share|improve this answer
    
+1, Nice algorithm and explanation :) –  Daniel Mar 1 '12 at 12:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.