Polylidar3D is a fast polygon extraction C++/Python library for 2D & 3D data (points, meshes, etc.). The library name is a misnomer, it works with more than just LiDAR sensor data. It will work with any generalized point/mesh data!
What does it do?
Polylidar3D extracts non-convex (multi)polygon(s) with interior holes from 2D & 3D data. Wow, that’s a lot of jargon. Lets break it down with an example in 2D.
Here is a picture of a 2D point set that has the “shape” of the letters “PL”:
Polylidar will extract the “shape” of the point set as a polygon. It will even capture the hole in the letter “P”. Here is a visualization of the output:
Basically Polyidar3D will first:
- Triangulate the data making a mesh. These are the black triangles.
- Perform region growing of edge-connected triangles. These is the shaded blue and orange triangles for the letters “P” and “L”. Users configure region growing by point distance.
- For each region, Polyidar will extract a non-convex polygon. The green line represents the exterior hull and orange lines represents interior holes. These are linear rings.
So in this example Polylidar extracted two non-convex polygons, hence a multipolygon.
It works in 3D too?
Yep, but of course theres a little bit more to it! Polylidar3D does a couple extra things: mesh smoothing and dominant plane estimation. Polygons are then extracted for each dominant plane. Users also have a lot more configuration available such as type of mesh smoothing and amount, enforcing planarity constraints, etc. Here is an example of using Polylidar3D in my living room:
Yep, thats a squirrel statue on my table. This is also made very fast with CPU multi-threading and GPU acceleration! For example, it only took a few milliseconds to extract the polygons above. Polylidar3D can take the following as input:
- Unorganized 2D Point Sets
- Unorganized 3D Point Clouds (airborne LiDAR Point Clouds)
- Organized 3D Point Clouds (e.g, range images, rgbd video)
- Triangular Meshes
Note that there are some limitations on unorganized 3D point clouds.
Should I use this?
If you need to extract polygons from “dense” 2D/3D data then maybe! However, if you don’t need “holes” or multiple polygons then I would look elsewhere. For example here’s a great 2D concavehull algorithm.
I want to know more!
Check out Polylidar3D being used in real-time with an Intel RealSense Camera: