Building a graph from a point cloud

Question

I have a PCL Point Cloud. Basically, I need to write some code that does the following:

Example

Basically, I need to build a graph/edge map of the point cloud. Where each node represents a point, and those points have pointers/edges to neighbouring points. And preferably, it cannot form a corner edge as seen in the picture. (This could be enforced by saying a point cannot have a large change in l1 norm too (taxicab distance. add all axis), not just l2 norm).

I need to do this because, it's useful for all my other algorithms. Normal computation etc.

I'm currently at a loss of how to implement this. My point cloud is unorganized. I could sort it into a KD Tree but I'm not sure if that is related to this or how I might use this.

Answer 1

The graph/edge map is the same as a triangulation between the vertices.

In your case, as you only want to connect vertices which are close together, Delaunay Triangulation will work.

The edges are the connections between vertices in your graph.

PCL has ConcaveHull, which will triangulate the surface of your vertices, given an alpha value. This alpha value is the maximum radius for each triangle, in your case, half the known distance between diagonal vertices.