SED navigation bar go to SED home page go to Dataplot home page go to NIST home page SED Home Page SED Staff SED Projects SED Products and Publications Search SED Pages
Dataplot Vol 2 Vol 1

CONVEX HULL

Name:
    CONVEX HULL
Type:
    LET Subcommand
Purpose:
    Compute the 2-dimensional convex hull of a set of points.
Description:
    The 2-dimensional convex hull of a set of 2-dimensional points are the vertices that form the minimum area convex polygon that contains all of the points.
Syntax:
    LET <y2> <x2> = CONVEX HULL <y> <x>
                <SUBSET/EXPCEPT/FOR qualification>
    where <y> is a variable containing the y-coordinates of the full data set;
                <x> is a variable containing the x-coordinates of the full data set;
                <y2> is a variable that will contain the y-coordinats of the returned convex hull;
                <x2> is a variable that will contain the x-coordinats of the returned convex hull;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.
Examples:
    LET Y2 X2 = CONVEX HULL Y X
    LET Y2 X2 = CONVEX HULL Y X SUBSET X > 0 SUBSET Y > 0
Note:
    Dataplot uses Eddy's CONVEX routine given in ACM algorithm 523 to compute the convex hull. The algorithm is described in the references given below.
Default:
    None.
Synonyms:
    None
Related Commands: References:
    W. F. Eddy (1977), "A New Convex Hull Algorithm for Planar Sets", ACM Transactions on Mathematical Software (TOMS), Vol. 3, No. 4, pp. 398-403.

    W. F. Eddy (1977), "Algorithm 523: CONVEX, A New Convex Hull Algorithm for Planar Sets", ACM Transactions on Mathematical Software (TOMS), Vol. 3, No. 4, pp. 411-412.

    O'Rourke (1998), "Computational Geometry in C", Second Edition, Cambridge Unversity Press, Chapter 3.

Applications:
    Computational Geometry
Implementation Date:
    2008/4
Program:
     
    .  Following data from Eddy'w ACM article
    read x y
    2.0       0.0
    1.73      -1.0
    1.0       1.73
    0.0       2.0
    0.1       0.1
    -1.0      -1.73
    0.2       -0.2
    -1.73     1.0
    -0.3      0.3
    0.0       -2.0
    -0.4      -0.4
    -2.0      0.0
    0.5       0.5
    1.73      1.0
    0.6       -0.6
    -1.0      1.73
    -0.7      0.7
    -1.73     -1.0
    -0.8      -0.8
    1.0       -1.73
    end of data
    .
    let y2 x2 = 2d convex hull y x
    let n = size y
    let id = sequence 1 1 n
    .
    title case asis
    title offset 2
    title Convex Hull
    y1label Y
    x1label X
    tic offset units screen
    tic offset 3 3
    x3label
    .
    character automatic id
    line blank all
    .
    plot y x id
    line so
    line color blue
    char blank all
    pre-erase off
    limits freeze
    pre-sort off
    let n2 = size y2
    let n2 = n2 + 1
    let y2(n2) = y2(1)
    let x2(n2) = x2(1)
    plot y2 x2
        
    plot generated by sample program

Date created: 10/15/2008
Last updated: 10/15/2008
Please email comments on this WWW page to alan.heckert@nist.gov.