Find if a point is within a triangle: Difference between revisions
Content added Content deleted
(→{{header|ALGOL 68}}: notes) |
|||
Line 838: | Line 838: | ||
Triangle[(0.100000, 0.111111), (12.500000, 33.333333), (-12.500000, 16.666667)] |
Triangle[(0.100000, 0.111111), (12.500000, 33.333333), (-12.500000, 16.666667)] |
||
Point (5.414286, 14.349206) is within triangle? true</pre> |
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}}== |
=={{header|Julia}}== |