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

POINTS IN POLYGON

Name:
    POINTS IN POLYGON
Type:
    LET Subcommand
Purpose:
    Given a polygon and a set of points, determine if each of these points are interior points, exterior points, edge points, or equal to a vertex.
Description:
    A basic problem in computational geometry is to determine if a point is inside or outside of a polygon. In a Dataplot context, the most common application for this basic problem is to determine whether a point should be plotted or not plotted.

    Given a set of one or more points, this command returns a tag value (where each row of the tag variable corresponds to the row of the variables containing the x and y coordinates of the points being tested). Each value of the tag variable will contain either a 1, 2, 3, or 4 where

      1 = interior point
      2 = exterior point
      3 = edge point
      4 = vertex point
Syntax:
    LET <tag> = POINTS IN POLYGON <xval> <yval> <xpoly> <ypoly>
                            <SUBSET/EXPCEPT/FOR qualification>
    where <xval> is a variable containing the x-coordinates of the data points being checked;
                <yval> is a variable containing the y-coordinates of the data points being checked;
                <xpoly> is a variable that will contain the x-coordinats of the polygon;
                <ypoly> is a variable that will contain the y-coordinats of the polygon;
                <tag> is a variable (of the same size as <xval> and <yval>) that specifies whether each point is an interior, exterior, edge, or vertex point;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.
Examples:
    LET TAG = POINTS IN POLYGON XVAL YVAL XPOLY YPOLY
Note:
    Dataplot uses a Fortran translation of the C routine "InPoly1" given on page 244 of O'Rourke (see Reference section below).

    This algorithm is based on counting the number of ray tracings. A complete description of the algorithm is given on pages 239-245 of O'Rourke's book.

    This algorithm works for both convex and non-convex polygons.

Note:
    The points in the polygon are assumed to be sorted (i.e., contiguous rows define an edge). No check is made that these points in fact define a valid polygon.

    The <xval> and <yval> points do not need to be in any specific order since they are tested independently of each other.

Note:
    In deterining if a point is equal to a vertex point, Dataplot checks that the x-coordinate and the y-coordinate are within epsilon of each vertex where epsilon is set equal to 0.0000001.
Default:
    None
Synonyms:
    None
Related Commands: Reference:
    O'Rourke (1998), "Computational Geometry in C", Second Edition, Cambridge Unversity Press, Chapter 7.
Applications:
    Computational Geometry
Implementation Date:
    2011/9
Program:
     
    . Name:     poly.dp
    . Purpose:  Demonstrate "points in polygon" routine
    . Source:   Data from O'Rourke (1998), "Computational Geometry in
    .           C", Second Edition.
    .
    . Step 1: Read data
    .
    read xpoly ypoly
    0 0
    2 0
    2 2
    3 1
    4 2
    5 2
    3 3
    3 2
    2 4
    6 3
    7 4
    7 2
    8 5
    8 7
    7 7
    8 8
    5 9
    6 6
    5 7
    4 6
    4 8
    3 7
    2 7
    3 6
    4 4
    0 7
    2 3
    0 2
    end of data
    .
    read xval yval
    0 0
    1 0
    2 1
    1 2
    0 2
    6 2
    2 4
    5 4
    1 5
    3 5
    6 5
    7 6
    8 6
    1 7
    2 7
    3 7
    4 7
    4 8
    5 9
    end of data
    .
    . Step 2: Plot data
    .
    tic mark offset units screen
    tic mark offset 5 5
    pre-sort off
    line blank solid
    character circ blank
    character hw 0.5 0.375
    character fill on
    plot yval xval and
    plot ypoly xpoly
    pause
    .
    let tag = point in polygon xval yval xpoly ypoly
    .
    line bl bl bl bl solid
    character circ circ circ circ blank
    character hw 0.5 0.375 all
    character fill on all
    char color blue red green cyan black
    plot yval xval subset tag = 1 and
    plot yval xval subset tag = 2 and
    plot yval xval subset tag = 3 and
    plot yval xval subset tag = 4 and
    plot ypoly xpoly
        
    plot generated by sample program

    plot generated by sample program

Date created: 09/14/2011
Last updated: 09/14/2011
Please email comments on this WWW page to alan.heckert@nist.gov.