API Reference

AbstractConvexHull{T}

Abstract supertype for all convex hull types over 2-D points of type T.

Concrete subtypes: MutableConvexHull, MutableLowerConvexHull, MutableUpperConvexHull, ChanConvexHull, ChanLowerConvexHull, ChanUpperConvexHull.

AbstractChanConvexHull{T}

Abstract supertype for convex hulls that distribute their points across multiple MutableConvexHull-style sub-hulls and merge the results.

Concrete subtypes are ChanConvexHull, ChanLowerConvexHull, and ChanUpperConvexHull. They support the same incremental operations as their Mutable* counterparts (addpoint!, mergepoints!, removepoint!, insidehull) but do not accept mergehulls!/mergehulls.

h = MutableConvexHull{T}(; orientation=CCW, collinear=false, sortedby=identity)

A mutable convex hull over 2-D points of type T (e.g., Tuple{Float64,Float64}), supporting incremental addition and removal of points. Iterating h yields the hull-vertex sequence in the specified orientation.

Initialize an empty hull with the provided attributes.

orientation specifies whether the points along the convex hull are ordered clockwise CW, or counterclockwise CCW, and defaults to CCW.

collinear specifies whether collinear points are allowed along the surface of the convex hull, and defaults to false.

sortedby specifies a function to apply to points prior to sorting, and defaults to identity (resulting in default sorting behavior).

See also: monotonechain, jarvismarch, addpoint!, mergepoints!, removepoint!

h = ChanConvexHull{T}(; orientation=CCW, collinear=false, sortedby=identity)

A full convex hull that distributes its points across multiple MutableConvexHull sub-hulls and merges them on demand. Supports the same keyword arguments and incremental operations as MutableConvexHull, but does not accept mergehulls!/mergehulls.

See also: ChanLowerConvexHull, ChanUpperConvexHull, addpoint!, mergepoints!, removepoint!

h = MutableLowerConvexHull{T}(; orientation=CCW, collinear=false, sortedby=identity)

A mutable lower convex hull over 2-D points of type T (e.g., Tuple{Float64,Float64}): the chain of hull vertices from the leftmost to the rightmost point along the bottom boundary. Supports the same incremental operations as MutableConvexHull.

Initialize an empty hull with the provided attributes.

orientation specifies whether the points along the convex hull are ordered clockwise CW, or counterclockwise CCW, and defaults to CCW.

collinear specifies whether collinear points are allowed along the surface of the convex hull, and defaults to false.

sortedby specifies a function to apply to points prior to sorting, and defaults to identity (resulting in default sorting behavior).

See also: lower_monotonechain, lower_jarvismarch, addpoint!, mergepoints!, removepoint!

h = ChanLowerConvexHull{T}(; orientation=CCW, collinear=false, sortedby=identity)

A lower convex hull that distributes its points across multiple MutableLowerConvexHull sub-hulls and merges them on demand. The lower hull spans from the leftmost to the rightmost point along the bottom boundary. Supports the same keyword arguments and incremental operations as MutableLowerConvexHull, but does not accept mergehulls!/mergehulls.

See also: ChanConvexHull, ChanUpperConvexHull, addpoint!, mergepoints!, removepoint!

h = MutableUpperConvexHull{T}(; orientation=CCW, collinear=false, sortedby=identity)

A mutable upper convex hull over 2-D points of type T (e.g., Tuple{Float64,Float64}): the chain of hull vertices from the leftmost to the rightmost point along the top boundary. Supports the same incremental operations as MutableConvexHull.

Initialize an empty hull with the provided attributes.

orientation specifies whether the points along the convex hull are ordered clockwise CW, or counterclockwise CCW, and defaults to CCW.

collinear specifies whether collinear points are allowed along the surface of the convex hull, and defaults to false.

sortedby specifies a function to apply to points prior to sorting, and defaults to identity (resulting in default sorting behavior).

See also: upper_monotonechain, upper_jarvismarch, addpoint!, mergepoints!, removepoint!

h = ChanUpperConvexHull{T}(; orientation=CCW, collinear=false, sortedby=identity)

An upper convex hull that distributes its points across multiple MutableUpperConvexHull sub-hulls and merges them on demand. The upper hull spans from the leftmost to the rightmost point along the top boundary. Supports the same keyword arguments and incremental operations as MutableUpperConvexHull, but does not accept mergehulls!/mergehulls.

