OpenEuphoria

Polygon Intersection

• Posted by Lewis Townsend <keroltarr at HOTMAIL.COM> Jul 05, 2001
• 370 views

Hello everyone,

Jeffrey Fielding sent the following solution to the polygon intersection 
problem I posted earlier. He couldn't get through to the list and has given 
me permission to post his work on the list. If anyone can improve upon this, 
be my guest. I would like to start one of those code threads that used to be 
so common on the list.

later,
Lewis Townsend

>function poly_to_lines(sequence poly)
>     sequence lines
>     lines = repeat(0, length(poly))
>     for i = 1 to length(poly)-1 do
>	lines[i] = {poly[i],poly[i+1]}
>     end for
>     lines[length(lines)] = {poly[length(poly)],poly[1]}
>     return lines
>end function
>function distance(atom x1, atom y1, atom x2, atom y2)
>     atom dx, dy
>     dx = x2-x1
>     dy = y2-y1
>     return sqrt((dx*dx)+(dy*dy))
>end function
>function round(atom x)
>     if x-floor(x) >= 0.5 then
>	return floor(x)+1
>     else
>	return floor(x)
>     end if
>end function
>function fix(atom x)
>     return round(x * 1000)
>end function
>function between(atom v, atom top, atom bottom)
>     v = fix(v)
>     top = fix(top)
>     bottom = fix(bottom)
>     return ((v <= top) and (v >= bottom)) or ((v >= top) and (v <= 
>bottom))
>end function
>function IntersectPolygon(atom x1, atom y1, atom x2, atom y2, sequence
>poly)
>     sequence lines
>     atom dx, dy, ray_slope, line_slope, tmp2, lx1, lx2, ly1, ly2
>     object tmp, best
>     atom best_distance, dst
>     best = 0
>     best_distance = -1
>     if x1 = x2 then
>	for i = 1 to length(poly) do
>	    poly[i] = {poly[i][2],poly[i][1]}
>	end for
>	tmp = IntersectPolygon(y1,x1,y2,x2,poly)
>	if sequence(tmp) then
>	    return {tmp[2],tmp[1]}
>	else
>	    return 0
>	end if
>     end if
>     dx = x2-x1
>     dy = y2-y1
>     ray_slope = dy/dx
>     lines = poly_to_lines(poly)
>     for i = 1 to length(lines) do
>	lx1 = lines[i][1][1]
>	ly1 = lines[i][1][2]
>	lx2 = lines[i][2][1]
>	ly2 = lines[i][2][2]
<snip>