Find if a point is within a triangle

From Rosetta Code
Revision as of 04:20, 3 December 2020 by rosettacode>Gerard Schildberger (→‎{{header|REXX}}: added wording to the REXX section header,)
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
Also see
  • Discussion of several methods. [[1]]
  • Determine if a point is in a polygon [[2]]
  • Triangle based coordinate systems [[3]]
  • Wolfram entry [[4]]

C

Translation of: Go

<lang c>#include <stdbool.h>

  1. include <stdio.h>
  2. include <stdlib.h>

const double EPS = 0.001; const double EPS_SQUARE = 0.000001;

double side(double x1, double y1, double x2, double y2, double x, double y) { 

   return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1);

}

bool naivePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) { 

   double checkSide1 = side(x1, y1, x2, y2, x, y) >= 0;
   double checkSide2 = side(x2, y2, x3, y3, x, y) >= 0;
   double checkSide3 = side(x3, y3, x1, y1, x, y) >= 0;
   return checkSide1 && checkSide2 && checkSide3;

}

bool pointInTriangleBoundingBox(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) { 

   double xMin = min(x1, min(x2, x3)) - EPS;
   double xMax = max(x1, max(x2, x3)) + EPS;
   double yMin = min(y1, min(y2, y3)) - EPS;
   double yMax = max(y1, max(y2, y3)) + EPS;
   return !(x < xMin || xMax < x || y < yMin || yMax < y);

}

double distanceSquarePointToSegment(double x1, double y1, double x2, double y2, double x, double y) { 

   double p1_p2_squareLength = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
   double dotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength;
   if (dotProduct < 0) {
       return (x - x1) * (x - x1) + (y - y1) * (y - y1);
   } else if (dotProduct <= 1) {
       double p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
       return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength;
   } else {
       return (x - x2) * (x - x2) + (y - y2) * (y - y2);
   }

}

bool accuratePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) { 

   if (!pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)) {
       return false;
   }
   if (naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) {
       return true;
   }
   if (distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE) {
       return true;
   }
   if (distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE) {
       return true;
   }
   if (distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE) {
       return true;
   }
   return false;

}

void printPoint(double x, double y) { 

   printf("(%f, %f)", x, y);

}

void printTriangle(double x1, double y1, double x2, double y2, double x3, double y3) { 

   printf("Triangle is [");
   printPoint(x1, y1);
   printf(", ");
   printPoint(x2, y2);
   printf(", ");
   printPoint(x3, y3);
   printf("] \n");

}

void test(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) { 

   printTriangle(x1, y1, x2, y2, x3, y3);
   printf("Point ");
   printPoint(x, y);
   printf(" is within triangle? ");
   if (accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) {
       printf("true\n");
   } else {
       printf("false\n");
   }

}

int main() { 

   test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 0);
   test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 1);
   test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3, 1);
   printf("\n");

   test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25, 11.11111111111111, 5.414285714285714, 14.349206349206348);
   printf("\n");

   test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348);
   printf("\n");

   return 0;

}</lang>

Output:
Triangle is [(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)]
Point (0.000000, 0.000000) is within triangle? true
Triangle is [(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)]
Point (0.000000, 1.000000) is within triangle? true
Triangle is [(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)]
Point (3.000000, 1.000000) is within triangle? false

Triangle is [(0.100000, 0.111111), (12.500000, 33.333333), (25.000000, 11.111111)]
Point (5.414286, 14.349206) is within triangle? true

Triangle is [(0.100000, 0.111111), (12.500000, 33.333333), (-12.500000, 16.666667)]
Point (5.414286, 14.349206) is within triangle? true

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:
....................
....................
....................
...#................
....#...............
.....##.............
.....####...........
......#####.........
......#######.......
.......########.....
.......##########...
........########....
........#######.....
.........#####......
.........####.......
..........##........
..........#.........
....................
....................
....................

Go

Translation of: Wren

<lang go>package main

import ( 

   "fmt"
   "math"

)

const EPS = 0.001 const EPS_SQUARE = EPS * EPS

func side(x1, y1, x2, y2, x, y float64) float64 { 

   return (y2-y1)*(x-x1) + (-x2+x1)*(y-y1)

}

func naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y float64) bool { 

   checkSide1 := side(x1, y1, x2, y2, x, y) >= 0
   checkSide2 := side(x2, y2, x3, y3, x, y) >= 0
   checkSide3 := side(x3, y3, x1, y1, x, y) >= 0
   return checkSide1 && checkSide2 && checkSide3

}

func pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y float64) bool { 

   xMin := math.Min(x1, math.Min(x2, x3)) - EPS
   xMax := math.Max(x1, math.Max(x2, x3)) + EPS
   yMin := math.Min(y1, math.Min(y2, y3)) - EPS
   yMax := math.Max(y1, math.Max(y2, y3)) + EPS
   return !(x < xMin || xMax < x || y < yMin || yMax < y)

}

func distanceSquarePointToSegment(x1, y1, x2, y2, x, y float64) float64 { 

   p1_p2_squareLength := (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)
   dotProduct := ((x-x1)*(x2-x1) + (y-y1)*(y2-y1)) / p1_p2_squareLength
   if dotProduct < 0 {
       return (x-x1)*(x-x1) + (y-y1)*(y-y1)
   } else if dotProduct <= 1 {
       p_p1_squareLength := (x1-x)*(x1-x) + (y1-y)*(y1-y)
       return p_p1_squareLength - dotProduct*dotProduct*p1_p2_squareLength
   } else {
       return (x-x2)*(x-x2) + (y-y2)*(y-y2)
   }

}

func accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y float64) bool { 

   if !pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y) {
       return false
   }
   if naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) {
       return true
   }
   if distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE {
       return true
   }
   if distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE {
       return true
   }
   if distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE {
       return true
   }
   return false

}

func main() { 

   pts := [][2]float64{{0, 0}, {0, 1}, {3, 1}}
   tri := [][2]float64{{3.0 / 2, 12.0 / 5}, {51.0 / 10, -31.0 / 10}, {-19.0 / 5, 1.2}}
   fmt.Println("Triangle is", tri)
   x1, y1 := tri[0][0], tri[0][1]
   x2, y2 := tri[1][0], tri[1][1]
   x3, y3 := tri[2][0], tri[2][1]
   for _, pt := range pts {
       x, y := pt[0], pt[1]
       within := accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
       fmt.Println("Point", pt, "is within triangle?", within)
   }
   fmt.Println()
   tri = [][2]float64{{1.0 / 10, 1.0 / 9}, {100.0 / 8, 100.0 / 3}, {100.0 / 4, 100.0 / 9}}
   fmt.Println("Triangle is", tri)
   x1, y1 = tri[0][0], tri[0][1]
   x2, y2 = tri[1][0], tri[1][1]
   x3, y3 = tri[2][0], tri[2][1]
   x := x1 + (3.0/7)*(x2-x1)
   y := y1 + (3.0/7)*(y2-y1)
   pt := [2]float64{x, y}
   within := accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
   fmt.Println("Point", pt, "is within triangle ?", within)
   fmt.Println()
   tri = [][2]float64{{1.0 / 10, 1.0 / 9}, {100.0 / 8, 100.0 / 3}, {-100.0 / 8, 100.0 / 6}}
   fmt.Println("Triangle is", tri)
   x3 = tri[2][0]
   y3 = tri[2][1]
   within = accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
   fmt.Println("Point", pt, "is within triangle ?", within)

}</lang>

Output:
Triangle is [[1.5 2.4] [5.1 -3.1] [-3.8 1.2]]
Point [0 0] is within triangle? true
Point [0 1] is within triangle? true
Point [3 1] is within triangle? false

Triangle is [[0.1 0.1111111111111111] [12.5 33.333333333333336] [25 11.11111111111111]]
Point [5.414285714285714 14.349206349206348] is within triangle ? true

Triangle is [[0.1 0.1111111111111111] [12.5 33.333333333333336] [-12.5 16.666666666666668]]
Point [5.414285714285714 14.349206349206348] is within triangle ? true

Julia

Translation of: Python

Using the Wren examples. <lang julia>Point(x, y) = [x, y] Triangle(a, b, c) = [a, b, c] LEzero(x) = x < 0 || isapprox(x, 0, atol=0.00000001) GEzero(x) = x > 0 || isapprox(x, 0, atol=0.00000001)

""" Determine which side of plane cut by line (p2, p3) p1 is on """ side(p1, p2, p3) = (p1[1] - p3[1]) * (p2[2] - p3[2]) - (p2[1] - p3[1]) * (p1[2] - p3[2])

""" 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. Each z is positive if outside, negative if inside such a plane. All should be positive or all negative if point is within the triangle. """ function iswithin(point, p1, p2, p3) 

   z1 = side(point, p1, p2)
   z2 = side(point, p2, p3)
   z3 = side(point, p3, p1)
   notanyneg = GEzero(z1) && GEzero(z2) && GEzero(z3)
   notanypos = LEzero(z1) && LEzero(z2) && LEzero(z3)
   return notanyneg || notanypos

end

const POINTS = [Point(0 // 1, 0 // 1), Point(0 // 1, 1 // 1), Point(3 // 1, 1 // 1), 

   Point(1 // 10 + (3 // 7) * (100 // 8 - 1 // 10), 1 // 9 + (3 // 7) * (100 // 3 - 1 // 9)),
   Point(3 // 2, 12 // 5), Point(51 // 100, -31 // 100), Point(-19 // 50, 6 // 5),
   Point(1 // 10, 1 // 9), Point(25 / 2, 100 // 3), Point(25, 100 // 9),
   Point(-25 // 2, 50 // 3)

]

const TRI = [ 

   Triangle(POINTS[5], POINTS[6], POINTS[7]),
   Triangle(POINTS[8], POINTS[9], POINTS[10]),
   Triangle(POINTS[8], POINTS[9], POINTS[11])

]

for tri in TRI 

   pstring(pt) = "[$(Float32(pt[1])), $(Float32(pt[2]))]"
   println("\nUsing triangle [", join([pstring(x) for x in tri], ", "), "]:")
   a, b, c = tri[1], tri[2], tri[3]
   for p in POINTS[1:4]
       isornot = iswithin(p, a, b, c) ? "is" : "is not"
       println("Point $(pstring(p)) $isornot within the triangle.")
   end

end

</lang>

Output:
Using triangle [[1.5, 2.4], [0.51, -0.31], [-0.38, 1.2]]:
Point [0.0, 0.0] is not within the triangle.
Point [0.0, 1.0] is within the triangle.
Point [3.0, 1.0] is not within the triangle.
Point [5.4142857, 14.349206] is not within the triangle.

Using triangle [[0.1, 0.11111111], [12.5, 33.333332], [25.0, 11.111111]]:
Point [0.0, 0.0] is not within the triangle.
Point [0.0, 1.0] is not within the triangle.
Point [3.0, 1.0] is not within the triangle.
Point [5.4142857, 14.349206] is within the triangle.

Using triangle [[0.1, 0.11111111], [12.5, 33.333332], [-12.5, 16.666666]]:
Point [0.0, 0.0] is not within the triangle.
Point [0.0, 1.0] is within the triangle.
Point [3.0, 1.0] is not within the triangle.
Point [5.4142857, 14.349206] is within the triangle.

Perl

Translte the Java program at this blog post and data set is taken from the Raku entry. <lang Perl># 20201123 added Perl programming solution

use strict; use warnings;

use List::AllUtils qw(min max natatime); use constant EPSILON => 0.001; use constant EPSILON_SQUARE => EPSILON*EPSILON;

sub side { 

  my ($x1, $y1, $x2, $y2, $x, $y) = @_;
  return ($y2 - $y1)*($x - $x1) + (-$x2 + $x1)*($y - $y1);

}

sub naivePointInTriangle { 

  my ($x1, $y1, $x2, $y2, $x3, $y3, $x, $y) = @_;
  my $checkSide1 = side($x1, $y1, $x2, $y2, $x, $y) >= 0 ;
  my $checkSide2 = side($x2, $y2, $x3, $y3, $x, $y) >= 0 ;
  my $checkSide3 = side($x3, $y3, $x1, $y1, $x, $y) >= 0 ;
  return $checkSide1 && $checkSide2 && $checkSide3  || 0 ;

}

sub pointInTriangleBoundingBox { 

  my ($x1, $y1, $x2, $y2, $x3, $y3, $x, $y) = @_;
  my $xMin = min($x1, min($x2, $x3)) - EPSILON;
  my $xMax = max($x1, max($x2, $x3)) + EPSILON;
  my $yMin = min($y1, min($y2, $y3)) - EPSILON;
  my $yMax = max($y1, max($y2, $y3)) + EPSILON;
  ( $x < $xMin || $xMax < $x || $y < $yMin || $yMax < $y ) ? 0 : 1

}

sub distanceSquarePointToSegment { 

  my ($x1, $y1, $x2, $y2, $x, $y) = @_;
  my $p1_p2_squareLength = ($x2 - $x1)**2 + ($y2 - $y1)**2;
  my $dotProduct = ($x-$x1)*($x2-$x1)+($y-$y1)*($y2-$y1) ;
  if ( $dotProduct < 0 ) {
     return ($x - $x1)**2 + ($y - $y1)**2;
  } elsif ( $dotProduct <= $p1_p2_squareLength ) {
     my $p_p1_squareLength = ($x1 - $x)**2 + ($y1 - $y)**2;
     return $p_p1_squareLength - $dotProduct**2 / $p1_p2_squareLength;
  } else {
     return ($x - $x2)**2 + ($y - $y2)**2;
  }

}

sub accuratePointInTriangle { 

  my ($x1, $y1, $x2, $y2, $x3, $y3, $x, $y) = @_;
  return 0 unless pointInTriangleBoundingBox($x1,$y1,$x2,$y2,$x3,$y3,$x,$y);
  return 1 if ( naivePointInTriangle($x1, $y1, $x2, $y2, $x3, $y3, $x, $y)
     or distanceSquarePointToSegment($x1, $y1, $x2, $y2, $x, $y) <= EPSILON_SQUARE
     or distanceSquarePointToSegment($x2, $y2, $x3, $y3, $x, $y) <= EPSILON_SQUARE
     or distanceSquarePointToSegment($x3, $y3, $x1, $y1, $x, $y) <= EPSILON_SQUARE);
  return 0

}

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

for my $point ( [0,0] , [0,1] ,[3,1] ) { 

  print "Point (", join(',',@$point), ") is within triangle ";
  my $iter = natatime 2, @DATA;
  while ( my @vertex = $iter->()) { print '(',join(',',@vertex),') ' }
  print ': ',naivePointInTriangle (@DATA, @$point) ? 'True' : 'False', "\n" ;

}</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

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}}

function inside(sequence p) return sort(convex_hull({p}&triangle))==sort(triangle) end function printf(1,"Point %v is with triangle %v?:%t\n",{p0,triangle,inside(p0)}) printf(1,"Point %v is with triangle %v?:%t\n",{p1,triangle,inside(p1)}) printf(1,"Point %v is with triangle %v?:%t\n",{p2,triangle,inside(p2)})</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


Extra certification code was added to verify that the   X,Y   coördinates for the points are not missing and are numeric. <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 inside the triangle ? */ 

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

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)

Wren

Library: Wren-math

This is a translation of the ActionScript code for the 'accurate' method in the first referenced article above. <lang ecmascript>import "/math" for Math

var EPS = 0.001 var EPS_SQUARE = EPS * EPS

var side = Fn.new { |x1, y1, x2, y2, x, y| 

   return (y2 - y1)*(x - x1) + (-x2 + x1)*(y - y1)

}

var naivePointInTriangle = Fn.new { |x1, y1, x2, y2, x3, y3, x, y| 

   var checkSide1 = side.call(x1, y1, x2, y2, x, y) >= 0
   var checkSide2 = side.call(x2, y2, x3, y3, x, y) >= 0
   var checkSide3 = side.call(x3, y3, x1, y1, x, y) >= 0
   return checkSide1 && checkSide2 && checkSide3

}

var pointInTriangleBoundingBox = Fn.new { |x1, y1, x2, y2, x3, y3, x, y| 

   var xMin = Math.min(x1, Math.min(x2, x3)) - EPS
   var xMax = Math.max(x1, Math.max(x2, x3)) + EPS
   var yMin = Math.min(y1, Math.min(y2, y3)) - EPS
   var yMax = Math.max(y1, Math.max(y2, y3)) + EPS
   return !(x < xMin || xMax < x || y < yMin || yMax < y)

}

var distanceSquarePointToSegment = Fn.new { |x1, y1, x2, y2, x, y| 

   var p1_p2_squareLength = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1)
   var dotProduct = ((x - x1)*(x2 - x1) + (y - y1)*(y2 - y1)) / p1_p2_squareLength
   if (dotProduct < 0) {
       return (x - x1)*(x - x1) + (y - y1)*(y - y1)
   } else if (dotProduct <= 1) {
       var p_p1_squareLength = (x1 - x)*(x1 - x) + (y1 - y)*(y1 - y)
       return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength
   } else {
       return (x - x2)*(x - x2) + (y - y2)*(y - y2)
   }

}

var accuratePointInTriangle = Fn.new { |x1, y1, x2, y2, x3, y3, x, y| 

   if (!pointInTriangleBoundingBox.call(x1, y1, x2, y2, x3, y3, x, y)) return false
   if (naivePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y)) return true
   if (distanceSquarePointToSegment.call(x1, y1, x2, y2, x, y) <= EPS_SQUARE) return true
   if (distanceSquarePointToSegment.call(x2, y2, x3, y3, x, y) <= EPS_SQUARE) return true
   if (distanceSquarePointToSegment.call(x3, y3, x1, y1, x, y) <= EPS_SQUARE) return true
   return false

}

var pts = [ [0, 0], [0, 1], [3, 1]] var tri = [ [3/2, 12/5], [51/10, -31/10], [-19/5, 1.2] ] System.print("Triangle is %(tri)") var x1 = tri[0][0] var y1 = tri[0][1] var x2 = tri[1][0] var y2 = tri[1][1] var x3 = tri[2][0] var y3 = tri[2][1]

for (pt in pts) { 

   var x = pt[0]
   var y = pt[1]
   var within = accuratePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y)
   System.print("Point %(pt) is within triangle ? %(within)")

} System.print() tri = [ [1/10, 1/9], [100/8, 100/3], [100/4, 100/9] ] System.print("Triangle is %(tri)") x1 = tri[0][0] y1 = tri[0][1] x2 = tri[1][0] y2 = tri[1][1] x3 = tri[2][0] y3 = tri[2][1] var x = x1 + (3/7)*(x2 - x1) var y = y1 + (3/7)*(y2 - y1) var pt = [x, y] var within = accuratePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y) System.print("Point %(pt) is within triangle ? %(within)") System.print() tri = [ [1/10, 1/9], [100/8, 100/3], [-100/8, 100/6] ] System.print("Triangle is %(tri)") x3 = tri[2][0] y3 = tri[2][1] within = accuratePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y) System.print("Point %(pt) is within triangle ? %(within)")</lang>

Output:
Triangle is [[1.5, 2.4], [5.1, -3.1], [-3.8, 1.2]]
Point [0, 0] is within triangle ? true
Point [0, 1] is within triangle ? true
Point [3, 1] is within triangle ? false

Triangle is [[0.1, 0.11111111111111], [12.5, 33.333333333333], [25, 11.111111111111]]
Point [5.4142857142857, 14.349206349206] is within triangle ? true

Triangle is [[0.1, 0.11111111111111], [12.5, 33.333333333333], [-12.5, 16.666666666667]]
Point [5.4142857142857, 14.349206349206] is within triangle ? true

XPL0

<lang XPL0>func real Dot(W,X,Y,Z); \Return the dot product of two 2D vectors real W,X,Y,Z; \ (W-X) dot (Y-Z) real WX(2), YZ(2); [WX(0):= W(0)-X(0); WX(1):= W(1)-X(1); 

YZ(0):= Y(0)-Z(0);  YZ(1):= Y(1)-Z(1);

return WX(0)*YZ(0) + WX(1)*YZ(1); ];

real A,B,C; \triangle

func PointInTri(P); \Return 'true' if point P is inside triangle ABC real P; int S0,S1,S2; \signs [S0:= Dot(P,A,B,A) >= 0.0; 

S1:= Dot(P,B,C,B) >= 0.0;
S2:= Dot(P,C,A,C) >= 0.0;

return S0=S1 & S1=S2 & S2=S0; ];

[A:= [10.5, 6.3]; B:= [13.5, 3.6]; C:= [ 3.3, -1.6]; Text(0, if PointInTri([10.0, 3.0]) then "inside" else "outside"); CrLf(0); Text(0, if PointInTri([-5.0,-2.2]) then "inside" else "outside"); CrLf(0); Text(0, if PointInTri([10.5, 6.3]) then "inside" else "outside"); CrLf(0); ]</lang>

Output:
inside
outside
inside
Retrieved from "https://rosettacode.org/wiki/Find_if_a_point_is_within_a_triangle?oldid=303846"