dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: To check if a point is inside a polygon

  1. #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. #2
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    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 1-6.
    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.

  3. #3
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    19,579

    Re: To check if a point is inside a polygon

    Victor Nijegorodov

  4. #4
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,727

    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

  5. #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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)