Find if a point is within a triangle
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
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 [ <point> ] cartesian-map ! Make a matrix of points 3 3 <point> 17 9 <point> 10 15 <point> <triangle> ! Make a triangle '[ [ _ point-in-triangle? "#" "." ? write ] each nl ] each nl ! Show points inside the triangle with '#'</lang>
- Output:
.................... .................... .................... ...#................ ....#............... ....###............. .....####........... .....#####.......... ......######........ ......########...... ......##########.... .......########..... .......#######...... ........#####....... ........####........ .........##......... .........#.......... .........#.......... .................... ....................
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
<lang rexx>/*REXX program determines if a specified point is within a specified triangle. */ parse arg pnt p.1 p.2 p.3 . /*obtain optional arguments from the CL*/ if pnt== | p.1=="," then pnt= ' 0 , 0 ' /*Not specified? Then use the default.*/ if p.1== | p.1=="," then p.1= '1.5 , 2.3' /* " " " " " " */ if p.2== | p.2=="," then p.2= '5.1 , -3.1' /* " " " " " " */ if p.3== | p.3=="," then p.3= '-3.8, 0.5' /* " " " " " " */ if isIn(pnt, p.1, p.2, p.3) then is= 'is' /*Is the point outside the triangle ? */
else is= "isn't" /* " " " inside " " */
say 'point ('$(pnt)") " is ' within the triangle ' $("("p.1'),('p.2"),("p.3')') exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ $: return space( arg(1), 0) /*elide superfluous blanks. */ x: procedure; parse arg x ',' y; return strip(x) /*return the X coördinate.*/ y: procedure; parse arg x ',' y; return strip(y) /* " " Y " */ sig: parse arg aa,bb,cc; return (x(aa)-x(cc))*(y(bb)-y(cc))-(x(bb)-x(cc))*(y(aa)-y(cc)) /*──────────────────────────────────────────────────────────────────────────────────────*/ isIn: z1= sig(pnt, p.1, p.2); z2= sig(pnt, p.2, p.3); z3= sig(pnt, p.3, p.1)
return ( (z1>=0) & (z2>=0) & (z3>=0) ) | ( (z1<=0) & (z2<=0) & (z3<=0) )</lang>
- output when using the default inputs:
point (0,0) is within the triangle (1.5,2.3),(5.1,-3.1),(-3.8,0.5)
- output when using the default triangle and the point at: 666,666
point (666,666) isn't within the triangle (1.5,2.3),(5.1,-3.1),(-3.8,0.5)