See also: ChanConvexHull, ChanLowerConvexHull, addpoint!, mergepoints!, removepoint!

h = monotonechain(points [; orientation, collinear, sortedby])

Return a MutableConvexHull containing the convex hull of the provided points.

points may be a vector of points or an AbstractMatrix in which each row is one point.

orientation specifies whether the points along the convex hull are ordered clockwise CW, or counterclockwise CCW, and defaults to CCW.

collinear specifies whether collinear points are allowed along the surface of the convex hull, and defaults to false.

sortedby specifies a function to apply to points prior to sorting, and defaults to identity (resulting in default sorting behavior).

Examples

julia> points = [(0.0, 0.0), (1.0, 0.0), (0.5, 0.5), (1.0, 1.0), (0.0, 1.0)];

julia> monotonechain(points)
MutableConvexHull{Tuple{Float64, Float64}, typeof(identity)}((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0))

lh = lower_monotonechain(points [; orientation, collinear, sortedby])

Return a MutableLowerConvexHull containing the lower convex hull of the provided points.

points may be a vector of points or an AbstractMatrix in which each row is one point.

orientation specifies whether the points along the convex hull are ordered clockwise CW, or counterclockwise CCW, and defaults to CCW.

collinear specifies whether collinear points are allowed along the surface of the convex hull, and defaults to false.

sortedby specifies a function to apply to points prior to sorting, and defaults to identity (resulting in default sorting behavior).

uh = upper_monotonechain(points [; orientation, collinear, sortedby])

Return a MutableUpperConvexHull containing the upper convex hull of the provided points.

points may be a vector of points or an AbstractMatrix in which each row is one point.

orientation specifies whether the points along the convex hull are ordered clockwise CW, or counterclockwise CCW, and defaults to CCW.

collinear specifies whether collinear points are allowed along the surface of the convex hull, and defaults to false.

sortedby specifies a function to apply to points prior to sorting, and defaults to identity (resulting in default sorting behavior).

h = jarvismarch(points [; orientation, collinear, sortedby])

Return a MutableConvexHull containing the convex hull of the provided points.

points may be a vector of points or an AbstractMatrix in which each row is one point.

orientation specifies whether the points along the convex hull are ordered clockwise CW, or counterclockwise CCW, and defaults to CCW.

collinear specifies whether collinear points are allowed along the surface of the convex hull, and defaults to false.

sortedby specifies a function to apply to points prior to sorting, and defaults to identity (resulting in default sorting behavior).

lh = lower_jarvismarch(points [; orientation, collinear, sortedby])

Return a MutableLowerConvexHull containing the lower convex hull of the provided points.

points may be a vector of points or an AbstractMatrix in which each row is one point.

orientation specifies whether the points along the convex hull are ordered clockwise CW, or counterclockwise CCW, and defaults to CCW.

collinear specifies whether collinear points are allowed along the surface of the convex hull, and defaults to false.

sortedby specifies a function to apply to points prior to sorting, and defaults to identity (resulting in default sorting behavior).

uh = upper_jarvismarch(points [; orientation, collinear, sortedby])

Return a MutableUpperConvexHull containing the upper convex hull of the provided points.

points may be a vector of points or an AbstractMatrix in which each row is one point.

orientation specifies whether the points along the convex hull are ordered clockwise CW, or counterclockwise CCW, and defaults to CCW.

collinear specifies whether collinear points are allowed along the surface of the convex hull, and defaults to false.

sortedby specifies a function to apply to points prior to sorting, and defaults to identity (resulting in default sorting behavior).

addpoint!(hull, point)

Add point to the list of points contained by the provided convex hull hull. If point lies outside the convex hull, the list of hull points will be updated accordingly.

Return (hull, expanded) where expanded is true if the added point expands the hull and false if it lies inside or on the boundary.

Examples

julia> h = MutableConvexHull{Tuple{Float64,Float64}}();

julia> h, _ = addpoint!(h, (0.0, 0.0)); h, _ = addpoint!(h, (1.0, 0.0));

julia> h, expanded = addpoint!(h, (0.0, 1.0));

julia> expanded
true

julia> h, expanded = addpoint!(h, (0.25, 0.25));

julia> expanded
false

See also: mergepoints!, removepoint!

mergepoints!(hull, points)

Add points to the list of points contained by the provided convex hull hull. If any of the points lie outside the convex hull, the list of hull points will be updated accordingly.

