# cdBoundary
<!-- WARNING: THIS FILE WAS AUTOGENERATED! DO NOT EDIT! -->
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
``` sh
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](https://github.com/mapbox/concaveman).
``` python
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`.
``` python
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)
``` python
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.
``` python
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.
``` python
ch.plot()
```
### 2. Working directly with files
[Fiona](https://github.com/Toblerity/Fiona) is used to read point data
directly from files. The resulting `Polygon` can also be written to the
file format supported by `Fiona`.
``` python
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
``` python
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](https://civildot.github.io/cdBoundary/)
## Requirements / Dependencies
- [shapely](https://github.com/shapely/shapely)
- [matplotlib](https://github.com/matplotlib/matplotlib)
- [numpy](https://github.com/numpy/numpy)
- [Fiona](https://github.com/Toblerity/Fiona) \>= 1.9.4
## 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](http://www.geosensor.net/papers/duckham08.PR.pdf).
## 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](https://github.com/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](http://www.openjump.org/) user
interface.
2. The `lasboundary` command line program from
**[LASTools](https://lastools.github.io/)** is unfortunately
proprierity but also edge length as an argument and is very
powerful.
3. MacRoad, later
**[HighRoad](http://www.interstudio.net/highroade.html)**, 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](https://github.com/locationtech/jts/blob/master/doc/JTSOp.md)**
from the *JTS* (Java Topology Suite) has got a
`Construction.concaveHullByLen` function as well.
Raw data
{
"_id": null,
"home_page": "https://github.com/civildot/cdBoundary",
"name": "cdBoundary",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "nbdev jupyter notebook python",
"author": "Andr\u00e9 Kruger",
"author_email": "andrelester32@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/d3/f0/b33d53692edf2dd89205189c5e04290c4d6d1b7ae4f131b70f6ac1efb748/cdBoundary-0.8.tar.gz",
"platform": null,
"description": "# cdBoundary\n\n<!-- WARNING: THIS FILE WAS AUTOGENERATED! DO NOT EDIT! -->\n\nA very fast 2.5D **concave hull** algorithm by distance implemented in\nPython.\n\nRather than using a factor between 0 and 1 as most *Concave Hull* or\n*Alpha Shape* algorithms this implementation uses *maximum edge length*\n(`tol`) as a paramater.\n\nThe library was needed specific for *survey* or *LiDAR* data for\nengineering applications.\n\n## Install\n\n``` sh\ngit clone https://github.com/civildot/cdBoundary\ncd cdBoundary\npython setup.py install\n```\n\n## Usage\n\n### 1. As a library\n\nThe points should be in list format with coordinate pairs: \n`[[x1, y1], [x2, y2], [x3, y3], ...]` or \n`[[x1, y1, z1], [x2, y2, z2], [x3, y3, z3], ...]`\n\nAll edge lengths exceeding `tol` parameter will be attempted to be\nremoved. This parameter\u2019s unit will thus be the same as your\ncoordinates. Wether it is meters, feet or degrees.\n\nThe `../examples/points-1k.json` dataset was borrowed with thanks from\n[concaveman](https://github.com/mapbox/concaveman).\n\n``` python\nimport json\nfrom cdBoundary.boundary import ConcaveHull\n\nch = ConcaveHull()\nwith open('../examples/points-1k.json') as source:\n pts = json.load(source)\nch.loadpoints(pts)\nch.calculatehull(tol=0.0025)\n```\n\nThe result is a `shapely` Polygon at `ch.hull`.\n\n``` python\nprint('Geometry type:', ch.hull.geom_type)\ncoords = ch.boundary_points()\nprint()\nprint('The first 5 coordinates of the concave hull is:')\nfor i in range(5):\n print(i+1, '.', coords[i], sep='')\n```\n\n Geometry type: Polygon\n\n The first 5 coordinates of the concave hull is:\n 1.(-122.08441, 37.384634)\n 2.(-122.0832, 37.383161)\n 3.(-122.08214, 37.3812)\n 4.(-122.08204, 37.380184)\n 5.(-122.08216, 37.379173)\n\n``` python\nch.plot()\n```\n\n\n\nIf there is an uncertianty on which value to use for `tol` the\n`estimate` function can be used to provide an estimate. The default\npercentile `perc` is 92.5%. At this value only outside border edges\nlonger than 92.5% of all the edges will be attempted to be removed.\n\n``` python\nprint('There is', len(coords), 'vertices on the current polygon.')\nprint('The suggested value to use is', round(ch.estimate(), 10))\nch.calculatehull(tol=ch.estimate())\nprint()\nprint('There is', len(ch.boundary_points()), 'vertices on the new polygon.')\n```\n\n There is 83 vertices on the current polygon.\n The suggested value to use is 0.0017366632\n\n There is 164 vertices on the new polygon.\n\nThe low value for the `estimate()` *(much smaller than 1)* suggest that\nthe coordinates are in degress. When working in feet or meters it will\nbe much larger.\n\n``` python\nch.plot()\n```\n\n\n\n### 2. Working directly with files\n\n[Fiona](https://github.com/Toblerity/Fiona) is used to read point data\ndirectly from files. The resulting `Polygon` can also be written to the\nfile format supported by `Fiona`.\n\n``` python\nfrom cdBoundary.fileio import FileIO\n\nfch = FileIO()\nfch.file2points('../examples/Bandelierkop_survey.shp')\nfch.write2file(tol=35)\n```\n\nIn the same folder as your input file there is now a file named\n`concave_hull.shp` *(default)* containing the concave hull as a polygon.\n\nor\n\n``` python\nwith open('../examples/points-1k.json') as source:\n pts = json.load(source)\nfch = FileIO()\nfch.loadpoints(pts)\nfch.calculatehull(tol=ch.estimate())\nfch.write2file(outfile='../examples/concave_hull2.shp', driver='ESRI Shapefile')\n```\n\n## Documentation\n\n[https://civildot.github.io/cdBoundary](https://civildot.github.io/cdBoundary/)\n\n## Requirements / Dependencies\n\n- [shapely](https://github.com/shapely/shapely)\n- [matplotlib](https://github.com/matplotlib/matplotlib)\n- [numpy](https://github.com/numpy/numpy)\n- [Fiona](https://github.com/Toblerity/Fiona) \\>= 1.9.4\n\n## Algorithm\n\nThis concave hull implementation is based on the algorithm developed by\nDuckham et al.\u00a0(2008) in the paper \u201cEfficient generation of simple\npolygons for characterizing the shape of a set of points in the plane\u201d,\navailable [here](http://www.geosensor.net/papers/duckham08.PR.pdf).\n\n## Wish list\n\nPossible features or enhancements in the future. Nothing planned. The\nlibrary is already satisfactory for our speicific application.\n\n- ~~Plot output for quick visualization~~ *Implemented 15 July 2023*\n- ~~Support an elevation (Z value) on the polygon vertices~~\n *Implemented 15 July 2023*\n- Support for holes\n- cli (Command Line Interface)\n- Provide as a QGIS Plugin\n- Implement it as a [Streamlit](https://github.com/streamlit)\n application\n\n## Similar Implementations\n\nA lot of *concave-hull* and *alpha-shape* implementations on Github, but\nvery few using maximum edge length as an argument.\n\n1. The greatest influence on *cdBoundary* is\n **<http://www.rotefabrik.free.fr/concave_hull>** which can be\n accessed through the [OpenJUMP](http://www.openjump.org/) user\n interface.\n2. The `lasboundary` command line program from\n **[LASTools](https://lastools.github.io/)** is unfortunately\n proprierity but also edge length as an argument and is very\n powerful.\n3. MacRoad, later\n **[HighRoad](http://www.interstudio.net/highroade.html)**, an\n ancient road design and earthworks program. Still being used today\n but no longer actively maintained. It has a `Join Edge Points`\n function which is a concave hull implementation already implemented\n in 1988. It has an `estimate` button which inspired the `estimate`\n function for cdBoundary.\n4. **[jtsop](https://github.com/locationtech/jts/blob/master/doc/JTSOp.md)**\n from the *JTS* (Java Topology Suite) has got a\n `Construction.concaveHullByLen` function as well.\n",
"bugtrack_url": null,
"license": "MIT License",
"summary": "Concave hull by distance",
"version": "0.8",
"project_urls": {
"Homepage": "https://github.com/civildot/cdBoundary"
},
"split_keywords": [
"nbdev",
"jupyter",
"notebook",
"python"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "26eb8b18022be46bce216efcfaab63de09adeb1099a464703c7ebe68f7f05bc2",
"md5": "bec3621ad7c7a190a9d6debe2e9c3aa7",
"sha256": "6142658a3bad7f8d597aca3d9c0d93c28bb162079ea5e3ed9027fd3497d38538"
},
"downloads": -1,
"filename": "cdBoundary-0.8-py3-none-any.whl",
"has_sig": false,
"md5_digest": "bec3621ad7c7a190a9d6debe2e9c3aa7",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 9515,
"upload_time": "2023-07-15T12:27:39",
"upload_time_iso_8601": "2023-07-15T12:27:39.986604Z",
"url": "https://files.pythonhosted.org/packages/26/eb/8b18022be46bce216efcfaab63de09adeb1099a464703c7ebe68f7f05bc2/cdBoundary-0.8-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "d3f0b33d53692edf2dd89205189c5e04290c4d6d1b7ae4f131b70f6ac1efb748",
"md5": "292248d163a4740d67b0a027da8e53ed",
"sha256": "b642181fa5934befe80d6a2c86a443ca5cb13ce3cf7c4d903beb6680f7135e7e"
},
"downloads": -1,
"filename": "cdBoundary-0.8.tar.gz",
"has_sig": false,
"md5_digest": "292248d163a4740d67b0a027da8e53ed",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 12152,
"upload_time": "2023-07-15T12:27:42",
"upload_time_iso_8601": "2023-07-15T12:27:42.094429Z",
"url": "https://files.pythonhosted.org/packages/d3/f0/b33d53692edf2dd89205189c5e04290c4d6d1b7ae4f131b70f6ac1efb748/cdBoundary-0.8.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-07-15 12:27:42",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "civildot",
"github_project": "cdBoundary",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "cdboundary"
}
JSON
