Convex Hull

Author(s)	O.Conrad (c) 2011
Library ID	shapes_points
Tool ID	12
Version	1.0
Menu	Shapes \| Tools

Description

Implementation of 'Andrew's Monotone Chain Algorithm' for convex hull construction.

References

Andrew, A.M. (1979): Another Efficient Algorithm for Convex Hulls in Two Dimensions. Info. Proc. Letters 9, pp.216-219.

Sunday, D. (2001-2006): The Convex Hull of a 2D Point Set or Polygon. Geometry Algorithms Home. (Web site with source code)

The Algorithmist (9 November 2011): Monotone Chain Convex Hull. (source code)

Parameters

	Name	Type	Identifier	Description	Constraints
Input	Points	shapes, input	`SHAPES`	-	-
Output	Convex Hull	shapes, output	`HULLS`	-	-
Output	Minimum Bounding Box	shapes, output, optional	`BOXES`	-	-
Options	Object Identifier	table field	`FIELD`	-	-
	Hull Construction	choice	`POLYPOINTS`	This option does not apply to simple point layers.	Available Choices: [0] one hull for all shapes [1] one hull per shape [2] one hull per shape part Default: 1
	Polygon Convexity	boolean	`POLYGONCVX`	Describes a polygon's compactness as ratio of its area to its hull's area.	Default: 0

Command Line


Usage: saga_cmd shapes_points 12 [-SHAPES ] [-FIELD ] [-HULLS ] [-BOXES ] [-POLYPOINTS ] [-POLYGONCVX ]
  -SHAPES:       Points
	shapes, input
  -FIELD:        Object Identifier
	table field
  -HULLS:        Convex Hull
	shapes, output
  -BOXES:        Minimum Bounding Box
	shapes, output, optional
  -POLYPOINTS:
                      Hull Construction
                      	choice
                      	Available Choices:
                      	[0] one hull for all shapes
                      	[1] one hull per shape
                      	[2] one hull per shape part
                      	Default: 1
  -POLYGONCVX:   Polygon Convexity
	boolean
	Default: 0