Find if a point is within a triangle: Difference between revisions
Find if a point is within a triangle (view source)
Revision as of 08:32, 29 September 2021
, 2 years ago→{{header|jq}}
(→{{header|ALGOL 68}}: notes) |
|||
Line 838:
Triangle[(0.100000, 0.111111), (12.500000, 33.333333), (-12.500000, 16.666667)]
Point (5.414286, 14.349206) is within triangle? true</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
'''Adapted from [[#Wren|Wren]'''
A point is represented by [x,y] and denoted by P1, P2, P3, or Q.
A triangle is represented by an array of points: [P1, P2, P3].
'''Preliminaries'''
<lang jq>def sum_of_squares(stream): reduce stream as $x (0; . + $x * $x);
def distanceSquared(P1; P2): sum_of_squares(P1[0]-P2[0], P1[1]-P2[1]);
# Emit {x1,y1, ...} for the input triangle
def xy:
{ x1: .[0][0],
y1: .[0][1],
x2: .[1][0],
y2: .[1][1],
x3: .[2][0],
y3: .[2][1] };
def EPS: 0.001;
def EPS_SQUARE: EPS * EPS; </lang>
<lang jq>def side(P1; P2; Q):
[P1, P2, Q]
| xy
| (.y2 - .y1)*(.x3 - .x1) + (-.x2 + .x1)*(.y3 - .y1);
def naivePointInTriangle(P1; P2; P3; Q):
side(P1; P2; Q) >= 0
and side(P2; P3; Q) >= 0
and side(P3; P1; Q) >= 0;
def pointInTriangleBoundingBox(P1; P2; P3; Q):
[P1,P2,P3]
| (map(.[0]) | min - EPS) as $xMin
| (map(.[0]) | max + EPS) as $xMax
| (map(.[1]) | min - EPS) as $yMin
| (map(.[1]) | max + EPS) as $yMax
| (Q[0] < $xMin or $xMax < Q[0] or Q[1] < $yMin or $yMax < Q[1]) | not;
def distanceSquarePointToSegment(P1; P2; Q):
distanceSquared(P1; P2) as $p1_p2_squareLength
| [P1, P2, Q]
| xy
| (((.x3 - .x1)*(.x2 - .x1) + (.y3 - .y1)*(.y2 - .y1)) / $p1_p2_squareLength) as $dotProduct
| if $dotProduct < 0
then sum_of_squares(.x3 - .x1, .y3 - .y1)
elif $dotProduct <= 1
then sum_of_squares(.x1 - .x3, .y1 - .y3) as $p_p1_squareLength
| $p_p1_squareLength - $dotProduct * $dotProduct * $p1_p2_squareLength
else sum_of_squares(.x3 - .x2, .y3 - .y2)
end;
def accuratePointInTriangle(P1; P2; P3; Q):
if (pointInTriangleBoundingBox(P1; P2; P3; Q) | not) then false
elif naivePointInTriangle(P1; P2; P3; Q) then true
elif distanceSquarePointToSegment(P1; P2; Q) <= EPS_SQUARE then true
elif distanceSquarePointToSegment(P2; P3; Q) <= EPS_SQUARE then true
elif distanceSquarePointToSegment(P3; P1; Q) <= EPS_SQUARE then true
else false
end;</lang>
'''Examples'''
<lang jq>def task1:
def pts: [ [0, 0], [0, 1], [3, 1]];
"Triangle is \(.)",
(. as [$P1, $P2, $P3]
| pts[] as $Q
| accuratePointInTriangle($P1; $P2; $P3; $Q) as $within
| "Point \($Q) is within triangle ? \($within)"
);
def task2:
"Triangle is \(.)",
(. as [$P1, $P2, $P3]
| [ $P1[0] + (3/7)*($P2[0] - $P1[0]), $P1[1] + (3/7)*($P2[1] - $P1[1]) ] as $Q
| accuratePointInTriangle($P1; $P2; $P3; $Q) as $within
| "Point \($Q) is within triangle ? \($within)"
);
([ [3/2, 12/5], [51/10, -31/10], [-19/5, 1.2] ] | task1), "",
([ [1/10, 1/9], [100/8, 100/3], [100/4, 100/9] ] | task2), "",
([ [1/10, 1/9], [100/8, 100/3], [-100/8, 100/6] ] | task2)</lang>
{{out}}
<pre>
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
</pre>
=={{header|Julia}}==
| |||