Polygon extraction from Point Cloud data
Project description
Polylidar
Polygon Extraction from 2D and 3D Point Clouds
Key Features • Install • How To Use • Use Cases • Credits • Related • License
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.
Install
Python
Polylidar is not on PyPI so it must be installed manually.
- Install conda or create a python virtual envrionment (Why?). I recommend conda for Windows users.
conda install shapely
- Only for Windows users because conda handles windows binary dependency correctly.pip install -e ".[dev]"
pytest
- OPTIONAL, this will run a series of tests and benchmarks.
C++
See examples/cpp
for how to build.
Robust Geometric Predicates
Delaunator 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. Theints
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 ofints
. 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.
Credits
This software uses the following open source packages:
- Delaunator - Original triangulation library
- DelaunatorCPP - Delaunator ported to C++ (used)
- parallel-hashmap - Very fast hashmap library (used)
- PyBind11 - Python C++ Binding (used)
- Robust Geometric Predicates - Original Robust Geometric predicates
- Updated Predicates -Updated geometric predicate library (used)
Related Methods
- CGAL Alpha Shapes - MultiPolygon with holes.
- PostGIS ConcaveHull - Single Polygon with holes.
- Spatialite ConcaveHull - MultiPolygon with holes.
- Concaveman - A 2D concave hull extraction algorithm for 2D point sets.
License
MIT
GitHub @jeremybyu
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for polylidar-0.0.6-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | af4a0838b313316bbea44d8bcbdf00a547b6b7f77b6e93f4cbb6fb15f8ddb2d8 |
|
MD5 | 2e223185c8d4db0d0a8121d663c4b780 |
|
BLAKE2b-256 | 6e1130f47575c0c98cd30afabb5bf33b4616e34da73dfd366a31f39f319694ed |
Hashes for polylidar-0.0.6-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4d7eb905f1cccba3e3e91baa29fe0e50aad74b752ee753fdd4d004adde13cc07 |
|
MD5 | 599fda825300082cdac2763538872f0b |
|
BLAKE2b-256 | a535ecd97863009b6c4ea69940018df84e2030ce0c14561337a5df7b1df629fd |