1
$\begingroup$

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

  • 0
    Not clear for me... you want to fit 3D points to N planes?2011-07-07

1 Answers 1

0

I'm not sure about your problem statement, but you might find the Hough transform, (in 3D) usefule. For example: http://plum.eecs.jacobs-university.de/download/3dresearch2011.pdf

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: http://forja.uji.es/docman/view.php/43/83/border_cloud_points.pdf

  • 1
    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. thanks2011-07-08
  • 0
    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.2011-07-08
  • 0
    @ 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.2011-07-08
  • 0
    @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: http://www.cs.duke.edu/~edels/Papers/2010-B-01-AlphaShapes.pdf2011-07-08