/ Machine Learning

Fast polygon extraction from point clouds

Fast polygon extraction from point clouds


Polygon Extraction from 2D and 3D Point Clouds.

Key Features

  • Fast (Multi)Polygon Extraction from 2D and 3D point clouds
    • Written in C++ for portability
    • Extremely fast. 100,000 3D point cloud takes ~130ms to process on laptop
    • Polygons with holes may be returned
  • Python3 bindings using PyBind11
    • Low overhead for calling python/cpp interface (no copying of point cloud data)
  • Python and C++ Examples
  • Cross platform
    • Windows and Linux ready.

Polylidar allows one to extract planar meshes from a point cloud and their polygon representations. The point cloud can be in 2, 3, or 4 dimensions (XY, XYZ, XYZC=Class). This module is written in C++ and can be used as a python module or standalone with a C++ project. Note the lidar in Polylidar is a misnomer; it works with any point cloud, not just from LiDAR sensors. Click here for a basic demo in the browser: Binder


Polylidar is going through a major rewrite to more properly handle 3D data. I'm very exctied about the work and will soon publish the results. If you are interested work is going on in the branch major_changes_refactor. Some key changes are:

  • New Data inputs: Organized Point Cloud (i.e. rgbd images) and arbitary user input meshes.
  • Parallelsim - Using OpenMP and Dynamic Tasks (Fibers).
  • Plane Extraction from all data inputs. Polylidar can determine all the dominant planes in the scene and extract polygonal representations.

This is still a WIP, but wanted to let people know that may be watching this work. Thanks!


Python Projects

Pip install

  1. Install conda or create a python virtual envrionment (Why?). I recommend conda for Windows users.
  2. conda install shapely - Only for Windows users because conda handles windows binary dependency correctly.
  3. pip install polylidar

Binary wheels are provided only for Windows x64 for Python 3.6-3.7. This means everyone else (Linux, MacOS) will need to have a C++ compiler (GCC or Clang) to compile the source during pip installation.

Manual build from git clone

  1. Install conda or create a python virtual envrionment (Why?). I recommend conda for Windows users.
  2. conda install shapely - Only for Windows users because conda handles windows binary dependency correctly.
  3. pip install -e ".[dev]"
  4. pytest - OPTIONAL, this will run a series of tests and benchmarks.

C++ Projects

Simple Makefile

See examples/cpp for how to build.


You can build Polylidar and an example project with CMake.

  1. mkdir build && cd build
  2. cmake .. && make -j && cd ..
  3. ./build/polylidar-simple-2d - Simple test program.

To integrate with a different CMake Project do the following:

  1. Add as a submodule into your repo: git submodule add https://github.com/JeremyBYU/polylidar thirdparty/polylidar
  2. Add the following to your CMakeLists.txt file:
target_link_libraries(MY_BINARY polylidar)

Robust Geometric Predicates

Delaunator (the 2D triangulation library used) does not use robust geometric predicates for its orientation and incircle tests; reference. This means that the triangulation can be incorrect when points are nearly colinear or cocircular. A library developed by Jonathan Richard Shewchuk provides very fast adaptive precision floating point arithmetic for geometric predicates. This library is released in the public domain and an updated version of it is maintained at this repository. I have included this source code in the folder polylidar/predicates.

If you desire to have robust geometric predicates built into Polylidar you must set an environment variable, "PL_USE_ROBUST_PREDICATES=1" (-DPL_USE_ROBUST_PREDICATES for C++). The python file setup.py will read this environment variable and then include the robust geometric predicates into the build process. Without setting this variable none of the predicates source code is included in the python plugin.

How To Use

You can see a demo in action py running python examples/python/basic2d.py. More Python and C++ examples can be found in the examples folder.

Function exposed:

from polylidar import extractPlanesAndPolygons, extractPolygons, Delaunator

kwargs = dict(alpha=0.0, lmax=1.0)

# You want everything!
delaunay, planes, polygons = extractPlanesAndPolygons(point_cloud, **kwargs)

# Show me JUST the polygons!
polygons = extractPolygons(point_cloud, **kwargs)

# Also if you just want fast 2D delaunay triangulation, no polylidar
delaunay = Delaunator(point_cloud)

API (WIP to improve documentation)

What are the inputs to the code? The input arguments are a contiguous numpy array with length N and 2,3,or 4 columns depending on your data. There are also configuration options as well that you can pass as keyword arguments.

What are the inputs?

  • points - Numpy array
  • Required - 2D Triangle Filtering
    • alpha (double, default=1.0) - The maximum circumradius of a triangle.
    • lmax (double,default=0.0 [inactive]) - Maximum edge length of any edge in a triangle. i.e. maximum point distance for spatial connectivity.
  • Optional - 3D Triangle Filtering (normal filtering aka planarity constraints)
    • normalVector ([double, double, double]) - NOT IMPLEMENTED. Currently fixed to [0,0,1]. The normal vector of the planar mesh(s) you desire to extract.
    • normThresh (double, default=0.9) - Any triangle whose abs(normalVector * triangleNormal) < normThresh is filtered
    • zThresh (double,default=0.2) - Normal filtering is ignored (bypassed) if the the "height" (dz) of a triangle is less than zThresh. This is used to attenuate false-positive filtering in noisy pointclouds.
    • normThreshMin (double, default=0.1) - Any triangle whose abs(normalVector * triangleNormal) < normThreshMin is filtered. This take priority over anything else, even zThresh bypass. Think of this as the bare minimum of flatness a triangle must have to remain in the mesh.
  • Optional - 3D Plane Filtering
    • minTriangles (int) - Any planar mesh who has less than this quantity of triangles will not be returned
  • Optional - Triangle Filtering by Class (4th Dimension)
    • allowedClass (double) - Will filter out triangles whose vertices are not classified the same as allowedClass

What are the outputs?

  • Delaunay - This is a C++ class data structure that has information about your triangles, half edges, and point indices. Read more here.
  • planes - This is a list of C++ vectors holding ints. Each vector is an extracted plane. The ints correspond to triangle indices.
  • polygons - This is a list of C++ polygon data structure.
  • polygon - This is a struct that has two fields: shell and holes. Shell is a vector of ints, where each int represents a point index. Holes is a list of a vector of ints. Each vector represents a hole in the polygon.

Polylidar Use Cases

  • Polylidar-RealSense - Live ground floor detection with Intel RealSense camera using Polylidar
  • PolylidarWeb. A Typescript (javascript) version with live demos.
  • Concave-Evaluation - Evaluates and benchmarks several competing concavehull algorithms.


This software uses the following open source packages:

Related Methods


Any help or suggestions would be appreciated! Some tools you may find useful when you install from git clone and build for development

  1. pytest - Run a series of tests and benchmarks.
  2. nox - Build environment for testing and build wheels.


  1. bash ./package.sh