Find geometry (shapes) from node cloud

Question

I am working on some code that needs to recognize some fairly basic geometry based on a cloud of nodes. I would be interested in detecting:

• plates (simple bounded planes)
• cylinders (two node loops)
• half cylinders (arc+line+arc+line)
• domes (n*loop+top node)

I tried searching for "geometry from node cloud", "get geometry from nodes", but I cant find a nice reference. There is probably a whole field on this, can someone point me the way? i already started coding something, but I feel like re-inventing the wheel...

Answer 1

A good start is to just get the convex hull (the tightest fitting polygon that can surround your node cloud) of the nodes, use either Grahams algorithm or QuickHull. Note that QuickHull is easier to code and probably faster, unless you are really unlucky. There is a pure python implementation of QuickHull here. But I'm sure a quick Google search will show many other results.

Usually the convex hull is the starting point for most other shape recognition algorithms, if your cloud can be described as a sequence of strokes, there are many algorithms and approaches:

Recognizing multistroke geometric shapes: an experimental evaluation

This may be even better, once you have the convex hull, break down the polygon to pairs of vertices and run this algorithm to match based on similarity to training data:

Hierarchical shape recognition using polygon approximation and dynamic alignment

Both of these papers are fairly old, so you can use google scholar to see who cites these papers and there you have a nice literature trail of attempts to solve this problem.

There are a multitude of different methods and approaches, this has been well studied in the literature, what method you take really depends on the level of accuracy you hope to achieve, and the amount of shapes you want to recognize, as well as your input data set.

Either way, using a convex hull algorithm to produce polygons out of point clouds is the very first step and usually input to the more sophisticated algorithmms.

EDIT:

I did not consider the 3D case, for that their is a lot of really interesting work in computer graphics that has focused on this, for instance this paper Efficient RANSAC for Point-Cloud Shape Detection

Selections from from Abstract:

We present an automatic algorithm to detect basic shapes in unorganized point clouds. The algorithm decomposes the point cloud into a concise, hybrid structure of inherent shapes and a set of remaining points. Each detected shape serves as a proxy for a set of corresponding points. Our method is based on random sampling and detects planes, spheres, cylinders, cones and tori...We demonstrate that the algorithm is robust even in the presence of many outliers and a high degree of noise...Moreover the algorithm is conceptually simple and easy to implement...

Answer 2

To complement Josiah's answer -- since you didn't say whether there is a single such object to be detected in your point cloud -- a good solution can be to use a (generalized) Hough transform.

The idea is that each point will vote for a set of candidates in the parameter space of the shape you are considering. For instance, if you think the current object is a cylinder, you have a 7D parameter space consisting of the cylinder center (3D), direction (2D), height (1D) and radius (1D), and each point in your point cloud will vote for all parameters that agree with the observation of that point. Doing so allows to find the parameters of the actual cylinder by taking the set of parameters who have the highest number of votes. Doing the same thing for planes, spheres etc.., will give you the best matching shape.

A strength of this method is that it allows for multiple objects in the same point cloud.