SVG/Convex Hull/english

This article is a study with the purpose of preparing an extension proposal to the W3C Scalable Vector Graphics standard.

An initial implementation could be done as an Inkscape Live Path Effect.

definition and premisses

The functionality described here is the ability to compute the Convex Hull of a given set of vector geometries.

This operation only applies to closed geometries. It seems reasonable to me that, when applying the Convex Hull operator to open curves, we can extended them with a line segment connecting the initial and end points in order to get equivalent closed geometries to work with.

TODO: add here an image depicting the suggested equivalence between closed and open curves for the purpose of computing convex hulls.

The Convex Hull of a set of closed curves, is defined as the convex curve with the smallest possible area that contains all of the curves in the original set.

The next picture represents (a) an arbitrary set of closed curves (red stroke) and (b) the result of computing the convex hull of that set (grey fill and green stroke).

existing implementations

OpenSCAD

OpenSCAD is an algorithmic and parametric CAD modelling tool. It implements the convex hull operation via the hull(){ ... } module.

Example

Here's an example of such feature. The script below describes a geometry composed of a circle with radius=50 positioned at the origin of the coordinate system and a larger circle, with radius=80, at the coordinate x=160 and y=0.

circle(r=50);
translate([160,0]) circle(r=80);

The image depicts the rendering of this initial geometry.

The next script computes the convex hull of that same original geometry, by using the hull() module.

hull(){
  circle(r=50);
  translate([160,0]) circle(r=80);
}

You can see in the next image the result of the convex hull operator.