Question about Clustering about polygon_coverage_planning HOT 1 CLOSED

You are correct, the shape of the decomposition depends a lot on the shape of the polygon and holes. That's why this approach is not the best if you have many, complex obstacles, because you will create many cells.

You can pick between Boustrophedon decomposition or trapezoidal decomposition. These are so called sweep line algorithms. The trapezoidal decomposition is part of CGAL, while the Boustrophedon decomposition we implemented ourselves. Because they are sweep line algorithm the resulting decomposition depends on the direction of the sweep. We iterate through all sweep directions perpendicular to any of the edge directions and select the one that has the minimum altitude sum.

If you want to read more on this you can have a look at the following publications:

Choset, H., Pignon, P.: Coverage path planning: The boustrophedon cellular decomposition. In: Field and Service Robotics, pp. 203–209. Springer (1998)

Huang, W.H.: Optimal line-sweep-based decompositions for coverage algorithms. In:
IEEE International Conference on Robotics and Automation, vol. 1, pp. 27–32. IEEE
(2001)

as well as this presentation: https://www.cs.cmu.edu/~motionplanning/lecture/Chap6-CellDecomp_howie.pdf

from polygon_coverage_planning.