Anonymous user
Ray-casting algorithm: Difference between revisions
+ Tcl
(new task (from cs page wanted) + C code (and planned enhancements)) |
(+ Tcl) |
||
Line 124:
{
if ( (s->y >= MAX(a->y, b->y) ||
s->y <= MIN(a->y, b->y)) ||
(s->x > MAX(a->x, b->x) )
) return false;
Line 144:
for(i=0; poly->edges[i] != -1 ; i+=2) {
if ( hseg_intersect_seg(pt,
cross++;
}
Line 153:
Testing:
<lang c>#define MAKE_TEST(S) do {
printf("point (%.5f,%.5f) is ", test_points[i].x, test_points[i].y); \
if ( point_is_inside(&S, &test_points[i]) )
printf("INSIDE " #S "\n");
else
printf("OUTSIDE " #S "\n");
} while(0);
Line 165:
{
point_t test_points[] = { {5,5}, {5,8}, {2,2},
int i;
Line 180:
The test's output reveals the meaning of <cite>coherent results</cite>: a point on the leftmost vertical side of the square (coordinate 0,5) is considered outside; while a point on the rightmost vertical side of the square (coordinate 10,5) is considered inside, but on the top-right vertex (coordinate 10,10), it is considered outside again.
=={{header|Tcl}}==
<lang Tcl>package require Tcl 8.5
proc point_in_polygon {point polygon} {
set count 0
foreach side [sides $polygon] {
if [ray_intersects_line $point $side] {incr count}
}
expr {$count % 2} ;#-- 1 = odd = true, 0 = even = false
}
proc sides polygon {
foreach {x0 y0} $polygon break
foreach {x y} [lrange [lappend polygon $x0 $y0] 2 end] {
lappend res [list $x0 $y0 $x $y]
set x0 $x
set y0 $y
}
return $res
}
proc ray_intersects_line {point line} {
foreach {x y} $point break
foreach {xa xb ya yb} $line break
set xout [expr {max($xa,$xb) + 1}]
lines_cross [list $x $y $xout $y] $line
}
proc lines_cross {line1 line2} {
foreach {xa ya xb yb} $line1 break
foreach {xc yc xd yd} $line2 break
set det [expr {($xb - $xa) * ($yd - $yc)
- ($xd - $xc) * ($yb - $ya)}]
if {$det == 0} {return 0} ;#-- parallel or collinear
set nump [expr {($xd - $xc) * ($yb + $ya)
- ($xb + $xa) * ($yd - $yc)
+ 2. * ($xc * $yd - $xd * $yc)}]
if {abs($nump) > abs($det)} {return 0} ;#-- cross outside line1
set numq [expr {($xd + $xc) * ($yb - $ya)
- ($xb - $xa) * ($yd + $yc)
+ 2. * ($xb * $ya - $xa * $yb)}]
if {abs($numq) > abs($det)} {return 0} ;#-- cross outside line2
return 1
}
foreach {point poly} {
{0 0} {-1 -1 -1 1 1 1 1 -1}
{2 2} {-1 -1 -1 1 1 1 1 -1}
{0 0} {-2 -2 -2 2 2 2 2 -2
2 -1 1 1 -1 1 -1 -1 1 -1 2 -1}
{1.5 1.5} {-2 -2 -2 2 2 2 2 -2
2 -1 1 1 -1 1 -1 -1 1 -1 2 -1}
{5 5} {0 0 2.5 2.5 0 10 2.5 7.5 7.5 7.5 10 10 10 0 7.5 0.1}
{5 8} {0 0 2.5 2.5 0 10 2.5 7.5 7.5 7.5 10 10 10 0 7.5 0.1}
{2 2} {0 0 2.5 2.5 0 10 2.5 7.5 7.5 7.5 10 10 10 0 7.5 0.1}
{0 0} {0 0 2.5 2.5 0 10 2.5 7.5 7.5 7.5 10 10 10 0 7.5 0.1}
{10 10} {0 0 2.5 2.5 0 10 2.5 7.5 7.5 7.5 10 10 10 0 7.5 0.1}
{2.5 2.5} {0 0 2.5 2.5 0 10 2.5 7.5 7.5 7.5 10 10 10 0 7.5 0.1}
} {
puts "$point in $poly = [point_in_polygon $point $poly]"
}
</lang>
| |||