points may be a vector of points or an AbstractMatrix in which each row is one point.

This function finds the convex hull of the points to be added before merging them with the hull. See Chan's algorithm for a similar idea.

Return hull.

See also: addpoint!, removepoint!

removepoint!(hull, node)

Remove node from hull. node may be a HullNode (a vertex on the hull boundary) or a PointNode (any tracked point, inside or on the boundary). If removing node alters the hull boundary, it is recomputed.

Return (hull, removed) where removed is true if a hull-boundary vertex was removed and false if an interior or duplicate point was removed.

See also: addpoint!, mergepoints!

removepoint!(hull, value)

Locate the point equal to value in hull and remove it, delegating to removepoint!(hull, node). Throws an ArgumentError if no point equal to value is contained in hull.

Return (hull, removed) where removed is true if a hull-boundary vertex was removed and false if an interior or duplicate point was removed.

Examples

julia> h = monotonechain([(0.0, 0.0), (1.0, 0.0), (0.0, 1.0), (0.25, 0.25)]);

julia> h, removed = removepoint!(h, (0.25, 0.25));

julia> removed  # interior point; hull boundary unchanged
false

julia> h, removed = removepoint!(h, (1.0, 0.0));

julia> removed  # hull vertex; boundary recomputed
true

julia> h
MutableConvexHull{Tuple{Float64, Float64}, typeof(identity)}((0.0, 0.0), (0.0, 1.0))

See also: addpoint!, mergepoints!

mergehulls!(hull, otherhulls...)

Merge the points contained in otherhulls into hull and return hull. All arguments must be the same concrete hull type (MutableConvexHull, MutableLowerConvexHull, or MutableUpperConvexHull); AbstractChanConvexHull subtypes are not accepted. See Chan's algorithm for a similar approach.

mergehulls(hull, otherhulls...)

Return a new hull of the same type as hull containing the points of hull and otherhulls, without mutating any argument. See mergehulls! for the in-place form.

insidehull(data, hull) -> Bool

Return true if data lies inside hull and false otherwise.

data must be a 2-D indexable point, supporting data[1] and data[2]; a scalar or other non-indexable value raises a BoundsError.

Boundary handling is governed by hull.collinear. Points that exactly coincide with a hull vertex always count as inside. For non-vertex boundary points, the default collinear=false treats hull edges as inside; collinear=true treats them as outside (so they will be added to the hull on merge).

Counterclockwise hull orientation: hull vertices are listed in counterclockwise order. See also CW.

Clockwise hull orientation: hull vertices are listed in clockwise order. See also CCW.

HullNodeIterator(start[; rev=false])

Return an iterator over the HullNode elements in the convex hull's linked list, starting at start.

If rev is true, the iterator advances toward the head of the list. Otherwise, it advances toward the tail.

HullNodeIterator(hull[; rev=false])

Return an iterator over the HullNode elements in the convex hull's linked list.

If rev is true, iteration starts at the tail and advances toward the head. Otherwise, it starts at the head and advances toward the tail.

PointNodeIterator(start[; rev=false])

Return an iterator over the PointNode elements in the hull's point list, starting at start.

If rev is true, the iterator advances toward the head of the list. Otherwise, it advances toward the tail.

PointNodeIterator(hull[; rev=false])

Return an iterator over the PointNode elements in the hull's point list.

If rev is true, iteration starts at the tail and advances toward the head. Otherwise, it starts at the head and advances toward the tail.

HullList{T,F}

A doubly-linked list of hull vertices of type T, sorted by function F. Each element is a HullNode. Accessible as h.hull on any convex hull; iterate with MutableConvexHulls.HullNodeIterator, or iterate the hull directly.

PointList{T,...}

A sorted skip-list of all 2-D points of type T tracked by a hull — hull vertices and interior points alike. Accessible as h.points on any convex hull; iterate with MutableConvexHulls.PointNodeIterator.

HullNode{T,...}

A node in a HullList, carrying one hull-vertex value of type T. Accessible as elements of a hull's h.hull list; iterate with MutableConvexHulls.HullNodeIterator.

PointNode{T,...}

A node in a PointList, carrying a tracked 2-D point of type T. Every point passed to a hull — hull vertex or interior point — is stored as a PointNode. Accessible as elements of a hull's h.points list; iterate over them with MutableConvexHulls.PointNodeIterator.