{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T05:46:18Z","timestamp":1783662378956,"version":"3.55.0"},"reference-count":74,"publisher":"MDPI AG","issue":"17","license":[{"start":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T00:00:00Z","timestamp":1598400000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1738714"],"award-info":[{"award-number":["1738714"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Flat surfaces captured by 3D point clouds are often used for localization, mapping, and modeling. Dense point cloud processing has high computation and memory costs making low-dimensional representations of flat surfaces such as polygons desirable. We present Polylidar3D, a non-convex polygon extraction algorithm which takes as input unorganized 3D point clouds (e.g., LiDAR data), organized point clouds (e.g., range images), or user-provided meshes. Non-convex polygons represent flat surfaces in an environment with interior cutouts representing obstacles or holes. The Polylidar3D front-end transforms input data into a half-edge triangular mesh. This representation provides a common level of abstraction for subsequent back-end processing. The Polylidar3D back-end is composed of four core algorithms: mesh smoothing, dominant plane normal estimation, planar segment extraction, and finally polygon extraction. Polylidar3D is shown to be quite fast, making use of CPU multi-threading and GPU acceleration when available. We demonstrate Polylidar3D\u2019s versatility and speed with real-world datasets including aerial LiDAR point clouds for rooftop mapping, autonomous driving LiDAR point clouds for road surface detection, and RGBD cameras for indoor floor\/wall detection. We also evaluate Polylidar3D on a challenging planar segmentation benchmark dataset. Results consistently show excellent speed and accuracy.<\/jats:p>","DOI":"10.3390\/s20174819","type":"journal-article","created":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T09:05:37Z","timestamp":1598432737000},"page":"4819","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Polylidar3D-Fast Polygon Extraction from 3D Data"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5458-9787","authenticated-orcid":false,"given":"Jeremy","family":"Castagno","sequence":"first","affiliation":[{"name":"Robotics Institute, University of Michigan, Ann Arbor, MI 48105, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2132-6256","authenticated-orcid":false,"given":"Ella","family":"Atkins","sequence":"additional","affiliation":[{"name":"Robotics Institute, University of Michigan, Ann Arbor, MI 48105, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1002\/rob.20322","article-title":"Online three-dimensional SLAM by registration of large planar surface segments and closed-form pose-graph relaxation","volume":"27","author":"Pathak","year":"2010","journal-title":"J. Field Robot."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Malihi, S., Valadan Zoej, M.J., Hahn, M., Mokhtarzade, M., and Arefi, H. (2016, January 12\u201319). 3D Building Reconstruction Using Dense Photogrammetric Point Cloud. Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Prague, Czech Republic.","DOI":"10.5194\/isprsarchives-XLI-B3-71-2016"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1016\/j.jas.2009.10.011","article-title":"Terrestrial laser scanning and close range photogrammetry for 3D archaeological documentation: The Upper Palaeolithic Cave of Parpall\u00f3 as a case study","volume":"37","author":"Lerma","year":"2010","journal-title":"J. Archaeol. Sci."},{"key":"ref_4","first-page":"57","article-title":"Generation of visually aesthetic and detailed 3D models of historical cities by using laser scanning and digital photogrammetry","volume":"8","author":"Fritsch","year":"2018","journal-title":"Digit. Appl. Archaeol. Cult. Herit."},{"key":"ref_5","unstructured":"Rusinkiewicz, S., and Levoy, M. (June, January 28). Efficient variants of the ICP algorithm. Proceedings of the Third International Conference on 3-D Digital Imaging and Modeling, Quebec City, QC, Canada."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Feng, C., Taguchi, Y., and Kamat, V.R. (June, January 31). Fast plane extraction in organized point clouds using agglomerative hierarchical clustering. Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA), Hong Kong, China.","DOI":"10.1109\/ICRA.2014.6907776"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Pham, T.T., Eich, M., Reid, I., and Wyeth, G. (2016, January 9\u201314). Geometrically consistent plane extraction for dense indoor 3D maps segmentation. Proceedings of the 2016 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, Korea.","DOI":"10.1109\/IROS.2016.7759618"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Schaefer, A., Vertens, J., Buscher, D., and Burgard, W. (2019, January 20\u201324). A Maximum Likelihood Approach to Extract Finite Planes from 3-D Laser Scans. Proceedings of the 2019 International Conference on Robotics and Automation (ICRA), Montreal, QC, Canada.","DOI":"10.1109\/ICRA.2019.8794318"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Lee, T.k., Lim, S., Lee, S., An, S., and Oh, S.y. (2012, January 7\u201312). Indoor mapping using planes extracted from noisy RGB-D sensors. Proceedings of the 2012 IEEE\/RSJ International Conference on Intelligent Robots and Systems, Vilamoura, Portugal.","DOI":"10.1109\/IROS.2012.6385909"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3684","DOI":"10.1080\/01431161.2017.1302112","article-title":"Roof plane extraction from airborne lidar point clouds","volume":"38","author":"Cao","year":"2017","journal-title":"Int. J. Remote Sens."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Biswas, J., and Veloso, M. (2012, January 7\u201312). Planar polygon extraction and merging from depth images. Proceedings of the 2012 IEEE\/RSJ International Conference on Intelligent Robots and Systems, Vilamoura, Portugal.","DOI":"10.1109\/IROS.2012.6385841"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/978-3-642-33932-5_7","article-title":"Fast Range Image Segmentation and Smoothing Using Approximate Surface Reconstruction and Region Growing","volume":"Volume 194","author":"Lee","year":"2013","journal-title":"Intelligent Autonomous Systems 12"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1109\/TIT.1983.1056714","article-title":"On the shape of a set of points in the plane","volume":"29","author":"Edelsbrunner","year":"1983","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"4634","DOI":"10.1109\/LRA.2020.3002212","article-title":"Polylidar-Polygons From Triangular Meshes","volume":"5","author":"Castagno","year":"2020","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_15","unstructured":"(2020, July 05). Github-Polylidar. Available online: https:\/\/github.com\/JeremyBYU\/polylidar."},{"key":"ref_16","unstructured":"(2020, July 05). Github-Fast Gaussian Sphere Accumulator. Available online: https:\/\/github.com\/JeremyBYU\/FastGaussianAccumulator."},{"key":"ref_17","unstructured":"(2020, July 05). Github-Polylidard3D and KITTI. Available online: https:\/\/github.com\/JeremyBYU\/polylidar-kitti."},{"key":"ref_18","unstructured":"(2020, July 05). Github-Polylidar3D with RealSense. Available online: https:\/\/github.com\/JeremyBYU\/polylidar-realsense."},{"key":"ref_19","unstructured":"(2020, July 05). Github-Polylidard3D and SynPEB. Available online: https:\/\/github.com\/JeremyBYU\/polylidar-plane-benchmark."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1111\/cgf.13451","article-title":"A Survey of Simple Geometric Primitives Detection Methods for Captured 3D Data","volume":"38","author":"Kaiser","year":"2019","journal-title":"Comput. Graph. Forum"},{"key":"ref_21","unstructured":"Trevor, A.J., Gedikli, S., Rusu, R.B., and Christensen, H.I. (2013, January 5). Efficient organized point cloud segmentation with connected components. Proceedings of the Semantic Perception Mapping and Exploration (SPME), Karlsruhe, Germany."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Salas-Moreno, R.F., Glocken, B., Kelly, P.H.J., and Davison, A.J. (2014, January 10\u201312). Dense planar SLAM. Proceedings of the 2014 IEEE International Symposium on Mixed and Augmented Reality (ISMAR), Munich, Germany.","DOI":"10.1109\/ISMAR.2014.6948422"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1111\/cgf.12720","article-title":"Planar Shape Detection and Regularization in Tandem: Planar Shape Detection and Regularization in Tandem","volume":"35","author":"Oesau","year":"2016","journal-title":"Comput. Graph. Forum"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Poppinga, J., Vaskevicius, N., Birk, A., and Pathak, K. (2008, January 22\u201326). Fast plane detection and polygonalization in noisy 3D range images. Proceedings of the 2008 IEEE\/RSJ International Conference on Intelligent Robots and Systems, Nice, France.","DOI":"10.1109\/IROS.2008.4650729"},{"key":"ref_25","unstructured":"Furieri, A. (2020, January 14). Spatialite. Available online: https:\/\/www.gaia-gis.it\/fossil\/libspatialite\/index."},{"key":"ref_26","unstructured":"OSGeo (2020, January 14). PostGIS. Available online: https:\/\/postgis.net\/docs\/ST_ConcaveHull.html."},{"key":"ref_27","unstructured":"(2020, January 05). Github-Benchmark Concave Hull. Available online: https:\/\/github.com\/JeremyBYU\/concavehull-evaluation."},{"key":"ref_28","unstructured":"Taubin, G. (1995, January 20\u201323). Curve and surface smoothing without shrinkage. Proceedings of the of IEEE International Conference on Computer Vision, Cambridge, MA, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1521","DOI":"10.1109\/TVCG.2010.264","article-title":"Bilateral normal filtering for mesh denoising","volume":"17","author":"Zheng","year":"2011","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1109\/TVCG.2007.1065","article-title":"Fast and Effective Feature-Preserving Mesh Denoising","volume":"13","author":"Sun","year":"2007","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/3DRes.02(2011)3","article-title":"The 3D Hough Transform for plane detection in point clouds: A review and a new accumulator design","volume":"2","author":"Borrmann","year":"2011","journal-title":"3D Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"2043","DOI":"10.1016\/j.patcog.2014.12.020","article-title":"Real-time detection of planar regions in unorganized point clouds","volume":"48","author":"Limberger","year":"2015","journal-title":"Pattern Recognit."},{"key":"ref_33","unstructured":"Cohen, T., Weiler, M., Kicanaoglu, B., and Welling, M. (2019, January 10\u201315). Gauge Equivariant Convolutional Networks and the Icosahedral CNN. Proceedings of the 36th International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1007\/s13319-015-0074-3","article-title":"Describing 3D Geometric Primitives Using the Gaussian Sphere and the Gaussian Accumulator","volume":"6","author":"Toony","year":"2015","journal-title":"3D Res."},{"key":"ref_35","unstructured":"Paris, R. (2013). Modified half-edge data structure and its applications to 3D mesh generation for complex tube networks. Electron. Theses Diss."},{"key":"ref_36","unstructured":"Herring, J.R. (2006). OpenGIS Implementation Specification for Geographic Information-Simple Feature Access-Part 1: Common Architecture, Open Geospatial Consortium."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. (2008). Delaunay Triangulations: Height Interpolation. Computational Geometry: Algorithms and Applications, Springer.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref_38","unstructured":"(2020, January 05). Github-Delaunator. Available online: https:\/\/github.com\/mapbox\/delaunator."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/PL00009321","article-title":"Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates","volume":"18","year":"1997","journal-title":"Discret. Comput. Geom."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"29:1","DOI":"10.1145\/2487228.2487237","article-title":"Screened poisson surface reconstruction","volume":"32","author":"Kazhdan","year":"2013","journal-title":"ACM Trans. Graph."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1109\/2945.817351","article-title":"The ball-pivoting algorithm for surface reconstruction","volume":"5","author":"Bernardini","year":"1999","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Zhou, Q.Y., and Koltun, V. (2013). Dense Scene Reconstruction with Points of Interest. ACM Trans. Graph., 32.","DOI":"10.1145\/2461912.2461919"},{"key":"ref_43","unstructured":"Zhou, Q.Y., Park, J., and Koltun, V. (2018). Open3D: A modern library for 3D data processing. arXiv."},{"key":"ref_44","unstructured":"(2020, July 05). Github-Organized Point Filters. Available online: https:\/\/github.com\/JeremyBYU\/OrganizedPointFilters."},{"key":"ref_45","unstructured":"Wenninger, M.J. (1999). Spherical Models, Courier Corporation."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Shekhar, S., and Xiong, H. (2008). Space-Filling Curves. Encyclopedia of GIS, Springer.","DOI":"10.1007\/978-0-387-35973-1"},{"key":"ref_47","unstructured":"Google (2020, July 05). S2 Geometry. Available online: https:\/\/s2geometry.io\/devguide\/s2cell_hierarchy#s2cellid-numbering."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Van Sandt, P., Chronis, Y., and Patel, J.M. (2019). Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?. Proceedings of the 2019 International Conference on Management of Data, Association for Computing Machinery. SIGMOD\u201919.","DOI":"10.1145\/3299869.3300075"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1.3:1","DOI":"10.1145\/3053370","article-title":"Array Layouts for Comparison-Based Searching","volume":"22","author":"Khuong","year":"2017","journal-title":"J. Exp. Algorithmics"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1109\/99.660313","article-title":"OpenMP: An industry standard API for shared-memory programming","volume":"5","author":"Dagum","year":"1998","journal-title":"IEEE Comput. Sci. Eng."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Huang, T.W., Lin, C.X., Guo, G., and Wong, M. (2019, January 20\u201324). Cpp-Taskflow: Fast Task-Based Parallel Programming Using Modern C++. Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Rio de Janeiro, Brazil.","DOI":"10.1109\/IPDPS.2019.00105"},{"key":"ref_52","unstructured":"(2020, July 05). Github-A Hybrid Thread\/Fiber Task Scheduler. Available online: https:\/\/github.com\/google\/marl."},{"key":"ref_53","first-page":"17","article-title":"The Douglas-Peucker line simplification algorithm","volume":"22","author":"Whyatt","year":"1988","journal-title":"Bull.-Soc. Univ. Cartogr."},{"key":"ref_54","unstructured":"Flato, E., and Halperin, D. (2000). Robust and Efficient Construction of Planar Minkowski Sums, University of Tel-Aviv."},{"key":"ref_55","unstructured":"(2020, July 05). Github-Shapely: Manipulation and Analysis of Geometric Objects. Available online: https:\/\/github.com\/Toblerity\/Shapely."},{"key":"ref_56","unstructured":"Blanco, J.L., and Rai, P.K. (2020, July 05). Nanoflann: A C++ Header-Only Fork of FLANN, a Library for Nearest Neighbor (NN) with KD-Trees. Available online: https:\/\/github.com\/jlblancoc\/nanoflann."},{"key":"ref_57","unstructured":"(2020, July 05). Github-Google Benchmark. Available online: https:\/\/github.com\/google\/benchmark."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"e453","DOI":"10.7717\/peerj.453","article-title":"scikit-image: Image processing in Python","volume":"2","author":"Boulogne","year":"2014","journal-title":"PeerJ Inc."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1038\/s41592-019-0686-2","article-title":"SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python","volume":"17","author":"Virtanen","year":"2020","journal-title":"Nat. Methods"},{"key":"ref_60","unstructured":"(2020, July 05). Open Geo Data. Available online: https:\/\/www.opengeodata.nrw.de\/produkte\/geobasis\/hm\/3dm_l_las\/3dm_l_las\/."},{"key":"ref_61","unstructured":"(2020, July 05). Open Geo Data. Available online: https:\/\/www.opengeodata.nrw.de\/produkte\/geobasis\/lbi\/dop\/dop_jp2_f10_paketiert\/."},{"key":"ref_62","unstructured":"(2020, July 05). Data licence Germany - Zero - Version 2.0, Available online: https:\/\/www.govdata.de\/dl-de\/zero-2-0."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.1177\/0278364913491297","article-title":"Vision meets Robotics: The KITTI Dataset","volume":"32","author":"Geiger","year":"2013","journal-title":"Int. J. Robot. Res. (IJRR)"},{"key":"ref_64","unstructured":"Jeremy Castagno (2020, July 30). Polylidar3D Kitti Videos. Available online: https:\/\/drive.google.com\/drive\/folders\/18R0alYprRYgwz5_MyzcdOQzf44496DOz?usp=sharing."},{"key":"ref_65","doi-asserted-by":"crossref","unstructured":"Ahn, M.S., Chae, H., Noh, D., Nam, H., and Hong, D. (2019, January 24\u201327). Analysis and Noise Modeling of the Intel RealSense D435 for Mobile Robots. Proceedings of the 2019 16th International Conference on Ubiquitous Robots (UR), Jeju, Korea.","DOI":"10.1109\/URAI.2019.8768489"},{"key":"ref_66","unstructured":"(2020, July 05). Github-Intel RealSense SDK. Available online: https:\/\/github.com\/IntelRealSense\/librealsense\/blob\/master\/doc\/post-processing-filters.md."},{"key":"ref_67","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1109\/34.506791","article-title":"An experimental comparison of range image segmentation algorithms","volume":"18","author":"Hoover","year":"1996","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_68","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/cviu.1999.0832","article-title":"MLESAC: A New Robust Estimator with Application to Estimating Image Geometry","volume":"78","author":"Torr","year":"2000","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_69","doi-asserted-by":"crossref","unstructured":"Amdahl, G.M. (1967, January 18\u201320). Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities. Proceedings of the Spring Joint Computer Conference, Association for Computing Machinery, AFIPS \u201967 (Spring), New York, NY, USA.","DOI":"10.1145\/1465482.1465560"},{"key":"ref_70","first-page":"3010","article-title":"Airborne light detection and ranging (LiDAR) point density analysis","volume":"7","author":"Avariento","year":"2012","journal-title":"Sci. Res. Essays"},{"key":"ref_71","first-page":"5","article-title":"Random Points: How Dense Are You, Anyway?","volume":"4","author":"Graham","year":"2014","journal-title":"LiDAR News Mag."},{"key":"ref_72","doi-asserted-by":"crossref","unstructured":"Bergelt, R., Khan, O., and Hardt, W. (November, January 29). Improving the intrinsic calibration of a Velodyne LiDAR sensor. Proceedings of the 2017 IEEE SENSORS, Glasgow, UK.","DOI":"10.1109\/ICSENS.2017.8234357"},{"key":"ref_73","unstructured":"(2020, January 05). Github-Intel RealSense Post Processing. Available online: https:\/\/github.com\/IntelRealSense\/librealsense\/blob\/master\/doc\/post-processing-filters.md."},{"key":"ref_74","doi-asserted-by":"crossref","unstructured":"Pham, T.T., Do, T.T., S\u00fcnderhauf, N., and Reid, I. (2018, January 21\u201325). SceneCut: Joint Geometric and Object Segmentation for Indoor Scenes. Proceedings of the 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia.","DOI":"10.1109\/ICRA.2018.8461108"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/17\/4819\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:07:02Z","timestamp":1760177222000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/17\/4819"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,26]]},"references-count":74,"journal-issue":{"issue":"17","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["s20174819"],"URL":"https:\/\/doi.org\/10.3390\/s20174819","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,26]]}}}