To check if a point is inside a polygon

[Muthuveerappan]

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

[monarch_dodra]

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.

[VictorN]

http://en.wikipedia.org/wiki/Point_in_polygon
and many other links:
http://www.google.com/search?num=20&...ygon+&gs_rfai=

[JohnW@Wessex]

Here's some code I've picked up from the web a while ago and modified a little that uses the 'Winding Algorithm'

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));
}

[Muthuveerappan]

Thanks a ton !!

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

Thanks again all of you !!