POINTS IN POLYGON

POINTS IN POLYGON

LET Subcommand

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.

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

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.

LET TAG = POINTS IN POLYGON XVAL YVAL XPOLY YPOLY

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.

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.

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.

None

None

CONVEX HULL	= Compute the convex hull of a set of points.
MINIMAL SPANNING TREE	= Determine the minimal spanning tree.
SPAINNING FOREST	= Determine the spanning forest.

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

Computational Geometry

2011/9

 
. 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