Find if a point is within a triangle: Difference between revisions
m (→{{header|REXX}}: simplified the code.) |
m (→{{header|REXX}}: elided the use of variable tails for an easier read.) |
||
Line 149: | Line 149: | ||
=={{header|REXX}}== |
=={{header|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. */ |
||
parse arg |
parse arg p a b c . /*obtain optional arguments from the CL*/ |
||
if |
if p=='' | p=="," then p= ' 0 , 0 ' /*Not specified? Then use the default.*/ |
||
if |
if a=='' | a=="," then a= ' 1.5 , 2.3 ' /* " " " " " " */ |
||
if |
if b=='' | b=="," then b= ' 5.1 , -3.1 ' /* " " " " " " */ |
||
if |
if c=='' | c=="," then c= ' -3.8 , 0.5 ' /* " " " " " " */ |
||
if isIn( |
if isIn(p, a, b, c) then @ = ' is ' /*Is the point outside the triangle ? */ |
||
else @ = " isn't " /* " " " inside " " */ |
|||
say 'point ('space( |
say 'point ('space(p, 0)")" @ 'within the triangle ' space("("a'),('||b"),("c')', 0) |
||
exit 0 /*stick a fork in it, we're all done. */ |
exit 0 /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
Line 164: | Line 164: | ||
sig: parse arg aa,bb,cc; return (x(aa)-x(cc))*(y(bb)-y(cc))-(x(bb)-x(cc))*(y(aa)-y(cc)) |
sig: parse arg aa,bb,cc; return (x(aa)-x(cc))*(y(bb)-y(cc))-(x(bb)-x(cc))*(y(aa)-y(cc)) |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
isIn: #1= sig( |
isIn: #1= sig(p, a, b); #2= sig(p, b, c); #3= sig(p, c, a) |
||
return ( (#1>=0) & (#2>=0) & (#3>=0) ) | ( (#1<=0) & (#2<=0) & (#3<=0) )</lang> |
return ( (#1>=0) & (#2>=0) & (#3>=0) ) | ( (#1<=0) & (#2<=0) & (#3<=0) )</lang> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
Revision as of 01:40, 12 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 [ <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 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 isIn(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.*/ y: procedure; parse arg ',' 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: #1= sig(p, a, b); #2= sig(p, b, c); #3= sig(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)