polylidar 0.0.7

Polygon extraction from Point Cloud data

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

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++

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. 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.

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