{"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":"

\u00a0<\/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=\u201dbanner\u201d]\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[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20C%2B%2B%20program%20to%20check%20if%20a%20given%20point%20lies%20inside%20a%20given%20polygon%0A%2F%2F%20Refer%20http%3A%2F%2Fwww.geeksforgeeks.org%2Fcheck-if-two-given-line-segments-intersect%2F%0A%2F%2F%20for%20explanation%20of%20functions%20onSegment()%2C%20orientation()%20and%20doIntersect()%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Define%20Infinite%20(Using%20INT_MAX%20caused%20overflow%20problems)%0A%23define%20INF%2010000%0A%20%0Astruct%20Point%0A%7B%0A%20%20%20%20int%20x%3B%0A%20%20%20%20int%20y%3B%0A%7D%3B%0A%20%0A%2F%2F%20Given%20three%20colinear%20points%20p%2C%20q%2C%20r%2C%20the%20function%20checks%20if%0A%2F%2F%20point%20q%20lies%20on%20line%20segment%20\u2019pr\u2019%0Abool%20onSegment(Point%20p%2C%20Point%20q%2C%20Point%20r)%0A%7B%0A%20%20%20%20if%20(q.x%20%3C%3D%20max(p.x%2C%20r.x)%20%26%26%20q.x%20%3E%3D%20min(p.x%2C%20r.x)%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20q.y%20%3C%3D%20max(p.y%2C%20r.y)%20%26%26%20q.y%20%3E%3D%20min(p.y%2C%20r.y))%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20To%20find%20orientation%20of%20ordered%20triplet%20(p%2C%20q%2C%20r).%0A%2F%2F%20The%20function%20returns%20following%20values%0A%2F%2F%200%20\u2013%3E%20p%2C%20q%20and%20r%20are%20colinear%0A%2F%2F%201%20\u2013%3E%20Clockwise%0A%2F%2F%202%20\u2013%3E%20Counterclockwise%0Aint%20orientation(Point%20p%2C%20Point%20q%2C%20Point%20r)%0A%7B%0A%20%20%20%20int%20val%20%3D%20(q.y%20-%20p.y)%20*%20(r.x%20-%20q.x)%20-%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20(q.x%20-%20p.x)%20*%20(r.y%20-%20q.y)%3B%0A%20%0A%20%20%20%20if%20(val%20%3D%3D%200)%20return%200%3B%20%20%2F%2F%20colinear%0A%20%20%20%20return%20(val%20%3E%200)%3F%201%3A%202%3B%20%2F%2F%20clock%20or%20counterclock%20wise%0A%7D%0A%20%0A%2F%2F%20The%20function%20that%20returns%20true%20if%20line%20segment%20\u2019p1q1\u2019%0A%2F%2F%20and%20\u2019p2q2\u2019%20intersect.%0Abool%20doIntersect(Point%20p1%2C%20Point%20q1%2C%20Point%20p2%2C%20Point%20q2)%0A%7B%0A%20%20%20%20%2F%2F%20Find%20the%20four%20orientations%20needed%20for%20general%20and%0A%20%20%20%20%2F%2F%20special%20cases%0A%20%20%20%20int%20o1%20%3D%20orientation(p1%2C%20q1%2C%20p2)%3B%0A%20%20%20%20int%20o2%20%3D%20orientation(p1%2C%20q1%2C%20q2)%3B%0A%20%20%20%20int%20o3%20%3D%20orientation(p2%2C%20q2%2C%20p1)%3B%0A%20%20%20%20int%20o4%20%3D%20orientation(p2%2C%20q2%2C%20q1)%3B%0A%20%0A%20%20%20%20%2F%2F%20General%20case%0A%20%20%20%20if%20(o1%20!%3D%20o2%20%26%26%20o3%20!%3D%20o4)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20Special%20Cases%0A%20%20%20%20%2F%2F%20p1%2C%20q1%20and%20p2%20are%20colinear%20and%20p2%20lies%20on%20segment%20p1q1%0A%20%20%20%20if%20(o1%20%3D%3D%200%20%26%26%20onSegment(p1%2C%20p2%2C%20q1))%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20p1%2C%20q1%20and%20p2%20are%20colinear%20and%20q2%20lies%20on%20segment%20p1q1%0A%20%20%20%20if%20(o2%20%3D%3D%200%20%26%26%20onSegment(p1%2C%20q2%2C%20q1))%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20p2%2C%20q2%20and%20p1%20are%20colinear%20and%20p1%20lies%20on%20segment%20p2q2%0A%20%20%20%20if%20(o3%20%3D%3D%200%20%26%26%20onSegment(p2%2C%20p1%2C%20q2))%20return%20true%3B%0A%20%0A%20%20%20%20%20%2F%2F%20p2%2C%20q2%20and%20q1%20are%20colinear%20and%20q1%20lies%20on%20segment%20p2q2%0A%20%20%20%20if%20(o4%20%3D%3D%200%20%26%26%20onSegment(p2%2C%20q1%2C%20q2))%20return%20true%3B%0A%20%0A%20%20%20%20return%20false%3B%20%2F%2F%20Doesn\u2019t%20fall%20in%20any%20of%20the%20above%20cases%0A%7D%0A%20%0A%2F%2F%20Returns%20true%20if%20the%20point%20p%20lies%20inside%20the%20polygon%5B%5D%20with%20n%20vertices%0Abool%20isInside(Point%20polygon%5B%5D%2C%20int%20n%2C%20Point%20p)%0A%7B%0A%20%20%20%20%2F%2F%20There%20must%20be%20at%20least%203%20vertices%20in%20polygon%5B%5D%0A%20%20%20%20if%20(n%20%3C%203)%20%20return%20false%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20point%20for%20line%20segment%20from%20p%20to%20infinite%0A%20%20%20%20Point%20extreme%20%3D%20%7BINF%2C%20p.y%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20Count%20intersections%20of%20the%20above%20line%20with%20sides%20of%20polygon%0A%20%20%20%20int%20count%20%3D%200%2C%20i%20%3D%200%3B%0A%20%20%20%20do%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20next%20%3D%20(i%2B1)%25n%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20the%20line%20segment%20from%20\u2019p\u2019%20to%20\u2019extreme\u2019%20intersects%0A%20%20%20%20%20%20%20%20%2F%2F%20with%20the%20line%20segment%20from%20\u2019polygon%5Bi%5D\u2019%20to%20\u2019polygon%5Bnext%5D\u2019%0A%20%20%20%20%20%20%20%20if%20(doIntersect(polygon%5Bi%5D%2C%20polygon%5Bnext%5D%2C%20p%2C%20extreme))%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20point%20\u2019p\u2019%20is%20colinear%20with%20line%20segment%20\u2019i-next\u2019%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20then%20check%20if%20it%20lies%20on%20segment.%20If%20it%20lies%2C%20return%20true%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20otherwise%20false%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(orientation(polygon%5Bi%5D%2C%20p%2C%20polygon%5Bnext%5D)%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20onSegment(polygon%5Bi%5D%2C%20p%2C%20polygon%5Bnext%5D)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20i%20%3D%20next%3B%0A%20%20%20%20%7D%20while%20(i%20!%3D%200)%3B%0A%20%0A%20%20%20%20%2F%2F%20Return%20true%20if%20count%20is%20odd%2C%20false%20otherwise%0A%20%20%20%20return%20count%261%3B%20%20%2F%2F%20Same%20as%20(count%252%20%3D%3D%201)%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20Point%20polygon1%5B%5D%20%3D%20%7B%7B0%2C%200%7D%2C%20%7B10%2C%200%7D%2C%20%7B10%2C%2010%7D%2C%20%7B0%2C%2010%7D%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(polygon1)%2Fsizeof(polygon1%5B0%5D)%3B%0A%20%20%20%20Point%20p%20%3D%20%7B20%2C%2020%7D%3B%0A%20%20%20%20isInside(polygon1%2C%20n%2C%20p)%3F%20cout%20%3C%3C%20%22Yes%20%5Cn%22%3A%20cout%20%3C%3C%20%22No%20%5Cn%22%3B%0A%20%0A%20%20%20%20p%20%3D%20%7B5%2C%205%7D%3B%0A%20%20%20%20isInside(polygon1%2C%20n%2C%20p)%3F%20cout%20%3C%3C%20%22Yes%20%5Cn%22%3A%20cout%20%3C%3C%20%22No%20%5Cn%22%3B%0A%20%0A%20%20%20%20Point%20polygon2%5B%5D%20%3D%20%7B%7B0%2C%200%7D%2C%20%7B5%2C%205%7D%2C%20%7B5%2C%200%7D%7D%3B%0A%20%20%20%20p%20%3D%20%7B3%2C%203%7D%3B%0A%20%20%20%20n%20%3D%20sizeof(polygon2)%2Fsizeof(polygon2%5B0%5D)%3B%0A%20%20%20%20isInside(polygon2%2C%20n%2C%20p)%3F%20cout%20%3C%3C%20%22Yes%20%5Cn%22%3A%20cout%20%3C%3C%20%22No%20%5Cn%22%3B%0A%20%0A%20%20%20%20p%20%3D%20%7B5%2C%201%7D%3B%0A%20%20%20%20isInside(polygon2%2C%20n%2C%20p)%3F%20cout%20%3C%3C%20%22Yes%20%5Cn%22%3A%20cout%20%3C%3C%20%22No%20%5Cn%22%3B%0A%20%0A%20%20%20%20p%20%3D%20%7B8%2C%201%7D%3B%0A%20%20%20%20isInside(polygon2%2C%20n%2C%20p)%3F%20cout%20%3C%3C%20%22Yes%20%5Cn%22%3A%20cout%20%3C%3C%20%22No%20%5Cn%22%3B%0A%20%0A%20%20%20%20Point%20polygon3%5B%5D%20%3D%20%20%7B%7B0%2C%200%7D%2C%20%7B10%2C%200%7D%2C%20%7B10%2C%2010%7D%2C%20%7B0%2C%2010%7D%7D%3B%0A%20%20%20%20p%20%3D%20%7B-1%2C10%7D%3B%0A%20%20%20%20n%20%3D%20sizeof(polygon3)%2Fsizeof(polygon3%5B0%5D)%3B%0A%20%20%20%20isInside(polygon3%2C%20n%2C%20p)%3F%20cout%20%3C%3C%20%22Yes%20%5Cn%22%3A%20cout%20%3C%3C%20%22No%20%5Cn%22%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
\u00a0<\/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}]}}