Associated Topics || Dr. Math Home || Search Dr. Math

### Determining If a Given Point Lies inside a Polygon

```Date: 12/27/2005 at 05:55:30
From: Kapil
Subject: Point in polygon or not

I have a finite number of points that constitute a polygon, and a
point p(x,y).  I want to know if point p lies inside the polygon.

```

```
Date: 12/27/2005 at 10:29:16
From: Doctor Floor
Subject: Re: Point in polygon or not

Hi, Kapil,

Thanks for your question.  You will need to have formulas for the
sides, something like:

y = 2x + 4

from starting point (1,6) to endpoint (3,10).

This is because points alone are not enough to define a polygon.  See
for instance this polygon:

+-------+
|       |
|       |
|       |
|   +   |
|  / \  |
| /   \ |
|/     \|
+       +

which has the same vertices as, but is a different polygon from:

+-------+
\      |
\     |
\    |
+   |
/    |
/     |
/      |
+-------+

Provided that you have the formulae for the sides, make the formula
for a line p(x,y) that does not pass through one of the vertices
(points) of the polygon.  Intersect this line with all sides.  Count
the number of intersections (only if they are between the starting
point and endpoint of the sides!) on the left hand side and right hand
side of p.  If they are

both even: p is outside of the polygon
both odd: p is inside of the polygon

Do you see why this is true?

Examples:

BOTH SIDES ODD

\         /
+\-------/-----------------+
/ \     /                 /
/   \   /                 /
/     \ /                 /
------------p----------------------
/       / \               /
/       /   \             /
+-------/-----\-----------+
/       \

BOTH SIDES EVEN

_.-'
+_.-'---------------------+
_.-'                        /
\ _.-' /                         /
--p------------------------------------------
\  /                         /
\/                         /
/\                        /
+--\----------------------+
\

If you have more questions, just write back.

Best regards,

- Doctor Floor, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Triangles and Other Polygons
High School Triangles and Other Polygons

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search