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

1. ## If a given point in the plane lies inside, outside, or on the boundary of a polygon ?

Hello friend.

I want to write a program whether a given point in the plane lies inside, outside, or on the boundary of a polygon. I have found this interesting website which shows 2 ways of doing that. i.e InsidePolygon() and pnpoly()
Determining if a point lies on the interior of a polygon

But these Algo/code don't detect if the input pt is on the boundary of a polygon?
Can you guys help me in that part of code/algo?

~ Jenny

2. @ Lesshardtofind, Thanks a ton for the clue

So looking at the original problem description. I can implement it in 2 parts.
1. Check if if three points are on the same line by checking if the determinant is 0
2. Follow that ALGO (as per my earlier update) which tells you if point is outside or inside of Polygon...

Sounds good to you?

3. Sounds good ;o). This a random project or part of some collision detection algorythym?

4. ohhh wait, I see a problem here.

Summarize....
So looking at the original problem description. I can implement it in below program flow :
Step1. Check if the input point is one of the vertices of polygon.
Step2. Check if if three points are on the same line by checking if the determinant is 0
Step3. Follow that ALGO (as per my earlier update) which tells you if point is outside or inside of Polygon...

I see a problem here in step2.
lets take an simple example...

Suppose I have an polygon, Square with vertices (10,10) (100,10) (100,100) and (10,100)
and I want to test a point (110,10) to see if this lies inside, outside, or on the boundary of a polygon.

In this case determinant is 0, but point is actually outside of polygon

Then I thought to check the return values of step 2 and 3.
If return from step 2 is TRUE (i.e determinant = 0) AND return from step 3 is TRUE (i.e INSIDE)
then by ANDing these two return value we can decide if pt is actually inside, outside, or on the boundary of a polygon.

But again problem here is....step3...it returns random values TRUE/FALSE (i.e INSIDE/OUTSIDE) if input point is on the boundary. So my logic of AND'ing return values fails

5. 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".

6. Thanks dwks !

What does the Winding number algorithm returns for a point which is on the boundary of a polygon ? Does that output in sameway as point-in-polygon algorithm ? i.e RANDOM ..sometimes INSIDE or OUTSIDE?

7. http://www.engr.colostate.edu/~dga/d...in_polygon.pdf
Note that the winding number is not defined when the point X is on the polygon

8. yea on that site I linked no one responded to the guy with his post about the matrix multplication. If you scroll down past that they discuss how to tell if a point lies on a infinite line, and from there how to tell if it lies within a segment of two points.

9. 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

10. 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

11. 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

Best Regards,

New Ink -- Henry

12. 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

13. Err...pardon me. The matrix X may not be invertible. One would have to use the a simplex method to determine the solution(s) for a that fall in the feasible region, if any they would imply that the point x lies within the region defined by X. The constraints were given, and then there are a collection of slack/surplus variables which would have to be handled. I apologize about the confusion...sometimes it escapes me that I'm not necessarily speaking to mathematicians.

Best Regards,

New Ink -- Henry

14. I use this one. It's super fast and simple.

Point Inclusion in Polygon Test
PNPOLY - Point Inclusion in Polygon Test - WR Franklin (WRF)