Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Original post is edited after getting some suggestions;

I am looking for a fast algorithm which is able to detect outer most boundary of a plane for given set of points. Suppose, I have 3D point clouds and points are segmented as belonging to different (identified) planes. Now I want to extract outer most points of each plane. The problem can be considered as a 2D case by projecting x,y coordinates of each point to the XY Plane. So what I am expecting is fast, precise algorithm, which is able to detect all the boundary points along very irregular borders. convex hull doesnt fit for me as it fails on irregular cases.

•publications relavent to this, codes and psudo codes are expecting to implement in c++. thank you

share|cite|improve this question
Not clear for me... you want to fit 3D points to N planes? – leonbloy Jul 7 '11 at 14:43
up vote 0 down vote accepted

I'm not sure about your problem statement, but you might find the Hough transform, (in 3D) usefule. For example:

Added: statement misunderstood, it seems that the planes are already identified, we just want to find out the borders of the figures that each subset of points determine over each plane. For that, I'd project the points to the respective plane and apply iterative algorithm, starting with the convex hull and deleting/splitting borders. For example:

share|cite|improve this answer
hi, thanks for the reference. but i am not looking for the hough transformation. it is for detecting planes. i have done plane fitting part. now i want to find the edges of the planes where outer most points are representing. for that, i want to detect outer most points. now, i am looking for an algorithm whaich is able to detect points locating along the boundary of each segment. it could be something like convex hull. but it doesnt fit for me as i have irragular edges. perhaps, modified alpha shape could work. but i do not have codes or psudo codes for that. hope it is more clear now. thanks – niro Jul 8 '11 at 9:12
it's more clear now, yes. but, assuming that the points can be segmented as belonging to different (identified) planes, the problem seems more 2D than 3D to me. like find out the border of a planar figure given a set of points. if i'm right, perhaps you should concentrate on that, and change the title. – leonbloy Jul 8 '11 at 12:19
@ leonbloy >> May i ask a question; actually, i dont have much experience on this field. therefore, i would like to know this method would be more efficient and precise than alpha shapes. your comments are appreciating. – niro Jul 8 '11 at 17:58
@g_niro: sorry, neither I have experience with any of them. I guess that would be difficult to answer in general, as the notion of "precise" is... imprecise, and all depends on the amount of points, shapes, density, etc This paper mentions some connections, looks nice: – leonbloy Jul 8 '11 at 18:17
thanks for the infor, – niro Jul 11 '11 at 21:09

Your Answer


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.