File ConvexHull.h

↰ Parent directory (ADS/geometry)

The convex hull of a set of points of the plane (section 16.1), the smallest convex polygon that contains them, as its vertices in counter clockwise order.

Definition (ADS/geometry/ConvexHull.h)

Detailed Description

The side of a point q with respect to the line through p_1 and p_2 is the sign of the cross product :math:` ( x_2 - x_1 ) ( y_q - y_1 ) - ( y_2 - y_1 ) ( x_q - x_1 ) `, and sameSide() of the book is the product of two such signs not being negative; with integer coordinates it is exact.

  • convexHullBrute(): a segment S_ij is an edge of the hull if all the other points are on one side of its line, O( n^3 );

  • graham(): the lowest point (the rightmost of the lowest ones) is a vertex; the others by increasing angle around it, of the collinear ones only the farthest kept, and each one pushed on a stack after popping the vertices that it makes not convex, a backtrack; each point is pushed and popped at most once, O( n ) after the sort, O( n log n ) in all. The angle is compared by the cross product, or by pseudoAngle(), a quantity of the same order as the angle that needs no arctangent (exercise 16.1).

  • convexHull(), beyond the book, the engineered hull: the extreme points in the eight directions of the axes and of the diagonals (the minimum and the maximum of x, y, x + y and x - y) are vertices of the hull, in counter clockwise order, and a point strictly inside their octagon (on the left of each of its edges, 8 cross products at most) is no vertex: one pass drops it (the heuristic of Akl and Toussaint). The k points left, each made a key of 64 bits :math:` ( x + 2^{31} ) 2^{32} + ( y + 2^{31} ) , whose order is the one by x and then y, are sorted by the radix sort of :ref:`namespace_ADS [see File Sort.h] in O( k ) (at most 8 passes of bytes), and the lower and the upper chain of the monotone chain of Andrew pop the points that make a turn not to the left, each point pushed and popped at most once, O( k ): in all :math:` O( n + k ) , :math: k le n `; for points uniform in a square or in a disk the octagon leaves a vanishing fraction of them, and the expected time is O( n ) (Devroye and Toussaint). The vertices come in the order and from the point of graham().

The contracts [see File Contract.h]: the pseudo-angle is in [ 0 , 4 ), and the hulls are convex, counter clockwise, made of input points and contain all of them (checked at level 3). The operations are defined in ConvexHull.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 16.1, https://algoritmicamente.it/materiali/libro/capitoli/cap16.pdf

    1. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Information Processing Letters 1(4), 132-133, 1972, doi:10.1016/0020-0190(72)90045-2

    1. Akl, G. T. Toussaint, A fast convex hull algorithm, Information Processing Letters 7(5), 219-222, 1978, doi:10.1016/0020-0190(78)90003-0

    1. Andrew, Another efficient algorithm for convex hulls in two dimensions, Information Processing Letters 9(5), 216-219, 1979, doi:10.1016/0020-0190(79)90072-3

  1. Devroye, G. T. Toussaint, A note on linear expected time algorithms for finding convex hulls, Computing 26(4), 361-366, 1981, doi:10.1007/BF02237955

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions