In computer graphics and geographic information systems, a concave hull of a set of points in space is a region enclosing the points which, can be concave. This is in contrast to the convex hull which is always a convex set. As such it may be a better representation of the area or volume spanned by the points than the convex hull.
Unlike the convex hull, a concave hull is not unique for a given set of points. It can depend on the algorithm used and the tolerances of the algorithm, such as for how jagged its outline is.[1][2] It should always be no bigger than the convex hull though. Predefined routines or commands for computation of a concave hull exist in common GIS systems, e.g. SDO_GEOM.SDO_CONCAVEHULL in Oracle Spatial,[1] ST_ConcaveHull in PostGIS,[3] v.concave.hull in GRASS GIS,[4] and lasboundary in LAStools.[5]
See also edit
Notes edit
References edit
- Jin -Seo Park and SE-Jong Oh (2012). "A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets" (PDF). Journal of Information Science and Engineering. 28: 587–600.
- Matt Duckham, Lars Kulik, Mike Worboys, Antony Galton (2008). "Efficient generation of simple polygons for characterizing the shape of a set of points in the plane" (PDF). doi:10.1016/j.patcog.2008.03.023.
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link) - Antony Galton (2008-03-08). "What makes a good footprint?" (PDF). University of Exeter.
- Moreira, A.; Santos, M.Y. (2007), "Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points", [http://www.grapp.visigrapp.org/Abstracts/2007/GRAPP_2007_Abstracts.htm International Conference on Computer Graphics Theory and Applications GRAPP (2007)] (PDF), retrieved 10 October 2014
{{citation}}: External link in|title= - Emil Rosén, Emil Jansson, Michelle Brundin (2014). "Implementation of a fast and efficient concave hull algorithm" (PDF). INSTITUTIONEN FÖR INFORMATIONSTEKNOLOGI, Uppsala Universitet.
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link) - http://patentscope.wipo.int/search/en/WO2008107859
Category:Computer graphics Category:Geometry Category:Geometric algorithms
 | This geometry-related article is a stub. You can help Wikipedia by expanding it. |
In computer graphics and geographic information systems, a concave hull of a set of points in space is a region enclosing the points which, can be concave. This is in contrast to the convex hull which is always a convex set. As such it may be a better representation of the area or volume spanned by the points than the convex hull.
Unlike the convex hull, the concave hull is not unique for a general set of points. It can depend on the algorithm used and the tolerances of the algorithm, such as for how jagged its outline is.[1][2] It should always be no bigger than the convex hull though. Predefined routines for computation of the concave hull exist in common GIS systems, e.g. SDO_GEOM.SDO_CONCAVEHULL in Oracle Spatial[1] and ST_ConcaveHull in PostGIS.[3]
See also edit
Notes edit
References edit
- Matt Duckham, Lars Kulik, Mike Worboys, Antony Galton (2008). "Efficient generation of simple polygons for characterizing the shape of a set of points in the plane" (PDF). doi:10.1016/j.patcog.2008.03.023.
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link) - Antony Galton (2008-03-08). "What makes a good footprint?" (PDF). University of Exeter.
- Moreira, A.; Santos, M.Y. (2007), "Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points", [http://www.grapp.visigrapp.org/Abstracts/2007/GRAPP_2007_Abstracts.htm International Conference on Computer Graphics Theory and Applications GRAPP (2007)] (PDF), retrieved 10 October 2014
{{citation}}: External link in|title= - Emil Rosén, Emil Jansson, Michelle Brundin (2014). "Implementation of a fast and efficient concave hull algorithm" (PDF). INSTITUTIONEN FÖR INFORMATIONSTEKNOLOGI, Uppsala Universitet.
{{cite journal}}: Cite journal requires|journal=(help); line feed character in|title=at position 29 (help)CS1 maint: multiple names: authors list (link)
Category:Computer graphics Category:Geometry Category:Geometric algorithms
| | This geometry-related article is a stub. You can help Wikipedia by expanding it. |