I am looking for any algorithms that can find simple 2D geometry such as square\rectangle\hexagon in a 3D point cloud. Point clouds never contain more than around 50 points.
I have looked at RANSAC but this doesn't suite my solution, basically all the shapes will have points only were the vectors change angle. For instance a square will contain 4 points, hexagon 6 points and octagon 8 points.
First step, in my opinion, should be finding all different planes containing all cloud's points. Any 3, different and not collinear, points in 3D make the plane. This choice of the set of starting points may be performed on N!/3! ways. Not scared? Then try to find all other cloud points belonging to this very plane. When done, you have the first 2D cluster. Continue at least to the point when members of all already found clusters exhaust your cloud. Note that some planes may still remain undetected, as at least some cloud's points may belong to more than one plane! Unfortunately, this hard work will almost certainly fail when performed by computer operating on floating point numbers - because unavoidable rounding errors - even if the coordinates of points making your 3D cloud are 'exact.'
How noisy is this data? Are the shapes embedded in a cloud of other points? For only 50 points or so, you just exhaust the n choose k (50 3) or appx 19k planes through 3 points from the cloud, project the other points to the plane under a threshold (to account for noise making them non-planar) and then assuming convexity run a convex hull algorithm in each plane to extract the shape.
Dear Michael:
As Marek said, you may need to try a clustering approach to find your 2D objects that are embedded in 3D space. In particular, you can formulate the equation of the plane as a Hough Transform problem to find your 2D objects. The results (3D points) in each plane need to be segmented further to separate them into single objects and a proximity threshold can do this job.
Regards,
Gamal
- Badges
- Science topic
- Similar topics
- Instrumentation Engineering
- Instruments