Giter Club home page Giter Club logo

polylidar's Introduction

Polylidar3D

Polygon Extraction from 2D Point Sets, Unorganized/Organized 3D Point Clouds, and Triangular Meshes

Key FeaturesDocumentationUse CasesCreditsRelatedCitationsLicense

Docs Cite 2D Cite 3D

Key Features

  • Fast (Multi)Polygon Extraction from multiple sources of 2D and 3D Data
    • Written in C++ for portability
    • Extremely fast single-threaded but includes CPU multi-threading using data and task-based parallelism
    • 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
    • Examples from 2D point sets, unorganized 3D point clouds, organized 3D point clouds (i.e., range images), and user provided meshes
  • Cross platform
    • Windows and Linux ready

Polylidar3D is a non-convex polygon extraction algorithm which takes as input either unorganized 2D point sets, unorganized 3D point clouds (e.g., airborne LiDAR point clouds), organized 3D point clouds (e.g., range images), or user provided meshes. In 3D, the non-convex polygons extracted represent flat surfaces in an environment, while interior holes represent obstacles on said surfaces. The picture above provides an examples of Polylidar3D extracting polygons from a 2D point set and a 3D triangular mesh; green is the concave hull and orange are interior holes. Polylidar3D outputs planar triangular segments and their polygonal representations. Polylidar3D is extremely fast, taking as little as a few milliseconds and makes use of CPU multi-threading and GPU acceleration when available.

Here is a small introductory blog-post about Polylidar3D.

Documentation and Branches

Please see documentation for installation, api, and examples. Note that Polylidar went though major changes in July 2020 for 3D work, now called Polylidar3D. The old repository for 2D work (and some basic 3D) is found in the branch polylidar2D and is connected to this paper. Polylidar3D can still handle 2D point sets but the API is different and not the focus of this repo. For papers referencing Polylidar2D and Polylidar3D please see Citations.

Eventually I am going to make a standalone cpp/header file for 2D point set -> polygon extraction for those that don't need any of the features of Polylidar3D.

Polylidar Use Cases

  • Polylidar-RealSense - Live ground floor detection with Intel RealSense camera using Polylidar
  • Polylidar-KITTI - Street surface and obstacle detection from autonomous driving platform
  • PolylidarWeb. An very old Typescript (javascript) version with live demos of Polylidar2D
  • Concave-Evaluation - Evaluates and benchmarks several competing concavehull algorithms

Credits

This software is only possible because of the great work from the following open source packages:

Related Methods

2D ConcaveHull Extraction

Contributing

Any help or suggestions would be appreciated!

Citation

2D

If are using Polylidar for 2D work please cite:

J. Castagno and E. Atkins, "Polylidar - Polygons From Triangular Meshes," in IEEE Robotics and Automation Letters, vol. 5, no. 3, pp. 4634-4641, July 2020, doi: 10.1109/LRA.2020.3002212. Link to Paper

@ARTICLE{9117017,
  author={J. {Castagno} and E. {Atkins}},
  journal={IEEE Robotics and Automation Letters}, 
  title={Polylidar - Polygons From Triangular Meshes}, 
  year={2020},
  volume={5},
  number={3},
  pages={4634-4641}
}

3D

If you are using Polylidar3D for 3D work please cite:

J. Castagno and E. Atkins, "Polylidar3D - Fast Polygon Extraction from 3D Data," in MDPI Sensors, vol. 20, no.17, 4819, September 2020, doi: 10.3390/s20174819 Link to Paper

