Rosetta Code

Ray-casting algorithm: Difference between revisions

Page Discussion

Ray-casting algorithm (view source)

Revision as of 13:40, 28 March 2021

27,619 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 2,535:
 
=={{header|Phix}}==
<!--<lang Phix>constant true = (1=1), false = not true-->
<span style="color: #008080;">constant</span> <span style="color: #000000;">inf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e300</span><span style="color: #0000FF;">*</span><span style="color: #000000;">1e300</span>
constant inf = 1e300*1e300
<span style="color: #008080;">function</span> <span style="color: #000000;">rayIntersectsSegment</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: #004080;">sequence</span> <span style="color: #000000;">segment</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">segment</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">pX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">point</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">aY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">m_red</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m_blue</span>
<span style="color: #000080;font-style:italic;">-- ensure {aX,aY} is the segment end-point with the smallest y coordinate</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">aY</span><span style="color: #0000FF;">></span><span style="color: #000000;">bY</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">aY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pY</span><span style="color: #0000FF;">=</span><span style="color: #000000;">aY</span> <span style="color: #008080;">or</span> <span style="color: #000000;">pY</span><span style="color: #0000FF;">=</span><span style="color: #000000;">bY</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">--
-- Consider a ray passing through the top or left corner of a diamond:
-- /
-- --- or -
-- ^ \
-- In both cases it touches both edges, but ends up outside in the
-- top case, whereas it ends up inside in the left case. Just move
-- the y co-ordinate down a smidge and it'll work properly, by
-- missing one line in the left/right cases and hitting both/none
-- in the top/bottom cases.
--</span>
<span style="color: #000000;">pY</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">0.000001</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pY</span><span style="color: #0000FF;"><</span><span style="color: #000000;">aY</span> <span style="color: #008080;">or</span> <span style="color: #000000;">pY</span><span style="color: #0000FF;">></span><span style="color: #000000;">bY</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pX</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pX</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">aX</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">bX</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">m_red</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">bY</span><span style="color: #0000FF;">-</span><span style="color: #000000;">aY</span><span style="color: #0000FF;">)/(</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">-</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">m_red</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inf</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">aX</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">pX</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">m_blue</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">pY</span><span style="color: #0000FF;">-</span><span style="color: #000000;">aY</span><span style="color: #0000FF;">)/(</span><span style="color: #000000;">pX</span><span style="color: #0000FF;">-</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">m_blue</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inf</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">m_blue</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">m_red</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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;">point</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rayIntersectsSegment</span><span style="color: #0000FF;">(</span><span style="color: #000000;">point</span><span style="color: #0000FF;">,</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">not</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">instr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">flag</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"in"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"out"</span><span style="color: #0000FF;">}[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">flag</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">flag</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">expected</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">"*** ERROR ***"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">instar</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">flag</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #008000;">"* "</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">flag</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">test_points</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">--constant NAME = 1, POLY = 2, EXPECTED = 3</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">test_polygons</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"square"</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><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</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>
<span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"square hole"</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><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</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>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"strange"</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;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"exagon"</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;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}}</span>
<span style="color: #0000FF;">}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">name</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tp</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test_polygons</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">name</span><span style="color: #0000FF;">,</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test_polygons</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</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;">"\n%12s:"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">name</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test_points</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test_points</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</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;">" %s, %-4s"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tp</span><span style="color: #0000FF;">),</span><span style="color: #000000;">instr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">),</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n\n\n"</span><span style="color: #0000FF;">)</span>
function rayIntersectsSegment(sequence point, sequence segment)
atom {pX,pY} = point
atom {{aX,aY},{bX,bY}} = segment
atom m_red,m_blue
-- ensure {aX,aY} is the segment end-point with the smallest y coordinate
if aY>bY then
{{bX,bY},{aX,aY}} = segment
end if
if pY=aY or pY=bY then
--
-- Consider a ray passing through the top or left corner of a diamond:
-- /
-- --- or -
-- ^ \
-- In both cases it touches both edges, but ends up outside in the
-- top case, whereas it ends up inside in the left case. Just move
-- the y co-ordinate down a smidge and it'll work properly, by
-- missing one line in the left/right cases and hitting both/none
-- in the top/bottom cases.
--
pY += 0.000001
end if
if pY<aY or pY>bY then return false end if
if pX>max(aX,bX) then return false end if
if pX<min(aX,bX) then return true end if
if aX!=bX then
m_red = (bY-aY)/(bX-aX)
else
m_red = inf
end if
if aX!=pX then
m_blue = (pY-aY)/(pX-aX)
else
m_blue = inf
end if
return m_blue >= m_red
end function
 
function inside(sequence point, sequence poly)
integer in = 0
for i=1 to length(poly) do
if rayIntersectsSegment(point,poly[i]) then
in = not in
end if
end for
return in
end function
 
constant INOUT = {"in", "out"}
function in(integer flag, integer expected)
if flag=expected then
return INOUT[2-flag]
end if
return INOUT[2-flag] & "*** ERROR ***"
end function
 
constant INSTAR = "* "
function instar(integer flag)
return INSTAR[2-flag]
end function
 
constant test_points = {{5,5},{5,8},{-10,5},{0,5},{10,5},{8,5},{10,10}}
 
--constant NAME = 1, POLY = 2, EXPECTED = 3
constant test_polygons = {
{"square", {{{0,0},{10,0}},{{10,0},{10,10}},{{10,10},{0,10}},{{0,10},{0,0}}},
{true,true,false,false,true,true,false}},
{"square hole", {{{0,0},{10,0}},{{10,0},{10,10}},{{10,10},{0,10}},{{0,10},{0,0}},
{{2.5,2.5},{7.5,2.5}},{{7.5,2.5},{7.5,7.5}},{{7.5,7.5},{2.5,7.5}},{{2.5,7.5},{2.5,2.5}}},
{false,true,false,false,true,true,false}},
{"strange", {{{0,5},{2.5,2.5}},{{2.5,2.5},{0,10}},{{0,10},{2.5,7.5}},{{2.5,7.5},{7.5,7.5}},
{{7.5,7.5},{10,10}},{{10,10},{10,0}},{{10,0},{2.5,2.5}}},
{true,false,false,false,true,true,false}},
{"exagon", {{{3,0},{7,0}},{{7,0},{10,5}},{{10,5},{7,10}},{{7,10},{3,10}},{{3,10},{0,5}},{{0,5},{3,0}}},
{true,true,false,false,true,true,false}}
}
 
sequence name, poly, expected, tp
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
for i=1 to length(test_polygons) do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test_polygons</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
{name,poly,expected} = test_polygons[i]
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)</span>
printf(1,"\n%12s:",{name})
<span style="color: #000000;">poly</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test_polygons</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
for j=1 to length(test_points) do
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
tp = test_points[j]
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">instar</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">({</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">0.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10.5</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">},</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">)))</span>
printf(1," %s, %-4s",{sprint(tp),in(inside(tp,poly),expected[j])})
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
puts(1,"\n\n\n")
<!--</lang>-->
 
for i=0 to 10 do
for j=1 to length(test_polygons) do
puts(1," ")
poly = test_polygons[j][2]
for k=0 to 10 do
puts(1,instar(inside({k+0.5,10.5-i},poly)))
end for
end for
puts(1,"\n")
end for</lang>
{{out}}
<pre>
Petelomax
7,806

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/111399"