Find if a point is within a triangle

Find if a point is within a triangle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Find if a point is within a triangle.

Task

•   Assume points are on a plane defined by (x, y) real number coordinates.

•   Given a point P(x, y) and a triangle formed by points A, B, and C, determine if P is within triangle ABC.

•   You may use any algorithm.

•   Bonus: explain why the algorithm you chose works.

Related tasks

•   Determine_if_two_triangles_overlap

Also see

• Discussion of several methods. [[1]]
• Determine if a point is in a polygon [[2]]
• Triangle based coordinate systems [[3]]
• Wolfram entry [[4]]

Factor

Uses the parametric equations method from [5]. <lang factor>USING: accessors fry io kernel locals math math.order sequences ;

TUPLE: point x y ; C: <point> point

>point< ( point -- x y ) [ x>> ] [ y>> ] bi ;

TUPLE: triangle p1 p2 p3 ; C: <triangle> triangle

>triangle< ( triangle -- x1 y1 x2 y2 x3 y3 )

   [ p1>> ] [ p2>> ] [ p3>> ] tri [ >point< ] tri@ ;

point-in-triangle? ( point triangle -- ? )

   point >point< triangle >triangle< :> ( x y x1 y1 x2 y2 x3 y3 )
   y2 y3 - x1 * x3 x2 - y1 * + x2 y3 * + y2 x3 * - :> d
   y3 y1 - x * x1 x3 - y * + x1 y3 * - y1 x3 * + d / :> t1
   y2 y1 - x * x1 x2 - y * + x1 y2 * - y1 x2 * + d neg / :> t2
   t1 t2 + :> s
   
   t1 t2 [ 0 1 between? ] bi@ and s 1 <= and ;

! Test if it works.

20 <iota> dup [ swap <point> ] cartesian-map  ! Make a matrix of points 3 3 <point> 16 10 <point> 10 16 <point> <triangle>  ! Make a triangle '[ [ _ point-in-triangle? "#" "." ? write ] each nl ] each nl  ! Show points inside the triangle with '#' </lang>

Output:

....................
....................
....................
...#................
....#...............
.....##.............
.....####...........
......#####.........
......#######.......
.......########.....
.......##########...
........########....
........#######.....
.........#####......
.........####.......
..........##........
..........#.........
....................
....................
....................

Phix

using convex_hull

Using convex_hull() from Convex_hull#Phix <lang Phix>constant p0 = {0,0},

        p1 = {0,1},    
        p2 = {3,1},    
        triangle = {{3/2, 12/5}, {51/10, -31/10}, {-19/5, 1/2}}

printf(1,"Point %v is with triangle %v?:%t\n",{p0,triangle,length(convex_hull({p0}&triangle))=3}) printf(1,"Point %v is with triangle %v?:%t\n",{p1,triangle,length(convex_hull({p1}&triangle))=3}) printf(1,"Point %v is with triangle %v?:%t\n",{p2,triangle,length(convex_hull({p2}&triangle))=3})</lang>

Output:

Point {0,0} is with triangle {{1.5,2.4},{5.1,-3.1},{-3.8,0.5}}?:true
Point {0,1} is with triangle {{1.5,2.4},{5.1,-3.1},{-3.8,0.5}}?:true
Point {3,1} is with triangle {{1.5,2.4},{5.1,-3.1},{-3.8,0.5}}?:false

trans python

(using the same p0/p1/p2/triangle constants from above, same output) <lang Phix>function side(sequence p1, p2, p3)

   -- which side of plane cut by line (p2, p3) is p1 on?
   atom {x1, y1} = p1,
        {x2, y2} = p2,
        {x3, y3} = p3
   return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3)

end function

function iswithin(sequence point, triangle) -- -- Determine if point is within triangle. -- If so, the point will be on the same side of each of the half planes -- defined by vectors p1p2, p2p3, and p3p1. zval is positive if outside, -- negative if inside such a plane. All should be positive or all negative -- if point is within the triangle. --

   sequence {pt1, pt2, pt3} = triangle
   atom zval1 = side(point, pt1, pt2),
        zval2 = side(point, pt2, pt3),
        zval3 = side(point, pt3, pt1)
   bool notanyneg = zval1 >= 0 and zval2 >= 0 and zval3 >= 0,
        notanypos = zval1 <= 0 and zval2 <= 0 and zval3 <= 0
   return notanyneg or notanypos

end function

printf(1,"point %v is with triangle %v?:%t\n",{p0,triangle,iswithin(p0,triangle)}) printf(1,"point %v is with triangle %v?:%t\n",{p1,triangle,iswithin(p1,triangle)}) printf(1,"point %v is with triangle %v?:%t\n",{p2,triangle,iswithin(p2,triangle)})</lang>

Python

<lang python> """ find if point is in a triangle """

from sympy.geometry import Point, Triangle

def sign(pt1, pt2, pt3):

   """ which side of plane cut by line (pt2, pt3) is pt1 on? """
   return (pt1.x - pt3.x) * (pt2.y - pt3.y) - (pt2.x - pt3.x) * (pt1.y - pt3.y)

def iswithin(point, pt1, pt2, pt3):

   """ 
   Determine if point is within triangle formed by points p1, p2, p3.
   If so, the point will be on the same side of each of the half planes
   defined by vectors p1p2, p2p3, and p3p1. zval is positive if outside,
   negative if inside such a plane. All should be positive or all negative
   if point is within the triangle.
   """
   zval1 = sign(point, pt1, pt2)
   zval2 = sign(point, pt2, pt3)
   zval3 = sign(point, pt3, pt1)
   notanyneg = zval1 >= 0 and zval2 >= 0 and zval3 >= 0
   notanypos = zval1 <= 0 and zval2 <= 0 and zval3 <= 0
   return notanyneg or notanypos

if __name__ == "__main__":

   POINTS = [Point(0, 0)]
   TRI = Triangle(Point(1.5, 2.4), Point(5.1, -3.1), Point(-3.8, 0.5))
   for pnt in POINTS:
       a, b, c = TRI.vertices
       isornot = "is" if iswithin(pnt, a, b, c) else "is not"
       print("Point", pnt, isornot, "within the triangle", TRI)

</lang>

Output:

Point Point2D(0, 0) is within the triangle Triangle(Point2D(3/2, 12/5), Point2D(51/10, -31/10), Point2D(-19/5, 1/2))

Raku

Reusing code from the Convex hull task and some logic from the Determine if two triangles overlap task.

<lang perl6>class Point {

   has Real $.x is rw;
   has Real $.y is rw;
   method gist { [~] '(', self.x,', ', self.y, ')' };

}

sub sign (Point $a, Point $b, Point $c) {

   ($b.x - $a.x)*($c.y - $a.y) - ($b.y - $a.y)*($c.x - $a.x);

}

sub triangle (*@points where *.elems == 6) {

   @points.batch(2).map: { Point.new(:x(.[0]),:y(.[1])) };

}

sub is-within ($point, @triangle is copy) {

  my @signs = sign($point, |(@triangle.=rotate)[0,1]) xx 3;
  so (all(@signs) >= 0) or so(all(@signs) <= 0);

}

my @triangle = triangle((1.5, 2.4), (5.1, -3.1), (-3.8, 0.5));

for Point.new(:x(0),:y(0)),

   Point.new(:x(0),:y(1)),
   Point.new(:x(3),:y(1))
 -> $point {
   say "Point {$point.gist} is within triangle {join ', ', @triangle».gist}: ",
       $point.&is-within: @triangle

}</lang>

Output:

Point (0, 0) is within triangle (1.5, 2.4), (5.1, -3.1), (-3.8, 0.5): True
Point (0, 1) is within triangle (1.5, 2.4), (5.1, -3.1), (-3.8, 0.5): True
Point (3, 1) is within triangle (1.5, 2.4), (5.1, -3.1), (-3.8, 0.5): False

REXX

Translation of: Python

<lang rexx>/*REXX program determines if a specified point is within a specified triangle. */ parse arg p a b c . /*obtain optional arguments from the CL*/ if p== | p=="," then p= '(0,0)' /*Not specified? Then use the default.*/ if a== | a=="," then a= '(1.5,2.4)' /* " " " " " " */ if b== | b=="," then b= '(5.1,-3.1)' /* " " " " " " */ if c== | c=="," then c= '(-3.8,0.5)' /* " " " " " " */ if ?(p, a, b, c) then @ = ' is ' /*Is the point outside the triangle ? */

                 else @ = " isn't "             /* "  "    "    inside  "      "       */

comma= ',' say 'point' p @ " within the triangle " a comma b comma c exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ cert: parse arg z,W; if datatype(z,'N') then return z; call serr z /*return coördinate.*/ serr: say W 'data point ' z " isn't numeric or missing."; exit 13 /*tell error message*/ x: procedure; parse arg "(" x ','  ; return cert(x,"X") /*return the X coördinate.*/ y: procedure; parse arg ',' y ")"; return cert(y,"Y") /* " " Y " */ $: parse arg aa,bb,cc; return (x(aa)-x(cc)) *(y(bb)-y(cc)) - (x(bb)-x(cc)) *(y(aa)-y(cc)) ?: #1=$(p,a,b); #2=$(p,b,c); #3=$(p,c,a); return (#1>=0&#2>=0&#3>=0) | (#1<=0&#2<=0&#3<=0)</lang>

output   when using the default triangle and the point at:   0,1

output   when using the default inputs:

point (0,0)   is   within the triangle  (1.5,2.4) , (5.1,-3.1) , (-3.8,0.5)

output   when using the default triangle and the point at:   0,1

point (0,1)   is   within the triangle  (1.5,2.4) , (5.1,-3.1) , (-3.8,0.5)

output   when using the default triangle and the point at:   3,1

point (3,1)   isn't   within the triangle  (1.5,2.4) , (5.1,-3.1) , (-3.8,0.5)