CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: To check if a point is inside a polygon

1. Join Date
Feb 2009
Posts
326

## To check if a point is inside a polygon

Hi,

I am looking for a Library / function / formula to check if a point is inside a polygon.

Assuming the polygon has N sides, and the co-ordinates are given of each vertex is given.
Also the co-ordinates of the point is also given.

How do we check if the point is inside the polygon. Is there a C++ library / function / formula to check this.

Note - Not sure if boost or other libraries support something like that.

Thanks,
Muthu

2. ## Re: To check if a point is inside a polygon

While I don't know of any libraries, I do have a friend who worked on something similar.

However it required the polygon to be concave...

In this case, you can just use vectorial product to make sure your point is on "the right side" of every vertex, if you iterate on them in a clock ward (or indirect) fashion.

This is a pretty direct and simple approach. Probably not the most efficient, but gets the work done.

4. ## Re: To check if a point is inside a polygon

Here's some code I've picked up from the web a while ago and modified a little that uses the 'Winding Algorithm'
Code:
```bool Is_Inside(const Point              &point,
const std::vector<Point> &points_list)
{
// The winding number counter.
int winding_number = 0;

// Loop through all edges of the polygon.
typedef std::vector<Point>::size_type size_type;

size_type size = points_list.size();

for (size_type i = 0; i < size; ++i)             // Edge from point1 to points_list[i+1]
{
Point point1(points_list[i]);
Point point2;

// Wrap?
if (i == (size - 1))
{
point2 = points_list[0];
}
else
{
point2 = points_list[i + 1];
}

if (point1.y <= point.y)                                    // start y <= point.y
{
if (point2.y > point.y)                                 // An upward crossing
{
if (Is_Left(point1, point2, point) > 0)             // Point left of edge
{
++winding_number;                               // Have a valid up intersect
}
}
}
else
{
// start y > point.y (no test needed)
if (point2.y <= point.y)                                // A downward crossing
{
if (Is_Left(point1, point2, point) < 0)             // Point right of edge
{
--winding_number;                               // Have a valid down intersect
}
}
}
}

return (winding_number != 0);
}

int Is_Left(const Point &p0,
const Point &p1,
const Point &point)
{
return ((p1.x - p0.x) * (point.y - p0.y) -
(point.x - p0.x) * (p1.y - p0.y));
}```

5. Join Date
Feb 2009
Posts
326

## Re: To check if a point is inside a polygon

Thanks a ton !!

Will go through them and come back with the doubts that I have.

Thanks again all of you !!

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•