@Article{s20174819,
author = {Castagno, Jeremy and Atkins, Ella},
title = {Polylidar3D-Fast Polygon Extraction from 3D Data},
journal = {Sensors},
volume = {20},
year = {2020},
number = {17},
article-number = {4819},
url = {https://www.mdpi.com/1424-8220/20/17/4819},
issn = {1424-8220}
}

License

MIT


GitHub @jeremybyu

polylidar's People

Contributors

jeremybyu avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

polylidar's Issues

Concave hull calculation?

I need to calculate the concave hull. I would like to use your repo to calculate due to faster than other packages.

Would you give a way to calculate concave hull using polylidar?
Thanks in advance

No module named 'polylidar.polylidar' on Ubuntu 18.04.5 LTS

  1. I get the following error "No module named 'polylidar.polylidar' " trying to run the example file basic2d.py on python3.6 on Ubuntu 18.04.5 LTS
    Traceback (most recent call last):
    File "", line 1, in
    File "/home/priyas/polylidar-master/cmake-build/lib/python_package/polylidar/init.py", line 1, in
    from .polylidar import * # py2 py3 compatible
    ModuleNotFoundError: No module named 'polylidar.polylidar'

  2. Polylidar installation was complete without errors
    O/P of ./bin/polylidar-simple
    Very Simple C++ Example of Polylidar3D on 2D Point Set
    Polylidar took 0 milliseconds processing a 5 point cloud
    Point indices of Polygon Shell: [3,0,1,2]

  3. Installation was tried both on virtual environment and directly ; both gives No module error.

  4. Installation on Windows platform works well. I could run the example files successfully.

  5. Earlier I had tried polylidar old verison on Ubuntu and all worked well. Switching to Polylidar3D to address large Pointcloud 3d data.

Any insight to this would be of great help , Thanks in advance

ImportError: No module named tests.python.helpers.utils

Describe the bug
Trying to run the python example robust.py throws an error Traceback (most recent call last): File "robust.py", line 7, in <module> from tests.python.helpers.utils import load_csv ModuleNotFoundError: No module named 'tests'

I have built everything from the source and did not install using pip command

Environment (please complete the following information):

  • OS: WIndows10 and Ubuntu 18.04

Thanks in advance

Error when importing MatrixDouble

I followed the steps on Polylidar3D installation. But get the error
ImportError: cannot import name 'MatrixDouble'
when running the line

from polylidar import MatrixDouble, Polylidar3D

I am currently running Python version 3.6.13 on a Windows 11 OS with an x86_64 architecture. I am utilizing WSL to run the Python environment.

Polylidar fails due to descartes and shapely incompatibility, solution: remove descartes from requirements including the fixed version

Describe the bug
Shapely with shapely 2.0 updated but the library descartes didn't follow the update.
As result, polylidar fails

In 2022 with shapely 1.8 was warning about the deprecation:
ShapelyDeprecationWarning: The array interface is deprecated and will no longer work in Shapely 2.0. Convert the '.coords' to a numpy array instead.
vertices = concatenate([

The problem is on line 62 of patch.py.
I suggest to remove the integration with descartes (only few lines of code) and integrate the fixed version of PolygonPath, Polygon, PolygonPatch directly in polylidar.

This is the fixed version of patch.py since descartes looks like dead.

"""Paths and patches"""

from matplotlib.patches import PathPatch
from matplotlib.path import Path
from numpy import asarray, concatenate, ones


class Polygon(object):
    # Adapt Shapely or GeoJSON/geo_interface polygons to a common interface
    def __init__(self, context):
        if isinstance(context, dict):
            self.context = context['coordinates']
        else:
            self.context = context

    @property
    def exterior(self):
        return (getattr(self.context, 'exterior', None)
                or self.context[0])

    @property
    def interiors(self):
        value = getattr(self.context, 'interiors', None)
        if value is None:
            value = self.context[1:]
        return value


def PolygonPath(polygon):
    """Constructs a compound matplotlib path from a Shapely or GeoJSON-like
    geometric object"""

    def coding(ob):
        # The codes will be all "LINETO" commands, except for "MOVETO"s at the
        # beginning of each subpath
        n = len(getattr(ob, 'coords', None) or ob)
        vals = ones(n, dtype=Path.code_type) * Path.LINETO
        vals[0] = Path.MOVETO
        return vals

    if hasattr(polygon, 'geom_type'):  # Shapely
        ptype = polygon.geom_type
        if ptype == 'Polygon':
            polygon = [Polygon(polygon)]
        elif ptype == 'MultiPolygon':
            polygon = [Polygon(p) for p in polygon]
        else:
            raise ValueError(
                "A polygon or multi-polygon representation is required")

    else:  # GeoJSON
        polygon = getattr(polygon, '__geo_interface__', polygon)
        ptype = polygon["type"]
        if ptype == 'Polygon':
            polygon = [Polygon(polygon)]
        elif ptype == 'MultiPolygon':
            polygon = [Polygon(p) for p in polygon['coordinates']]
        else:
            raise ValueError(
                "A polygon or multi-polygon representation is required")

    vertices = concatenate([
        concatenate([asarray(t.exterior.coords)[:, :2]] +
                    [asarray(r)[:, :2] for r in t.interiors])
        for t in polygon])
    codes = concatenate([
        concatenate([coding(t.exterior.coords)] +
                    [coding(r) for r in t.interiors]) for t in polygon])

    return Path(vertices, codes)


def PolygonPatch(polygon, **kwargs):
    """Constructs a matplotlib patch from a geometric object

    The `polygon` may be a Shapely or GeoJSON-like object with or without holes.
    The `kwargs` are those supported by the matplotlib.patches.Polygon class
    constructor. Returns an instance of matplotlib.patches.PathPatch.

    Example (using Shapely Point and a matplotlib axes):

      >>> b = Point(0, 0).buffer(1.0)
      >>> patch = PolygonPatch(b, fc='blue', ec='blue', alpha=0.5)
      >>> axis.add_patch(patch)

    """
    return PathPatch(PolygonPath(polygon), **kwargs)

To Reproduce
Just pip install and run the example basic2d.py

Environment (please complete the following information):
Every environment and version

Try to use polylidar with ROS

Hi @JeremyBYU, thank you for sharing your awesome work. I would like to achieve what you did in polylidar-realsense using ROS and C++. However, the C++ tutorials are empty and the c++ example (simple.cpp) might be too simple to let me figure out how to deal with the streaming 3D point cloud. Therefore, could you give me some advice on how to do it?

Python Installation: No module named 'polylidar.polylidar'

I am trying to install the polylidar python package on Windows (Python 3.7; conda 4.9.2).
I first conda install shapely (version 1.7.1) and then pip install polylidar (version 0.0.8).

The installations seem to succeed. However, when I try to import polylidar in Python, I get the following error message: ModuleNotFoundError: No module named 'polylidar.polylidar'

I highly appreciate any advice, thanks in advance!

Error when running realsense_mesh.py example

Describe the bug
When running the realsense_mesh.py script, I get an error suggesting an incorrect argument type on a call to rotate():

  File "examples/python/realsense_mesh.py", line 196, in <module>
    main()
  File "examples/python/realsense_mesh.py", line 188, in main
    pcd = pcd.rotate(R_Standard_d400[:3, :3], center=False)
TypeError: rotate(): incompatible function arguments. The following argument types are supported:
    1. (self: open3d.open3d_pybind.geometry.Geometry3D, R: numpy.ndarray[float64[3, 3]], center: numpy.ndarray[float64[3, 1]]) -> open3d.open3d_pybind.geometry.Geometry3D

Invoked with: geometry::PointCloud with 24259 points., array([[ 1.,  0.,  0.],
       [ 0.,  0.,  1.],
       [ 0., -1.,  0.]]); kwargs: center=FalseTraceback (most recent call last):
  File "examples/python/realsense_mesh.py", line 196, in <module>
    main()
  File "examples/python/realsense_mesh.py", line 188, in main
    pcd = pcd.rotate(R_Standard_d400[:3, :3], center=False)
TypeError: rotate(): incompatible function arguments. The following argument types are supported:
    1. (self: open3d.open3d_pybind.geometry.Geometry3D, R: numpy.ndarray[float64[3, 3]], center: numpy.ndarray[float64[3, 1]]) -> open3d.open3d_pybind.geometry.Geometry3D

Invoked with: geometry::PointCloud with 24259 points., array([[ 1.,  0.,  0.],
       [ 0.,  0.,  1.],
       [ 0., -1.,  0.]]); kwargs: center=False

To Reproduce
Steps to reproduce the behavior:
Simply run realsense_mesh.py.

Expected behavior
I think the problem is that somewhere along the way, an open3d point cloud is being passed around rather than a numpy array, or vice-versa. Obviously, the expected behavior is that it shouldn't crash, but I haven't been able to sort out where exactly the wrong type starts being used.

Environment (please complete the following information):

  • OS: MacOS
  • Architecture: 2.6 GHz Intel Core i7
  • Version: 10.13.6 High Sierra

Additional context
Add any other context about the problem here.

cannot run polylidar-simple

Hi,
I have compiled successfully, however I can't run polylidar-simple, cloud you please tell me what's the problem?

recent:///caaa6a1ad59055fe9355edc15ea904c1

No polygons detected in Airborne Lidar Pointclouds

Hey all,
I am trying to use this repository for the first time, and followed the Python documentation to test a pointcloud of my own. But I could not get any planes in the output. This might be a kwargs issue, which I feel is more of a trial and error task but do you think that might be causing this issue? In that case, what would be your solution and how do i get to these optimum argument values for alpha, lmax, z_threshold and others?

This is the code i am using and I am also attaching a link to the pointcloud in discussion

import polylidar
import math
import numpy as np
from polylidar import MatrixDouble, Polylidar3D
import laspy
import time
import matplotlib.pyplot as plt
from polylidar.polylidarutil import (generate_test_points, plot_triangles, get_estimated_lmax,
                                     plot_triangle_meshes, get_triangles_from_list, get_colored_planar_segments, plot_polygons)

from polylidar.polylidarutil import (plot_polygons_3d, generate_3d_plane, set_axes_equal, plot_planes_3d,
                                     scale_points, rotation_matrix, apply_rotation)
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

# Read LAS file
# las_file_path = 'house1.las'
las_file_path = '/home/tarun/Downloads/house1.las'
las_file = laspy.read(las_file_path)

# Extract x, y, and z coordinates from the LAS points
points = np.vstack((las_file.x, las_file.y, las_file.z)).transpose()

polylidar_kwargs = dict(alpha=0.0, lmax=10, min_triangles=20, z_thresh=0.0, norm_thresh_min=0.94)
polylidar = Polylidar3D(**polylidar_kwargs)

points_mat = MatrixDouble(points, copy=False)
t1 = time.time()
mesh, planes, polygons = polylidar.extract_planes_and_polygons(points_mat)
t2 = time.time()
print("Took {:.2f} milliseconds".format((t2 - t1) * 1000))

triangles = np.asarray(mesh.triangles)
fig, ax = plt.subplots(figsize=(10, 10), nrows=1, ncols=1,
                       subplot_kw=dict(projection='3d'))
# plot all triangles
plot_planes_3d(points, triangles, planes, ax)
plot_polygons_3d(points, polygons, ax)
# plot points
ax.scatter(*scale_points(points), c='k', s=0.1)
set_axes_equal(ax)
ax.view_init(elev=15., azim=-35)
plt.show()
print("")

Link to the pointcloud: https://drive.google.com/file/d/1xuPerTlJ4ScAXkhR_WyrzlSHmZ4KAhYZ/view?usp=sharing

"Segmentation fault" on extract_point_cloud_from_float_depth()

Using Polylidar with Python 3.8 on MacOS. I get "Segmentation fault" when calling extract_point_cloud_from_float_depth() function. Tried both OrganizedDemo.ipynb and in polylidar-realsense's capture

Environment

  • OS: MacOS
  • Architecture x64

On both Ubuntu x64 and ARM, it works correctly. issue only on MacOS (intel)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.