
May 21st, 2010, 04:31 AM
#1
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 coordinates are given of each vertex is given.
Also the coordinates 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

May 21st, 2010, 04:41 AM
#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.
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 16.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

May 21st, 2010, 05:07 AM
#3
Re: To check if a point is inside a polygon
Victor Nijegorodov

May 21st, 2010, 05:15 AM
#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));
}
"It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
Richard P. Feynman

May 24th, 2010, 01:51 AM
#5
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

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
