{"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<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-cpp code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-cpp code-embed-code\">#include &lt;stdio.h&gt;<br\/>#include &lt;stdlib.h&gt;<br\/> <br\/>\/* A utility function to calculate area of triangle formed by (x1, y1), <br\/>   (x2, y2) and (x3, y3) *\/<br\/>float area(int x1, int y1, int x2, int y2, int x3, int y3)<br\/>{<br\/>   return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))\/2.0);<br\/>}<br\/> <br\/>\/* A function to check whether point P(x, y) lies inside the triangle formed <br\/>   by A(x1, y1), B(x2, y2) and C(x3, y3) *\/<br\/>bool isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)<br\/>{   <br\/>   \/* Calculate area of triangle ABC *\/<br\/>   float A = area (x1, y1, x2, y2, x3, y3);<br\/> <br\/>   \/* Calculate area of triangle PBC *\/  <br\/>   float A1 = area (x, y, x2, y2, x3, y3);<br\/> <br\/>   \/* Calculate area of triangle PAC *\/  <br\/>   float A2 = area (x1, y1, x, y, x3, y3);<br\/> <br\/>   \/* Calculate area of triangle PAB *\/   <br\/>   float A3 = area (x1, y1, x2, y2, x, y);<br\/>   <br\/>   \/* Check if sum of A1, A2 and A3 is same as A *\/<br\/>   return (A == A1 + A2 + A3);<br\/>}<br\/> <br\/>\/* Driver program to test above function *\/<br\/>int main()<br\/>{<br\/>   \/* Let us check whether the point P(10, 15) lies inside the triangle <br\/>      formed by A(0, 0), B(20, 0) and C(10, 30) *\/<br\/>   if (isInside(0, 0, 20, 0, 10, 30, 10, 15))<br\/>     printf (&quot;Inside&quot;);<br\/>   else<br\/>     printf (&quot;Not Inside&quot;);<br\/> <br\/>   return 0;<br\/>}<\/code><\/pre> <\/div>\n<p>&nbsp;<\/p>\n<p>Ouptut:<\/p>\n<pre> Inside<\/pre>\n[ad type=&#8221;banner&#8221;]\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}]}}