\n\n\n## Key Features\n\n* Fast (Multi)Polygon Extraction from 2D and 3D point clouds \n - Written in C++ for portability\n - Extremely fast. 100,000 3D point cloud takes ~130ms to process on laptop\n - Polygons with holes may be returned\n* Python3 bindings using PyBind11\n - Low overhead for calling python/cpp interface (no copying of point cloud data)\n* Python and C++ Examples\n* Cross platform\n - Windows and Linux ready.\n\nPolylidar 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 Poly**lidar** is a misnomer; it works with any point cloud, not just from LiDAR sensors.\n\n## Install\n\n### Python\n\n**PIP install**\n\n1. Install [conda](https://conda.io/projects/conda/en/latest/) or create a python virtual envrionment ([Why?](https://medium.freecodecamp.org/why-you-need-python-environments-and-how-to-manage-them-with-conda-85f155f4353c)). I recommend conda for Windows users.\n2. `conda install shapely` - Only for Windows users because conda handles windows binary dependency correctly.\n3. `pip install polylidar`\n\nBinary 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.\n\n**Manual build from git clone**\n\n1. Install [conda](https://conda.io/projects/conda/en/latest/) or create a python virtual envrionment ([Why?](https://medium.freecodecamp.org/why-you-need-python-environments-and-how-to-manage-them-with-conda-85f155f4353c)). I recommend conda for Windows users.\n2. `conda install shapely` - Only for Windows users because conda handles windows binary dependency correctly.\n3. `pip install -e \".[dev]\"`\n4. `pytest` - OPTIONAL, this will run a series of tests and benchmarks.\n\n### C++\n\nSee `examples/cpp` for how to build.\n\n### Robust Geometric Predicates\n\nDelaunator does not use [robust geometric predicates](https://github.com/mikolalysenko/robust-arithmetic-notes) for its orientation and incircle tests; [reference](https://github.com/mapbox/delaunator/issues/43). 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](https://www.cs.cmu.edu/~quake/robust.html). This library is released in the public domain and an updated version of it is maintained at this [repository](https://github.com/danshapero/predicates). I have included this source code in the folder `polylidar/predicates`. \n\nIf 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.\n\n\n## How To Use\n\nYou 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.\n\nFunction exposed:\n\n```python\nfrom polylidar import extractPlanesAndPolygons, extractPolygons, Delaunator\n\nkwargs = dict(alpha=0.0, lmax=1.0)\n\n# You want everything!\ndelaunay, planes, polygons = extractPlanesAndPolygons(point_cloud, **kwargs)\n\n# Show me JUST the polygons!\npolygons = extractPolygons(point_cloud, **kwargs)\n\n# Also if you just want fast 2D delaunay triangulation, no polylidar\ndelaunay = Delaunator(point_cloud)\n```\n\n### API (WIP to improve documentation)\n\nWhat 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.\n\n\nWhat are the inputs?\n\n* points - Numpy array\n* Required - 2D Triangle Filtering\n * alpha (double, default=1.0) - The maximum circumradius of a triangle.\n * lmax (double,default=0.0 [inactive]) - Maximum edge length of any edge in a triangle. i.e. maximum point distance for spatial connectivity.\n* Optional - 3D Triangle Filtering (normal filtering aka planarity constraints)\n * normalVector ([double, double, double]) - NOT IMPLEMENTED. Currently fixed to [0,0,1]. The normal vector of the planar mesh(s) you desire to extract.\n * normThresh (double, default=0.9) - Any triangle whose `abs(normalVector * triangleNormal) < normThresh` is filtered\n * 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. \n * 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.\n* Optional - 3D Plane Filtering\n * minTriangles (int) - Any planar mesh who has less than this quantity of triangles will not be returned\n* Optional - Triangle Filtering by Class (4th Dimension)\n * allowedClass (double) - Will filter out triangles whose vertices are not classified the same as allowedClass\n\nWhat are the outputs?\n\n* Delaunay - This is a C++ class data structure that has information about your triangles, half edges, and point indices. Read more [here](https://mapbox.github.io/delaunator/).\n* planes - This is a *list* of C++ *vectors* holding `ints`. Each vector is an extracted plane. The `ints` correspond to triangle indices.\n* polygons - This is a *list* of C++ `polygon` data structure.\n* 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.\n\n\n## Polylidar Use Cases\n\n- [Polylidar-RealSense](https://github.com/JeremyBYU/polylidar-realsense) - Live ground floor detection with Intel RealSense camera using Polylidar\n- [PolylidarWeb](https://github.com/JeremyBYU/polylidarweb). A Typescript (javascript) version with live demos.\n- [Concave-Evaluation](https://github.com/JeremyBYU/concavehull-evaluation) - Evaluates and benchmarks several competing concavehull algorithms.\n\n\n## Credits\n\nThis software uses the following open source packages:\n\n- [Delaunator](https://github.com/mapbox/delaunator) - Original triangulation library\n- [DelaunatorCPP](https://github.com/delfrrr/delaunator-cpp) - Delaunator ported to C++ (used)\n- [parallel-hashmap](https://github.com/greg7mdp/parallel-hashmap) - Very fast hashmap library (used)\n- [PyBind11](https://github.com/pybind/pybind11) - Python C++ Binding (used)\n- [Robust Geometric Predicates](https://www.cs.cmu.edu/~quake/robust.html) - Original Robust Geometric predicates\n- [Updated Predicates](https://github.com/danshapero/predicates) -Updated geometric predicate library (used)\n\n## Related Methods\n\n- [CGAL Alpha Shapes](https://doc.cgal.org/latest/Alpha_shapes_2/index.html) - MultiPolygon with holes.\n- [PostGIS ConcaveHull](http://postgis.net/docs/ST_ConcaveHull.html) - Single Polygon with holes.\n- [Spatialite ConcaveHull](https://www.gaia-gis.it/fossil/libspatialite/wiki?name=tesselations-4.0) - MultiPolygon with holes.\n- [Concaveman](https://github.com/mapbox/concaveman) - A 2D concave hull extraction algorithm for 2D point sets.\n\n## License\n\nMIT\n\n---\n\n> GitHub [@jeremybyu](https://github.com/JeremyBYU)\n\n\n",
"description_content_type": "text/markdown",
"docs_url": null,
"download_url": "",
"downloads": {
"last_day": -1,
"last_month": -1,
"last_week": -1
},
"home_page": "",
"keywords": "",
"license": "",
"maintainer": "",
"maintainer_email": "",
"name": "polylidar",
"package_url": "https://pypi.org/project/polylidar/",
"platform": "",
"project_url": "https://pypi.org/project/polylidar/",
"project_urls": null,
"release_url": "https://pypi.org/project/polylidar/0.0.7/",
"requires_dist": [
"numpy (>=1.15.0)",
"pybind11 (>=2.2.4)",
"shapely",
"matplotlib",
"descartes",
"pytest ; extra == 'dev'",
"pytest-xdist ; extra == 'dev'",
"pytest-benchmark ; extra == 'dev'",
"pylint ; extra == 'dev'",
"twine ; extra == 'dev'",
"autopep8 ; extra == 'dev'",
"nox ; extra == 'dev'"
],
"requires_python": "",
"summary": "Polygon extraction from Point Cloud data",
"version": "0.0.7"
},
"last_serial": 5983595,
"releases": {
"0.0.6": [
{
"comment_text": "",
"digests": {
"md5": "599fda825300082cdac2763538872f0b",
"sha256": "4d7eb905f1cccba3e3e91baa29fe0e50aad74b752ee753fdd4d004adde13cc07"
},
"downloads": -1,
"filename": "polylidar-0.0.6-cp36-cp36m-win_amd64.whl",
"has_sig": false,
"md5_digest": "599fda825300082cdac2763538872f0b",
"packagetype": "bdist_wheel",
"python_version": "cp36",
"requires_python": null,
"size": 320064,
"upload_time": "2019-10-12T00:16:17",
"url": "https://files.pythonhosted.org/packages/a5/35/ecd97863009b6c4ea69940018df84e2030ce0c14561337a5df7b1df629fd/polylidar-0.0.6-cp36-cp36m-win_amd64.whl"
},
{
"comment_text": "",
"digests": {
"md5": "2e223185c8d4db0d0a8121d663c4b780",
"sha256": "af4a0838b313316bbea44d8bcbdf00a547b6b7f77b6e93f4cbb6fb15f8ddb2d8"
},
"downloads": -1,
"filename": "polylidar-0.0.6-cp37-cp37m-win_amd64.whl",
"has_sig": false,
"md5_digest": "2e223185c8d4db0d0a8121d663c4b780",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": null,
"size": 320386,
"upload_time": "2019-10-12T00:16:19",
"url": "https://files.pythonhosted.org/packages/6e/11/30f47575c0c98cd30afabb5bf33b4616e34da73dfd366a31f39f319694ed/polylidar-0.0.6-cp37-cp37m-win_amd64.whl"
},
{
"comment_text": "",
"digests": {
"md5": "a62ab4bf6a1d50e968924d76a730e13a",
"sha256": "39c24504f5c47563b80eddbbe8270c6c6ba5f64a113b18d1573d081fc1063a6c"
},
"downloads": -1,
"filename": "polylidar-0.0.6.tar.gz",
"has_sig": false,
"md5_digest": "a62ab4bf6a1d50e968924d76a730e13a",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 2315505,
"upload_time": "2019-10-12T00:16:22",
"url": "https://files.pythonhosted.org/packages/7f/ce/334272c413eaa1b9daf0e941fb4e2c5071d4a778f8a48f3e3ba4afed97b2/polylidar-0.0.6.tar.gz"
}
],
"0.0.7": [
{
"comment_text": "",
"digests": {
"md5": "caf3ca2ab79f483fccdba4d82ad99534",
"sha256": "a92efabcab4b8f3a5ba04b9c7a4fb7f774482a0e9445d5a6a81ad6306097bca7"
},
"downloads": -1,
"filename": "polylidar-0.0.7-cp36-cp36m-win_amd64.whl",
"has_sig": false,
"md5_digest": "caf3ca2ab79f483fccdba4d82ad99534",
"packagetype": "bdist_wheel",
"python_version": "cp36",
"requires_python": null,
"size": 319361,
"upload_time": "2019-10-16T14:00:32",
"url": "https://files.pythonhosted.org/packages/8a/cc/f032a51a3ab36ee25c08a27b098b9f1f50fa3a7851c921d6187898e789a3/polylidar-0.0.7-cp36-cp36m-win_amd64.whl"
},
{
"comment_text": "",
"digests": {
"md5": "306135fd563fcafe6ac41cc1b8247ca4",
"sha256": "032d25685c65864833eabecf66341a7efd349a3d70f5d126dff9b80558d11c7a"
},
"downloads": -1,
"filename": "polylidar-0.0.7-cp37-cp37m-win_amd64.whl",
"has_sig": false,
"md5_digest": "306135fd563fcafe6ac41cc1b8247ca4",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": null,
"size": 319790,
"upload_time": "2019-10-16T14:00:49",
"url": "https://files.pythonhosted.org/packages/4a/a3/73ecda74fe97b4074876da5f964dce8ce9b0ae6704d5156e9f7879e7af9b/polylidar-0.0.7-cp37-cp37m-win_amd64.whl"
},
{
"comment_text": "",
"digests": {
"md5": "934bdc167d3bc88ad020e1fb3b435c29",
"sha256": "9be233af538b430ed016817ebe034a607e90afe96e1e6ce5fce0fc9c636bd1fd"
},
"downloads": -1,
"filename": "polylidar-0.0.7.tar.gz",
"has_sig": false,
"md5_digest": "934bdc167d3bc88ad020e1fb3b435c29",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 2325344,
"upload_time": "2019-10-16T14:01:00",
"url": "https://files.pythonhosted.org/packages/2d/07/f5de09eac5edeeb589c764f47e835cc9d256b32961347e2d47bf03304299/polylidar-0.0.7.tar.gz"
}
]
},
"urls": [
{
"comment_text": "",
"digests": {
"md5": "caf3ca2ab79f483fccdba4d82ad99534",
"sha256": "a92efabcab4b8f3a5ba04b9c7a4fb7f774482a0e9445d5a6a81ad6306097bca7"
},
"downloads": -1,
"filename": "polylidar-0.0.7-cp36-cp36m-win_amd64.whl",
"has_sig": false,
"md5_digest": "caf3ca2ab79f483fccdba4d82ad99534",
"packagetype": "bdist_wheel",
"python_version": "cp36",
"requires_python": null,
"size": 319361,
"upload_time": "2019-10-16T14:00:32",
"url": "https://files.pythonhosted.org/packages/8a/cc/f032a51a3ab36ee25c08a27b098b9f1f50fa3a7851c921d6187898e789a3/polylidar-0.0.7-cp36-cp36m-win_amd64.whl"
},
{
"comment_text": "",
"digests": {
"md5": "306135fd563fcafe6ac41cc1b8247ca4",
"sha256": "032d25685c65864833eabecf66341a7efd349a3d70f5d126dff9b80558d11c7a"
},
"downloads": -1,
"filename": "polylidar-0.0.7-cp37-cp37m-win_amd64.whl",
"has_sig": false,
"md5_digest": "306135fd563fcafe6ac41cc1b8247ca4",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": null,
"size": 319790,
"upload_time": "2019-10-16T14:00:49",
"url": "https://files.pythonhosted.org/packages/4a/a3/73ecda74fe97b4074876da5f964dce8ce9b0ae6704d5156e9f7879e7af9b/polylidar-0.0.7-cp37-cp37m-win_amd64.whl"
},
{
"comment_text": "",
"digests": {
"md5": "934bdc167d3bc88ad020e1fb3b435c29",
"sha256": "9be233af538b430ed016817ebe034a607e90afe96e1e6ce5fce0fc9c636bd1fd"
},
"downloads": -1,
"filename": "polylidar-0.0.7.tar.gz",
"has_sig": false,
"md5_digest": "934bdc167d3bc88ad020e1fb3b435c29",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 2325344,
"upload_time": "2019-10-16T14:01:00",
"url": "https://files.pythonhosted.org/packages/2d/07/f5de09eac5edeeb589c764f47e835cc9d256b32961347e2d47bf03304299/polylidar-0.0.7.tar.gz"
}
]
}
![](\"https://raw.githubusercontent.com/JeremyBYU/polylidarv2/master/assets/2D_polygon_text.png\")
\n ![](\"https://raw.githubusercontent.com/JeremyBYU/polylidarv2/master/assets/combined.png\")
\n