Ray-casting algorithm: Difference between revisions

Content added Content deleted
m (comment: edges not corners)
m (→‎{{header|REXX}}: corrected a typo, changed some comments.)
Line 2,525: Line 2,525:


=={{header|REXX}}==
=={{header|REXX}}==
Over half of the REXX program is devoted to specifing/defining/assigning the points for
Over half of the REXX program is devoted to specifying/defining/assigning the points for the test cases and the polygons.

<br>the test cases and the polygons.
<br>Code was added to facilitate easier specification of polygon sides by
Code was added to facilitate easier specification of polygon sides by just specifying their vertices instead of specifying line segments.

<br>just specifying their vertices instead of specifying line segments.
<br><br>Points on a vertex (or side) don't obtain ''coherent'' results, but casual observation
Points on a vertex (or side) don't obtain &nbsp; ''coherent'' &nbsp; results, but casual observation
<br>seems to indicate that this program considers those points as outside the polygon.
seems to indicate that this code considers those points as outside the polygon.
<lang rexx>/*REXX program to see if a horizontal ray from pt P intersects a polygon*/
<lang rexx>/*REXX pgm checks to see if a horizontal ray from point P intersects a polygon*/
call points 5 5, 5 8, -10 5, 0 5, 10 5, 8 5, 10 10
call points 5 5, 5 8, -10 5, 0 5, 10 5, 8 5, 10 10
call polygon 0 0, 10 0, 10 10, 0 10 ; call test 'square'
call polygon 0 0, 10 0, 10 10, 0 10 ; call test 'square'
call polygon 0 0, 10 0, 10 10, 0 10, 2.5 2.5, 7.5 2.5, 7.5 7.5, 2.5 7.5 ; call test 'square hole'
call polygon 0 0, 10 0, 10 10, 0 10, 2.5 2.5, 7.5 2.5, 7.5 7.5, 2.5 7.5 ; call test 'square hole'
call polygon 0 0, 2.5 2.5, 0 10, 2.5 7.5, 7.5 7.5, 10 10, 10 0 ; call test 'irregular'
call polygon 0 0, 2.5 2.5, 0 10, 2.5 7.5, 7.5 7.5, 10 10, 10 0 ; call test 'irregular'
call polygon 3 0, 7 0, 10 5, 7 10, 3 10, 0 5 ; call test 'exagon'
call polygon 3 0, 7 0, 10 5, 7 10, 3 10, 0 5 ; call test 'hexagon'
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're all done. */
/*────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────IN_OUT subroutine────────────────────*/
in_out: procedure expose point. poly. /*note: // is division remainder.*/
in_out: procedure expose point. poly.; parse arg p; #=0
parse arg p; #=0; do side=1 to poly.0 by 2; #=#+ray_intersect(p,side)
do side=1 to poly.0 by 2; #=#+ray_intersect(p,side)
end /*side*/
end /*side*/
return #//2 /*odd=inside, return 1; else 0.*/
return #//2 /*ODD is inside. EVEN is outside. */
/*────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────POINTS subroutine───────────────────*/
points: n=0; v='POINT.'; do j=1 for arg(); n=n+1
points: n=0; v='POINT.'; do j=1 for arg(); n=n+1; _=arg(j); parse var _ xx yy
call value v||n'.X', word(arg(j),1)
call value v||n'.X',xx
call value v||n'.Y', word(arg(j),2)
call value v||n'.Y',yy
end /*j*/
end /*j*/
call value v'0',n /*define number of points.*/
call value v'0',n /*define the number of points.*/
return
return
/*────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────POLYGON subroutine──────────────────*/
polygon: n=0; v='POLY.'; parse arg Fx Fy
polygon: n=0; v='POLY.'; parse arg Fx Fy /* [↓] process the X,Y points*/


