Jump to content

User:Kku/Concave hull

From Wikipedia, the free encyclopedia
Concave hull of a set of points in the plane (lines a + c) vs. convex hull (lines a + v). Outline a+c' will be the result of a more restrictive tolerance parameter setting.

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]
  1. ^ a b http://docs.oracle.com/cd/E11882_01/appdev.112/e11830/sdo_objgeom.htm#SPATL1419
  2. ^ http://ubicomp.algoritmi.uminho.pt/local/concavehull.html
  3. ^ "ST_ConcaveHull". PostGIS Manual.
  4. ^ http://grass.osgeo.org/grass70/manuals/addons/v.concave.hull.html
  5. ^ http://rapidlasso.com/lastools/lasboundary/

References

[edit]

Category:Computer graphics Category:Geometry Category:Geometric algorithms


Concave hull of a set of points in the plane (lines a + c) vs. convex hull (lines a + v). Outline a+c' will be the result of a more restrictive tolerance parameter setting.

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]

Category:Computer graphics Category:Geometry Category:Geometric algorithms