Jump to content

Find if a point is within a triangle: Difference between revisions

Find if a point is within a triangle (view source)

Revision as of 18:20, 16 January 2022

13,859 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring, marked p2js compatible
(→‎{{header|Wren}}: Now uses new core library method.)
m (→‎{{header|Phix}}: added syntax colouring, marked p2js compatible)
Line 1,677:
=== using convex_hull ===
Using convex_hull() from [[Convex_hull#Phix]]
<!--<lang Phix>constant p0 = {0,0},(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
p1 = {0,1},
<span style="color: #008080;">constant</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span>
p2 = {3,1},
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
triangle = {{3/2, 12/5}, {51/10, -31/10}, {-19/5, 1/2}}
<span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
function inside(sequence p) return sort(convex_hull({p}&triangle))==sort(triangle) end function
<span style="color: #000000;">triangle</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">/</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">51</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">31</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{-</span><span style="color: #000000;">19</span><span style="color: #0000FF;">/</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}}</span>
printf(1,"Point %v is with triangle %v?:%t\n",{p0,triangle,inside(p0)})
<span style="color: #008080;">function</span> <span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
printf(1,"Point %v is with triangle %v?:%t\n",{p1,triangle,inside(p1)})
<span style="color: #008080;">return</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">convex_hull</span><span style="color: #0000FF;">({</span><span style="color: #000000;">p</span><span style="color: #0000FF;">}&</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">))==</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">))</span>
printf(1,"Point %v is with triangle %v?:%t\n",{p2,triangle,inside(p2)})</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)})</span>
<!--</lang>-->
{{out}}
<pre>
Line 1,693 ⟶ 1,698:
 
===trans python===
(same output)
(using the same p0/p1/p2/triangle constants from above, same output)
<!--<lang Phix>function side(sequence p1, p2, p3phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
-- which side of plane cut by line (p2, p3) is p1 on?▼
<span style="color: #008080;">constant</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span>
atom {x1, y1} = p1,
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
{x2, y2} = p2,
<span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
{x3, y3} = p3
<span style="color: #000000;">triangle</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">/</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">51</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">31</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{-</span><span style="color: #000000;">19</span><span style="color: #0000FF;">/</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}}</span>
return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3)
end function
<span style="color: #008080;">function</span> <span style="color: #000000;">side</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p3</span><span style="color: #0000FF;">)</span>
function iswithin(sequence point, triangle)
▲ <span style="color: #000080;font-style:italic;">-- which side of plane cut by line (p2, p3) is p1 on?</span>
--
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span>
-- Determine if point is within triangle.▼
<span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span>
-- If so, the point will be on the same side of each of the half planes
<span style="color: #0000FF;">{</span><span style="color: #000000;">x3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y3</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p3</span>
-- defined by vectors p1p2, p2p3, and p3p1. zval is positive if outside,▼
<span style="color: #008080;">return</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">x1</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">x3</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">*</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">y2</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">y3</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">-</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">x2</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">x3</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">*</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">y1</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">y3</span><span style="color: #0000FF;">)</span>
-- negative if inside such a plane. All should be positive or all negative▼
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
-- if point is within the triangle.▼
--
<span style="color: #008080;">function</span> <span style="color: #000000;">iswithin</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">point</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">triangle</span><span style="color: #0000FF;">)</span>
sequence {pt1, pt2, pt3} = triangle
<span style="color: #000080;font-style:italic;">--
atom zval1 = side(point, pt1, pt2),
▲ -- Determine if point is within triangle.
zval2 = side(point, pt2, pt3),
-- If so, the point will be on zval3the =same side(point, pt3,of each of the half pt1)planes
▲ -- defined by vectors p1p2, p2p3, and p3p1. zvalside is positive if outside,
bool notanyneg = zval1 >= 0 and zval2 >= 0 and zval3 >= 0,
▲ -- negative if inside such a plane. All should be positivenon-negative or all negative
notanypos = zval1 <= 0 and zval2 <= 0 and zval3 <= 0
▲ -- non-positive if the point is within the triangle.
return notanyneg or notanypos
--</span>
end function
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">pt1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt3</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">triangle</span>
 
<span style="color: #004080;">atom</span> <span style="color: #000000;">side12</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">side</span><span style="color: #0000FF;">(</span><span style="color: #000000;">point</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt2</span><span style="color: #0000FF;">),</span>
printf(1,"point %v is with triangle %v?:%t\n",{p0,triangle,iswithin(p0,triangle)})
<span style="color: #000000;">side23</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">side</span><span style="color: #0000FF;">(</span><span style="color: #000000;">point</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt3</span><span style="color: #0000FF;">),</span>
printf(1,"point %v is with triangle %v?:%t\n",{p1,triangle,iswithin(p1,triangle)})
<span style="color: #000000;">side31</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">side</span><span style="color: #0000FF;">(</span><span style="color: #000000;">point</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt1</span><span style="color: #0000FF;">)</span>
printf(1,"point %v is with triangle %v?:%t\n",{p2,triangle,iswithin(p2,triangle)})</lang>
<span style="color: #004080;">bool</span> <span style="color: #000000;">all_non_neg</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">side12</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">side23</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">side31</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">all_non_pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">side12</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">side23</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">side31</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">all_non_neg</span> <span style="color: #008080;">or</span> <span style="color: #000000;">all_non_pos</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iswithin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iswithin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iswithin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">)})</span>
<!--</lang>-->
 
=={{header|Python}}==
Petelomax
7,794

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/303884"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information