do j=1 for arg(); _=arg(j); n=n+1
do j=1 for arg(); n=n+1; _=arg(j); parse var _ xx yy
call value v||n'.X', word(_,1); call value v||n'.Y', word(_,2)
call value v||n'.X', word(_,1); call value v||n'.Y', word(_,2)
if n//2 then iterate
if n//2 then iterate
n=n+1
n=n+1
call value v||n'.X', word(_,1); call value v||n'.Y', word(_,2)
call value v||n'.X', word(_,1); call value v||n'.Y', word(_,2)
end /*j*/
end /*j*/
n=n+1
n=n+1
call value v||n".X", Fx; call value v||n".Y", Fy; call value v'0',n
call value v||n".X", Fx; call value v||n".Y", Fy; call value v'0',n
return /*POLY.0 is # of segments/sides.*/
return /*POLY.0 is number of segments/sides.*/
/*────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────RAY_INTERSECT subroutine────────────*/
ray_intersect: procedure expose point. poly.; parse arg ?,s; sp=s+1
ray_intersect: procedure expose point. poly.; parse arg ?,s; sp=s+1
epsilon = '1e'||(digits()%2); infinity = '1e'||(digits()*2)
epsilon='1e' || (digits()%2); infinity='1e' || (digits()*2)
Px=point.?.x; Py=point.?.y
Px=point.?.x; Py=point.?.y
Ax=poly.s.x; Bx=poly.sp.x ; Ay=poly.s.y; By=poly.sp.y
Ax=poly.s.x; Bx=poly.sp.x; Ay=poly.s.y; By=poly.sp.y
if Ay>By then parse value Ax Ay Bx By with Bx By Ax Ay
if Ay>By then parse value Ax Ay Bx By with Bx By Ax Ay
if Py=Ay | Py=By then Py=Py+epsilon
if Py=Ay | Py=By then Py=Py+epsilon
if Py<Ay | Py>By | Px>max(Ax,Bx) then return 0
if Py<Ay | Py>By | Px>max(Ax,Bx) then return 0
if Px<min(Ax,Bx) then return 1
if Px<min(Ax,Bx) then return 1
if Ax\=Bx then m_red = (By-Ay) / (Bx-Ax); else m_red = infinity
if Ax\=Bx then m_red =(By-Ay)/(Bx-Ax)
else m_red=infinity
if Ax\=Px then m_blue = (Py-Ay) / (Px-Ax); else return 1
if Ax\=Px then m_blue=(Py-Ay)/(Px-Ax)
return m_blue>=m_red
else return 1
/*──────────────────────────────────TEST procedure──────────────────────*/
test: say; do k=1 for point.0 /*traipse through each test point*/
return m_blue>=m_red
/*────────────────────────────────────────────────────────────────────────────*/
⚫
say ' ['arg(1)"] point:" right(point.k.x','point.k.y, 9),
test: say; do k=1 for point.0; say right(' ['arg(1)"] point:",30),
⚫
" is " word('outside inside', in_out(k)+1)
⚫
right(point.k.x', 'point.k.y, 9) " is ",
⚫
end /*k*/
⚫
word('outside inside', in_out(k)+1)
⚫
return</lang>
⚫
end /*k*/
⚫
return</lang>
'''output'''
'''output'''
<pre>
<pre style="height:50ex">
[square] point: 5,5 is inside
[square] point: 5, 5 is inside
[square] point: 5,8 is inside
[square] point: 5, 8 is inside
[square] point: -10,5 is outside
[square] point: -10, 5 is outside
[square] point: 0,5 is outside
[square] point: 0, 5 is outside
[square] point: 10,5 is inside
[square] point: 10, 5 is inside
[square] point: 8,5 is inside
[square] point: 8, 5 is inside
[square] point: 10,10 is outside
[square] point: 10, 10 is outside


[square hole] point: 5,5 is outside
[square hole] point: 5, 5 is outside
[square hole] point: 5,8 is inside
[square hole] point: 5, 8 is inside
[square hole] point: -10,5 is outside
[square hole] point: -10, 5 is outside
[square hole] point: 0,5 is outside
[square hole] point: 0, 5 is outside
[square hole] point: 10,5 is inside
[square hole] point: 10, 5 is inside
[square hole] point: 8,5 is inside
[square hole] point: 8, 5 is inside
[square hole] point: 10,10 is outside
[square hole] point: 10, 10 is outside


[irregular] point: 5,5 is inside
[irregular] point: 5, 5 is inside
[irregular] point: 5,8 is outside
[irregular] point: 5, 8 is outside
[irregular] point: -10,5 is outside
[irregular] point: -10, 5 is outside
[irregular] point: 0,5 is outside
[irregular] point: 0, 5 is outside
[irregular] point: 10,5 is inside
[irregular] point: 10, 5 is inside
[irregular] point: 8,5 is inside
[irregular] point: 8, 5 is inside
[irregular] point: 10,10 is outside
[irregular] point: 10, 10 is outside


[exagon] point: 5,5 is outside
[hexagon] point: 5, 5 is outside
[exagon] point: 5,8 is inside
[hexagon] point: 5, 8 is inside
[exagon] point: -10,5 is outside
[hexagon] point: -10, 5 is outside
[exagon] point: 0,5 is outside
[hexagon] point: 0, 5 is outside
[exagon] point: 10,5 is outside
[hexagon] point: 10, 5 is outside
[exagon] point: 8,5 is outside
[hexagon] point: 8, 5 is outside
[exagon] point: 10,10 is outside
[hexagon] point: 10, 10 is outside
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Ray-casting_algorithm"