Polylidar3D - An Introduction
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!
Please check out the documentation or the Github Repo. You can also read the papers for Polylidar that explains the overall algorithm and its extension to 3D.
Check out Polylidar3D being used in real-time with an Intel RealSense Camera:
