Find if a point is within a triangle: Difference between revisions
| Line 196: | Line 196: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
{{incorrect|REXX|there's a 2.3 which should really be 2.4 for consistency, I'm sure it will be fine... (but I havne installed REXX)}} |
|||
{{trans|Python}} |
{{trans|Python}} |
||
<lang rexx>/*REXX program determines if a specified point is within a specified triangle. */ |
<lang rexx>/*REXX program determines if a specified point is within a specified triangle. */ |
||
Revision as of 02:19, 13 November 2020
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 [ 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
<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.3 ' /* " " " " " " */ 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 " " */
say 'point ('space(p, 0)")" @ 'within the triangle ' space("("a'),('||b"),("c')', 0) exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ x: procedure; parse arg x ',' ; return strip(x) /*return the X coördinate sans blanks*/ y: procedure; parse arg ',' y; return strip(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 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)