Skip to main content

Concave hull by distance

Project description

cdBoundary

A very fast 2.5D concave hull algorithm by distance implemented in Python.

Rather than using a factor between 0 and 1 as most Concave Hull or Alpha Shape algorithms this implementation uses maximum edge length (tol) as a paramater.

The library was needed specific for survey or LiDAR data for engineering applications.

Install

git clone https://github.com/civildot/cdBoundary
cd cdBoundary
python setup.py install

Usage

1. As a library

The points should be in list format with coordinate pairs:
[[x1, y1], [x2, y2], [x3, y3], ...] or
[[x1, y1, z1], [x2, y2, z2], [x3, y3, z3], ...]

All edge lengths exceeding tol parameter will be attempted to be removed. This parameter’s unit will thus be the same as your coordinates. Wether it is meters, feet or degrees.

The ../examples/points-1k.json dataset was borrowed with thanks from concaveman.

import json
from cdBoundary.boundary import ConcaveHull

ch = ConcaveHull()
with open('../examples/points-1k.json') as source:
    pts = json.load(source)
ch.loadpoints(pts)
ch.calculatehull(tol=0.0025)

The result is a shapely Polygon at ch.hull.

print('Geometry type:', ch.hull.geom_type)
coords = ch.boundary_points()
print()
print('The first 5 coordinates of the concave hull is:')
for i in range(5):
    print(i+1, '.', coords[i], sep='')
Geometry type: Polygon

The first 5 coordinates of the concave hull is:
1.(-122.08441, 37.384634)
2.(-122.0832, 37.383161)
3.(-122.08214, 37.3812)
4.(-122.08204, 37.380184)
5.(-122.08216, 37.379173)
ch.plot()

If there is an uncertianty on which value to use for tol the estimate function can be used to provide an estimate. The default percentile perc is 92.5%. At this value only outside border edges longer than 92.5% of all the edges will be attempted to be removed.

print('There is', len(coords), 'vertices on the current polygon.')
print('The suggested value to use is', round(ch.estimate(), 10))
ch.calculatehull(tol=ch.estimate())
print()
print('There is', len(ch.boundary_points()), 'vertices on the new polygon.')
There is 83 vertices on the current polygon.
The suggested value to use is 0.0017366632

There is 164 vertices on the new polygon.

The low value for the estimate() (much smaller than 1) suggest that the coordinates are in degress. When working in feet or meters it will be much larger.

ch.plot()

2. Working directly with files

Fiona is used to read point data directly from files. The resulting Polygon can also be written to the file format supported by Fiona.

from cdBoundary.fileio import FileIO

fch = FileIO()
fch.file2points('../examples/Bandelierkop_survey.shp')
fch.write2file(tol=35)

In the same folder as your input file there is now a file named concave_hull.shp (default) containing the concave hull as a polygon.

or

with open('../examples/points-1k.json') as source:
    pts = json.load(source)
fch = FileIO()
fch.loadpoints(pts)
fch.calculatehull(tol=ch.estimate())
fch.write2file(outfile='../examples/concave_hull2.shp', driver='ESRI Shapefile')

Documentation

https://civildot.github.io/cdBoundary

Requirements / Dependencies

Algorithm

This concave hull implementation is based on the algorithm developed by Duckham et al. (2008) in the paper “Efficient generation of simple polygons for characterizing the shape of a set of points in the plane”, available here.

Wish list

Possible features or enhancements in the future. Nothing planned. The library is already satisfactory for our speicific application.

  • Plot output for quick visualization Implemented 15 July 2023
  • Support an elevation (Z value) on the polygon vertices Implemented 15 July 2023
  • Support for holes
  • cli (Command Line Interface)
  • Provide as a QGIS Plugin
  • Implement it as a Streamlit application

Similar Implementations

A lot of concave-hull and alpha-shape implementations on Github, but very few using maximum edge length as an argument.

  1. The greatest influence on cdBoundary is http://www.rotefabrik.free.fr/concave_hull which can be accessed through the OpenJUMP user interface.
  2. The lasboundary command line program from LASTools is unfortunately proprierity but also edge length as an argument and is very powerful.
  3. MacRoad, later HighRoad, an ancient road design and earthworks program. Still being used today but no longer actively maintained. It has a Join Edge Points function which is a concave hull implementation already implemented in 1988. It has an estimate button which inspired the estimate function for cdBoundary.
  4. jtsop from the JTS (Java Topology Suite) has got a Construction.concaveHullByLen function as well.

Project details


Release history Release notifications | RSS feed

This version

0.8

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

cdBoundary-0.8.tar.gz (12.2 kB view details)

Uploaded Source

Built Distribution

cdBoundary-0.8-py3-none-any.whl (9.5 kB view details)

Uploaded Python 3

File details

Details for the file cdBoundary-0.8.tar.gz.

File metadata

  • Download URL: cdBoundary-0.8.tar.gz
  • Upload date:
  • Size: 12.2 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.11.3

File hashes

Hashes for cdBoundary-0.8.tar.gz
Algorithm Hash digest
SHA256 b642181fa5934befe80d6a2c86a443ca5cb13ce3cf7c4d903beb6680f7135e7e
MD5 292248d163a4740d67b0a027da8e53ed
BLAKE2b-256 d3f0b33d53692edf2dd89205189c5e04290c4d6d1b7ae4f131b70f6ac1efb748

See more details on using hashes here.

File details

Details for the file cdBoundary-0.8-py3-none-any.whl.

File metadata

  • Download URL: cdBoundary-0.8-py3-none-any.whl
  • Upload date:
  • Size: 9.5 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.11.3

File hashes

Hashes for cdBoundary-0.8-py3-none-any.whl
Algorithm Hash digest
SHA256 6142658a3bad7f8d597aca3d9c0d93c28bb162079ea5e3ed9027fd3497d38538
MD5 bec3621ad7c7a190a9d6debe2e9c3aa7
BLAKE2b-256 26eb8b18022be46bce216efcfaab63de09adeb1099a464703c7ebe68f7f05bc2

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page