convex hull example script

The following script computes the convex hull of polygons with one ring each, by repeatedly dropping the corners where a ring turns inward. GeoDMS ships it as examples\convex_hull.dms, with three test shapes and checks of the result; there Shapes is a domain with a polygon attribute geometry_rd in the coordinate unit geometries/rdc.

the script

container lib
{
	// One step: the points of the rings in seq, without the points where a ring turns left.
	// seq holds the points of each ring in order, the first point of a ring once; crd is the
	// unit of their coordinates and domain the unit of the rings. iteration is the number of
	// the step, which fold_c passes to every step; this step does not use it. The functions read
	// only their arguments, so they work for any coordinate unit.
	function DropReflexCorners(
		unit<fpoint> crd;
		unit<uint32> domain;
		parameter<uint32> iteration;
		unit<uint32> seq { attribute<crd> point; attribute<domain> sequence_rel; }
	)
	-> unit<uint32> := hull_points
	{
		attribute<uint32> first_id (domain) := min_index(id(seq), seq/sequence_rel);
		attribute<uint32> last_id  (domain) := max_index(id(seq), seq/sequence_rel);

		// the predecessor and the successor of each point within its ring, which is closed
		attribute<uint32> prev_id (seq) := id(seq) == first_id[seq/sequence_rel] ? last_id[seq/sequence_rel]  : sub_or_null(id(seq), 1);
		attribute<uint32> next_id (seq) := id(seq) == last_id[seq/sequence_rel]  ? first_id[seq/sequence_rel] : id(seq) + 1;

		attribute<crd>     p   (seq) := seq/point - seq/point[prev_id];
		attribute<crd>     q   (seq) := seq/point[next_id] - seq/point;
		attribute<float32> det (seq) := pointcol(p) * pointrow(q) - pointrow(p) * pointcol(q);

		// keep the right turns and the straight parts, and drop a point that repeats its predecessor
		unit<uint32> hull_points := select_with_org_rel(det <= 0f && seq/point != seq/point[prev_id])
		{
			attribute<crd>    point        := seq/point[hull_points/org_rel];
			attribute<domain> sequence_rel := seq/sequence_rel[hull_points/org_rel];
		}
	}

	// The rings of the points in pts, each closed by repeating its first point.
	function ClosedRings(
		unit<fpoint> crd;
		unit<uint32> domain;
		unit<uint32> pts { attribute<crd> point; attribute<domain> sequence_rel; }
	)
	-> attribute<crd> (domain, poly) := rings
	{
		unit<uint32> with_endpoints := union_unit(pts, domain)
		{
			attribute<crd>    point        := union_data(with_endpoints, pts/point, first(pts/point, pts/sequence_rel));
			attribute<domain> sequence_rel := union_data(with_endpoints, pts/sequence_rel, id(domain));
		}
		attribute<crd> rings (domain, poly) := points2polygon(with_endpoints/point, with_endpoints/sequence_rel);
	}

	// Whether DropReflexCorners drops a point of seq. The step does not use its number, so this
	// application is the same calculation as the next step of fold_c in ConvexHull.
	function DropsAPoint(
		unit<fpoint> crd;
		unit<uint32> domain;
		unit<uint32> seq { attribute<crd> point; attribute<domain> sequence_rel; }
	)
	-> parameter<bool> := #DropReflexCorners(crd, domain, 0u, seq) < #seq;

	// The convex hulls of the rings in seq: DropReflexCorners applied as long as it drops a
	// point, each time to the points the step before it kept, and the rings closed again. The
	// number of points in seq is a ceiling that a correct run cannot reach.
	function ConvexHull(
		unit<fpoint> crd;
		unit<uint32> domain;
		unit<uint32> seq { attribute<crd> point; attribute<domain> sequence_rel; }
	)
	-> attribute<crd> (domain, poly) := ClosedRings(crd, domain, fold_c(DropReflexCorners(crd, domain, _, _), DropsAPoint(crd, domain, _), #seq, seq));
}

container Simplified
{
	// the first step starts from the points of the rings themselves
	unit<uint32> StartingState := sequence2points(Shapes/geometry_rd);

	attribute<geometries/rdc> convex_hull (Shapes, poly) := lib/ConvexHull(geometries/rdc, Shapes, StartingState);
}

how it works

DropReflexCorners computes, for every point of a ring, the sign of the cross product det of the edge into the point and the edge out of it: negative where the ring turns right, zero where it goes straight on, positive where it turns left. In a clockwise ring, the GeoDMS order for an exterior ring, a left turn is a reflex corner, a dent in the shape, and the step drops those points, which fills the dent. Dropping a point can turn a neighbour into a reflex corner, so the step is repeated until it finds no reflex corner and keeps every point. The points that remain form the convex hull, including points that lie on a straight part of it. ClosedRings then closes every ring by repeating its first point.

DropReflexCorners, DropsAPoint, ClosedRings and ConvexHull are functions. ConvexHull repeats the step with Fold_c: starting from seq, it applies DropReflexCorners for as long as DropsAPoint is true, that is, as long as the step still drops a point, each time to the points that the application before it kept, and closes the rings of what the last application kept. Each step that is taken drops at least one point, so a correct run takes fewer steps than seq has points; #seq is therefore the ceiling, and reaching it would be an error. fold_c passes the number of the step to the step as its first open argument, which is why DropReflexCorners has the parameter iteration although it does not use it. Because it does not use it, DropReflexCorners(crd, domain, 0u, seq) in DropsAPoint is the same calculation as the next step, so testing the condition costs no extra step. The partial application DropReflexCorners(crd, domain, _, _) fixes the coordinate unit and the domain and leaves the number and the state open. Container Simplified, where the hull is needed, only names the points to start from.

The script handles one ring per polygon, without holes, in clockwise order; a counter-clockwise ring loses its convex corners instead. Dropping a corner cuts straight across, so a ring that winds back into the triangle it cuts off, such as a spiral, can end up crossing itself.

this script versus pareto_optimal

This script computes the exact convex hull of a point set. pareto_optimal solves a related but different problem: it keeps the elements of a partition that are not dominated by any other element on a set of minimised criteria. The two are easy to confuse because both can be computed with one sort and one sweep, but the sweep tests something different at each step: pareto_optimal compares a point against the best seen so far on every criterion, while this script’s det <= 0 test is an orientation test over three consecutive points of the hull built so far.

For two criteria the two results relate in one direction only. Every point on the side of the hull facing the origin, the side a model wants when both criteria are minimised, is also Pareto-optimal, but a Pareto-optimal point does not have to be on the hull: it can be undominated by any single other point and still lie inside the hull of the other Pareto-optimal points, on a concave dent of the front. Multi-objective optimisation theory calls this the difference between supported and unsupported Pareto-optimal points. So pareto_optimal cannot stand in for this script, nor the other way round, and a hull computed on an already Pareto-optimal point set still needs this script’s orientation test, not pareto_optimal’s dominance test.

GeoDMS#1331 proposes an actual operator for this hull, and a second mode restricted to the side facing the origin, for the two-criterion case where that distinction matters.