After a weekend full of reflections, I found a convenient solution.
So, we need a grid, we need to fill it with our own points, without difficulty.
We must decide which squares are considered the "outline". Our criteria: at least one empty neighbor and at least 3 non-empty neighbors.
We are missing connection information. Thus, we select the “Contour” square, which as 2 “Contour” neighbors or less. Then we select one of the neighbors. From this, decomposition can begin. We simply go around the current square to find the next Contour square, knowing the previous Contour squares. Our contour criteria do not allow us to reach a dead end.
Now we have vectors of connected squares, and usually, if our form does not have a hole, only one vector of connected squares!
Now for each square we need to find the best point for the path. Choose the one that is further from the barycenter of our aircraft. It works for most forms. Another method is to calculate the barycenter of the empty neighbors of the selected square and select the nearest point.
Red dots are the outline of green. The equipment used is a flat barycenter.
For a set of 28,000 points, these methods take 8 ms. CGAL Alpha forms occupy an average of 125 ms at 28,000 points.
PS: I hope I realized that English is not my native language: s
Cyril
source share