Thread: If a given point in the plane lies inside, outside, or on the boundary of a polygon ?

If I were you I'd just use a well-known point-in-polygon algorithm (my personal favourite is the winding algorithm) for the first part. For the second problem, determining whether a point lies on a line segment, an idea that comes to mind is as follows.

As you may know, the cross product is a mathematical operation (only defined in three dimensions, but if you want 2D you can just use z=0) between two vectors that has several useful properties. The property that's useful here is that the length of the cross-product vector will be the same as the area in the parallelogram between the original two vectors. (Confusing? Look at a picture.)

So if the vectors are parallel, the area will be zero. Basically, if you take a vector from your point to one endpoint on the line, and another vector from your point to the other line endpoint, and their cross-product is zero, then all three points lie in a line. You can then just use a bounding box calculation to see if the point lies on the line segment.

BTW: here's an implementation of the winding algorithm I wrote a long time ago. It's undocumented and not very understandable at all, but I thought I'd link to it anyway. You need SDL and SDL_gfx to compile it, or you can just look at the screenshots. http://dwks.theprogrammingsite.com/m...tinpoly.tar.gz
(Warning: when you extract the archive, all files go into the current directory.)

Just wondering: why do you care if a point lies on the boundary of the polygon? If you use floating-point numbers then it might be very rare that a point lies in precisely the right place. If you're trying to display a polygon, for example, it's more effective to use something like Bresenham's algorithm.

If you want reasonably "wide" boundaries for collision detection, I'd find the distance of the point from the edge (one method: find the perpendicular line, find its intersection with the original line segment; use distance from intersection to point unless intersection lies outside line segment, in which case use shortest distance from the point to each endpoint) and then treat points within a small epsilon distance from the edge as being "on the edge".

Jenny,

What sort of constraints are there on the polygon in question? There are several variations, but from Calculus I recall that there are a multitude of assumptions that may be made about certain (convex I think) polygons. Here's an article from the Wikipedia: Polygon - Wikipedia, the free encyclopedia. I'm going to go root around in the library for a minute...brb.

Best Regards,

New Ink -- Henry

Jenny,

This link came off the page listed in the post a moment ago: Point in polygon - Wikipedia, the free encyclopedia. It looked like "Ray casting" was the most direct solution, but for points that lie very close to the boundary the solutions were a little shady due to computational precision.... How "neat" are these polygons? In operations research, we'd study constrain tableus (tables) that would describe polygon regions using equations for the lines and there extents as part of the polygon...but that was some advanced linear programming material leading to non-linear programming.

I apologize about the hurried nature of the post, I was about to walk away from the article to hit the books when I saw the reference in the previous article.... I'll get to looking now.

Best Regards,

New Ink -- Henry

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

Jenny,

I found a good one in the library that may also be helpful for your problem. It is an observation pointed out by Taha, Hamdy A. Operations Research: An Introduction 7th ed. New Jersey: Prentice Hall Copyright 2003. ISBN: 0-13-032374-8. On pages 289-90 he is discussing some attributes of the Simplex Method. Given the extreme points x1, x2, ... xn which are the corner points of a polygon, a point lying within, x, can be expressed as a convex combination of the extreme points using:

Code:

x = a1x1 + a2x2 + ... + anxn
where
a1 + a2 + ... + an = 1
and
ai >= 0, for i = 1, 2, ..., n

Using your test point, x, you have a matrix equation:

Code:

x = Xe * a

Using a procedure to invert Xe, for example Eigen values or Gausian elimination, one may find a solution for a:

Code:

Xe^-1 * x = a

And determine if the elements are positive and the norm (sum of the elements) is one to show that x lies within the boundaries specified in Xe, otherwise it is outside.

I like the predictable nature of the matrix approach, but I would enjoy hearing your ideas too.

Best Regards,

New Ink -- Henry