  This paper presents Polylidar, an efficient algorithm to extract non-convex
polygons from 2D point sets, including interior holes. Plane segmented point
clouds can be input into Polylidar to extract their polygonal counterpart,
thereby reducing map size and improving visualization. The algorithm begins by
triangulating the point set and filtering triangles by user configurable
parameters such as triangle edge length. Next, connected triangles are
extracted into triangular mesh regions representing the shape of the point set.
Finally each region is converted to a polygon through a novel boundary
following method which accounts for holes. Real-world and synthetic benchmarks
are presented to comparatively evaluate Polylidar speed and accuracy. Results
show comparable accuracy and more than four times speedup compared to other
concave polygon extraction methods.
