Given a polygon and a point ‘p’, find if ‘p’ lies inside the polygon or not. The points lying on the border are considered inside.
Following is a simple idea to check whether a point is inside or outside.
If point is same as one of the vertices of polygon, then it intersects with two lines. We explicitly handle it by comparing the point with n vertices of the polygon.
Following is C++ implementation of the above idea.
Output:
Source:
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
Following is a simple idea to check whether a point is inside or outside.
1)Draw a horizontal line to the right of each point and extend it to infinity. 2) Count the number of times a line intersects the polygon. We have: even number ---> point is outside odd number ----> point is inside
If point is same as one of the vertices of polygon, then it intersects with two lines. We explicitly handle it by comparing the point with n vertices of the polygon.
Following is C++ implementation of the above idea.
// A C++ program to check if a given point lies inside a given polygon #include <iostream> #include <limits.h> using namespace std; struct Point { int x; int y; }; // Given three colinear points p, q, r, the function checks if // point q lies on line segment 'pr' bool onSegment(Point p, Point q, Point r) { if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y)) return true ; return false ; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are colinear // 1 --> Clockwise // 2 --> Counterclockwise int orientation(Point p, Point q, Point r) { int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0) return 0; // colinear return (val > 0)? 1: 2; // clock or counterclock wise } // The function that returns true if line segment 'p1q1' // and 'p2q2' intersect. bool doIntersect(Point p1, Point q1, Point p2, Point q2) { // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true ; // Special Cases // p1, q1 and p2 are colinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true ; // p1, q1 and p2 are colinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true ; // p2, q2 and p1 are colinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true ; // p2, q2 and q1 are colinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true ; return false ; // Doesn't fall in any of the above cases } // Returns true if the point p lies inside the polygon[] with n vertices bool isInside(Point polygon[], int n, Point p) { // There must be at least 3 vertices in polygon[] if (n < 3) return false ; // Create a point for line segment from p to infinite Point extreme = {INT_MAX, p.y}; // Count intersections of the above line with sides of polygon int count = 0; for ( int i = 0; i < n-1; i++) { // If p is same as one of the vertices if (p.x == polygon[i].x && p.y == polygon[i].y) return true ; // Otherwise check for intersection if (doIntersect(polygon[i], polygon[i+1], p, extreme)) count++; } // If p is same as last vertex if (p.x == polygon[n-1].x && p.y == polygon[n-1].y) return true ; // Last side (from last to first point) is missed in the // above loop, consider it now if (doIntersect(polygon[n-1], polygon[0], p, extreme)) count++; // Return true if count is odd, false otherwise return count&1; // Same as (count%2 == 1) } // Driver program to test above functions int main() { Point polygon[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}}; int n = sizeof (polygon)/ sizeof (polygon[0]); Point p = {20, 20}; isInside(polygon, n, p)? cout << "Yes \n" : cout << "No \n" ; p = {5, 5}; isInside(polygon, n, p)? cout << "Yes \n" : cout << "No \n" ; return 0; } |
No YesTime Complexity: O(n) where n is the number of vertices in the given polygon.
Source:
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
Hi,
ReplyDeleteThanks for the code. But hands down!!! This code shows me the wrong output.
Hi Himangi,
ReplyDeleteIs this taking into account the co-ordinate system? The following did not work for me.
Point polygon[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};
Point p = {-1, 0};
I was expecting Point (-1,0) to be reported as lying outside but the program did not.