{"id":25878,"date":"2017-10-25T21:10:32","date_gmt":"2017-10-25T15:40:32","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25878"},"modified":"2017-10-25T21:10:32","modified_gmt":"2017-10-25T15:40:32","slug":"check-given-point-lies-inside-outside-polygon","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/check-given-point-lies-inside-outside-polygon\/","title":{"rendered":"How to check if a given point lies inside or outside a polygon?"},"content":{"rendered":"

 <\/p>\n

Given a polygon and a point \u2018p\u2019, find if \u2018p\u2019 lies inside the polygon or not. The points lying on the border are considered inside.<\/p>\n

\"How<\/p>\n

Following is a simple idea to check whether a point is inside or outside.<\/p>\n

1)<\/strong> Draw a horizontal line to the right of each point and extend it to infinity\r\n\r\n1)<\/strong> Count the number of times the line intersects with polygon edges.\r\n\r\n2)<\/strong> A point is inside the polygon if either count of intersections is odd or\r\n   point lies on an edge of polygon.  If none of the conditions is true, then \r\n   point lies outside.\r\n\r\n<\/pre>\n
\"How<\/p>\n[ad type=”banner”]\n
How to handle point \u2018g\u2019 in the above figure?<\/strong>
\nNote that we should returns true if the point lies on the line or same as one of the vertices of the given polygon.\u00a0To handle this, after checking if the line from \u2018p\u2019 to extreme intersects, we check whether \u2018p\u2019 is colinear with vertices of current line of polygon. If it is coliear, then we check if the point \u2018p\u2019 lies on current side of polygon, if it lies, we return true, else false.<\/p>\n
Following is C++ implementation of the above idea.<\/p>\n
 
 <\/div> 
\/\/ A C++ program to check if a given point lies inside a given polygon\/\/ Refer http:\/\/www.geeksforgeeks.org\/check-if-two-given-line-segments-intersect\/\/\/ for explanation of functions onSegment(), orientation() and doIntersect()#include <iostream>using namespace std; \/\/ Define Infinite (Using INT_MAX caused overflow problems)#define INF 10000 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 --> Counterclockwiseint 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 verticesbool 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 = {INF, p.y};     \/\/ Count intersections of the above line with sides of polygon    int count = 0, i = 0;    do    {        int next = (i+1)%n;         \/\/ Check if the line segment from 'p' to 'extreme' intersects        \/\/ with the line segment from 'polygon[i]' to 'polygon[next]'        if (doIntersect(polygon[i], polygon[next], p, extreme))        {            \/\/ If the point 'p' is colinear with line segment 'i-next',            \/\/ then check if it lies on segment. If it lies, return true,            \/\/ otherwise false            if (orientation(polygon[i], p, polygon[next]) == 0)               return onSegment(polygon[i], p, polygon[next]);             count++;        }        i = next;    } while (i != 0);     \/\/ Return true if count is odd, false otherwise    return count&1;  \/\/ Same as (count%2 == 1)} \/\/ Driver program to test above functionsint main(){    Point polygon1[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};    int n = sizeof(polygon1)\/sizeof(polygon1[0]);    Point p = {20, 20};    isInside(polygon1, n, p)? cout << "Yes \\n": cout << "No \\n";     p = {5, 5};    isInside(polygon1, n, p)? cout << "Yes \\n": cout << "No \\n";     Point polygon2[] = {{0, 0}, {5, 5}, {5, 0}};    p = {3, 3};    n = sizeof(polygon2)\/sizeof(polygon2[0]);    isInside(polygon2, n, p)? cout << "Yes \\n": cout << "No \\n";     p = {5, 1};    isInside(polygon2, n, p)? cout << "Yes \\n": cout << "No \\n";     p = {8, 1};    isInside(polygon2, n, p)? cout << "Yes \\n": cout << "No \\n";     Point polygon3[] =  {{0, 0}, {10, 0}, {10, 10}, {0, 10}};    p = {-1,10};    n = sizeof(polygon3)\/sizeof(polygon3[0]);    isInside(polygon3, n, p)? cout << "Yes \\n": cout << "No \\n";     return 0;}<\/code><\/pre> <\/div>\n
 <\/p>\n
Output:<\/p>\n
No\r\nYes\r\nYes\r\nYes\r\nNo\r\nNo<\/pre>\n","protected":false},"excerpt":{"rendered":"
How to check if a given point lies inside or outside a polygon – Geometric Algorithm –  To handle this, after checking if the line from \u2018p\u2019 to extreme.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,73905,83569],"tags":[75868,75872,75874,75875,75869,75873,75870,75871],"class_list":["post-25878","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-geometric-algorithms","category-polygon","tag-check-if-a-point-is-inside-a-rectangle","tag-check-if-a-point-is-inside-a-square","tag-check-if-point-is-inside-polygon-javascript","tag-check-if-point-is-inside-rectangle-java","tag-how-to-find-whether-a-point-lies-inside-a-triangle","tag-point-in-polygon-winding-number","tag-point-inside-convex-polygon","tag-point-inside-polygon-python"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25878","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25878"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25878\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25878"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25878"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25878"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}