Concave hull
In computer graphics, and geographic information systems (GIS) the concave hull of a set of points in the plane is the area occupied by the points in the plane. In the generic situation, the concave hull represents a better approximation to the area actually taken up than the convex hull, because it will take into account concave outlines. There is usually not one unique solution, rather certain tolerance parameters[1][2] have to be introduced into the algorithm that determine the jaggedness of the outline.
The area enclosed by the concave hull is always less than or equal to that of the convex hull.
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.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 External link in
|title=
(help) - Emil Rosén, Emil Jansson, Michelle Brundin (2014). "Implementation of a fast and efficient concave hull algorithm" (PDF). INSTITUTIONEN FÖR INFORMATIONSTEKNOLOGI, Uppsala Universitet. line feed character in
|title=
at position 29 (help)CS1 maint: Multiple names: authors list (link)
This geometry-related article is a stub. You can help EverybodyWiki by expanding it. |
This article "Concave hull" is from Wikipedia. The list of its authors can be seen in its historical. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.