Jenny,

A quick way to determine the equation for the line containing the end points of an edge is given by Larson, Ron, Edwards, Bruce

H and Falvo, David C. __Elementary Linear Algebra__ 4th ed. Boston: Houghton Mifflin Copyright 2000. ISBN: 0-395-96717-1,

on page 148 as:

Code:

The equation of the line passing through the distinct points (x1, y1) and (x2, y2) is given by
[ x y 1 ]
det[ x1 y1 1 ] = 0.
[ x2 y2 1 ]
| y1 1 | | x1 1 | | x1 y1 |
<=> x| y2 1 | - y| x2 1 | + | x2 y2 | = 0
<=> x(y1 - y2) -y(x1 - x2) + (x1*y2 - x2*y1) = 0
<=> x(y1 - y2)/(x1 - x2) + (x1*y2 - x2*y1)/(x1 - x2) = y
<=> y = x(y1 - y2)/(x1 - x2) + (x1*y2 - x2*y1)/(x1 - x2)

Then, after the other tests determine the point to lie outside (not inside or on boundary) of the polygon, one could use this

familiar equation to determine if it "on" the edge of the polygon. The tedious part would be testing which edge to test against

the test point...that is:

Code:

for( i = 0; i < egdes; i++ )
if( ex[i][0] == ex[i][1] && x <= ex[i][0] + epsilon && x >= ex[i][0] - epsilon ) // vertical line, x coinciding with edge
{
if( y >= ey[i][0] && y <= ey[i][1] )
{
// x, y is on edge i
}
}
else if( x >= ex[i][0] && x <= ex[i][1] ) // non-vertical line
{
yprime = x*(ey[i][0] - ey[i][1])/(ex[i][0] - ex[i][1]) + (ex[i][0]*ey[i][1] - ex[i][1]*ey[i][0])/(ex[i][0] - ex[i][1])
if( y <= yprime + epsilon && y >= yprime - epsilon)
{
// x, y is on edge i
}
}
else
{
// otherwise x,y is not on edge_i
}

It may also be difficult to choose epsilon small enough to compensate for computational loss, but for many problems I do not

believe this will be an issue. Is that what you were looking for? I've heard the problem before, and it always intrigues me

when I hear/read it....

Best Regards,

New Ink -- Henry