{"id":25942,"date":"2017-10-25T21:55:11","date_gmt":"2017-10-25T16:25:11","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25942"},"modified":"2017-10-25T21:55:11","modified_gmt":"2017-10-25T16:25:11","slug":"check-whether-given-point-lies-inside-triangle-not","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/check-whether-given-point-lies-inside-triangle-not\/","title":{"rendered":"Check whether a given point lies inside a triangle or not"},"content":{"rendered":"<p>Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not.<span id=\"more-22146\"><\/span><\/p>\n<p>For example, consider the following program, the function should return true for P(10, 15) and false for P'(30, 15)<\/p>\n<pre>         B(10,30)\r\n                \/ \\\r\n               \/   \\\r\n              \/     \\\r\n             \/   P   \\      P'\r\n            \/         \\\r\n     A(0,0) ----------- C(20,0)<\/pre>\n<p><strong>Solution:<\/strong><br \/>\nLet the coordinates of three corners be (x1, y1), (x2, y2) and (x3, y3). And coordinates of the given point P be (x, y)<\/p>\n<p>1) Calculate area of the given triangle, i.e., area of the triangle ABC in the above diagram. Area A = [ x1(y2 \u2013 y3) + x2(y3 \u2013 y1) + x3(y1-y2)]\/2<br \/>\n2) Calculate area of the triangle PAB. We can use the same formula for this. Let this area be A1.<br \/>\n3) Calculate area of the triangle PBC. Let this area be A2.<br \/>\n4) Calculate area of the triangle PAC. Let this area be A3.<br \/>\n5) If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F*%20A%20utility%20function%20to%20calculate%20area%20of%20triangle%20formed%20by%20(x1%2C%20y1)%2C%20%0A%20%20%20(x2%2C%20y2)%20and%20(x3%2C%20y3)%20*%2F%0Afloat%20area(int%20\u00d71%2C%20int%20y1%2C%20int%20\u00d72%2C%20int%20y2%2C%20int%20\u00d73%2C%20int%20y3)%0A%7B%0A%20%20%20return%20abs((x1*(y2-y3)%20%2B%20\u00d72*(y3-y1)%2B%20\u00d73*(y1-y2))%2F2.0)%3B%0A%7D%0A%20%0A%2F*%20A%20function%20to%20check%20whether%20point%20P(x%2C%20y)%20lies%20inside%20the%20triangle%20formed%20%0A%20%20%20by%20A(x1%2C%20y1)%2C%20B(x2%2C%20y2)%20and%20C(x3%2C%20y3)%20*%2F%0Abool%20isInside(int%20\u00d71%2C%20int%20y1%2C%20int%20\u00d72%2C%20int%20y2%2C%20int%20\u00d73%2C%20int%20y3%2C%20int%20x%2C%20int%20y)%0A%7B%20%20%20%0A%20%20%20%2F*%20Calculate%20area%20of%20triangle%20ABC%20*%2F%0A%20%20%20float%20A%20%3D%20area%20(x1%2C%20y1%2C%20\u00d72%2C%20y2%2C%20\u00d73%2C%20y3)%3B%0A%20%0A%20%20%20%2F*%20Calculate%20area%20of%20triangle%20PBC%20*%2F%20%20%0A%20%20%20float%20A1%20%3D%20area%20(x%2C%20y%2C%20\u00d72%2C%20y2%2C%20\u00d73%2C%20y3)%3B%0A%20%0A%20%20%20%2F*%20Calculate%20area%20of%20triangle%20PAC%20*%2F%20%20%0A%20%20%20float%20A2%20%3D%20area%20(x1%2C%20y1%2C%20x%2C%20y%2C%20\u00d73%2C%20y3)%3B%0A%20%0A%20%20%20%2F*%20Calculate%20area%20of%20triangle%20PAB%20*%2F%20%20%20%0A%20%20%20float%20A3%20%3D%20area%20(x1%2C%20y1%2C%20\u00d72%2C%20y2%2C%20x%2C%20y)%3B%0A%20%20%20%0A%20%20%20%2F*%20Check%20if%20sum%20of%20A1%2C%20A2%20and%20A3%20is%20same%20as%20A%20*%2F%0A%20%20%20return%20(A%20%3D%3D%20A1%20%2B%20A2%20%2B%20A3)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%2F*%20Let%20us%20check%20whether%20the%20point%20P(10%2C%2015)%20lies%20inside%20the%20triangle%20%0A%20%20%20%20%20%20formed%20by%20A(0%2C%200)%2C%20B(20%2C%200)%20and%20C(10%2C%2030)%20*%2F%0A%20%20%20if%20(isInside(0%2C%200%2C%2020%2C%200%2C%2010%2C%2030%2C%2010%2C%2015))%0A%20%20%20%20%20printf%20(%22Inside%22)%3B%0A%20%20%20else%0A%20%20%20%20%20printf%20(%22Not%20Inside%22)%3B%0A%20%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>\u00a0<\/p>\n<p>Ouptut:<\/p>\n<pre> Inside<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Check whether a given point lies inside a triangle or not &#8211; Geometric Algorithm &#8211; Given three corner points of a triangle, and one more point P.<\/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],"tags":[75868,76271,75875,76272,76274,76270,76269,76273],"class_list":["post-25942","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-geometric-algorithms","tag-check-if-a-point-is-inside-a-rectangle","tag-check-if-a-point-is-inside-a-rectangle-c","tag-check-if-point-is-inside-rectangle-java","tag-check-if-three-points-form-triangle","tag-check-if-three-points-form-triangle-java","tag-how-to-check-if-a-point-is-inside-a-triangle-java","tag-how-to-check-if-a-point-lies-inside-a-polygon","tag-point-inside-triangle-3d"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25942","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=25942"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25942\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25942"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25942"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25942"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}