Find contour of 2D unorganized pointcloud

Question

I have a set of 2D points, unorganized, and I want to find the "contour" of this set (not the convex hull). I can't use alpha shapes because I have a speed objective (less than 10ms on an average computer). My first approach was to compute a grid and find the outline squares (squares which have an empty square as a neighbor). So I think I downsized efficiently my numbers of points (from 22000 to 3000 roughly). But I still need to refine this new set.

My question is : how do I find the real outlines points among my green points ?

Answer 1

After a weekend full of reflexions, I may have found a convenient solution.

So we need a grid, we need to fill it with our points, no difficulty here.

We have to decide which squares are considered as "Contour". Our criteria is : at least one empty neighbor and at least 3 non empty neighbors.

We lack connectivity information. So we choose a "Contour" square which as 2 "Contour" neighbors or less. We then pick one of the neighbor. From that, we can start the expansion. We just circle around the current square to find the next "Contour" square, knowing the previous "Contour" squares. Our contour criteria prevent us from a dead end.

We now have vectors of connected squares, and normally if our shape doesn't have a hole, only one vector of connected squares !

Now for each square, we need to find the best point for the contour. We select the one which is farther from the barycenter of our plane. It works for most of the shapes. Another technique is to compute the barycenter of the empty neighbors of the selected square and choose the nearest point.

The red points are the contour of the green one. The technique used is the plane barycenter one.

For a set of 28000 points, this techniques take 8 ms. CGAL's Alpha shapes would take an average 125 ms for 28000 points.

PS : I hope I made myself clear, English is not my mothertongue :s