OpenEuphoria

Re: intersection and ExoticaX

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

Hello Jiri, Jeff,


>BTW, Jeff, I would like to have a look at your solution, unfortunately
>Lewis' note with it was truncated.
>
>jiri

Oops, I wonder how that happened. Here it is again. It looks whole to me 
right now, so if it is truncated again it must be hotmail or Topica that is 
doing it.

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]
	if lx1 = lx2 and ((lx1-x1)*dx) >= 0 then
	    tmp = y1 + (ray_slope * (lx1 - x1))
	    if between(tmp,ly1,ly2) then
		dst = distance(x1,y1,lx1,tmp)
		if integer(best) or dst < best_distance then
		    best = {lx1,tmp}
		    best_distance = dst
		    if dst = 0 then
			return best
		    end if
		end if
	    end if
	elsif lx1 != lx2 then
	    line_slope = (ly2-ly1)/(lx2-lx1)
	    if ray_slope = line_slope then
		if (y1 - (x1 * ray_slope)) = (ly1 - (lx1 * line_slope))
then
		    if between(x1, lx1, lx2)  then
			return {x1, y1}
		    else
			tmp = 0
			if (lx1-x1)*dx >= 0 then
			    tmp = lines[i][1]
			end if
			if (lx2-x1)*dx >= 0 then
			    if integer(tmp) then
				tmp = lines[i][2]
			    else
				if ((tmp[1]-x1)*dx) > ((lx2-x1)*dx) then
				    tmp = lines[i][2]
				end if
			    end if
			end if
			if sequence(tmp) then
			    dst = distance(x1,y1,tmp[1],tmp[2])
			    if integer(best) or dst < best_distance then
				best = tmp
				best_distance = dst
			    end if
			end if
		    end if
		end if
	    else
		tmp = (ly1 - (line_slope * lx1) - y1 + (ray_slope *
x1))/(ray_slope - line_slope)
		tmp2 = y1 + (ray_slope * (tmp - x1))
		if ((tmp-x1)*dx) >= 0 then
		    if between(tmp,lx1,lx2) and
		       between(tmp2,ly1,ly2) then
			dst = distance(x1,y1,tmp,tmp2)
			if integer(best) or dst < best_distance then
			    best = {tmp,tmp2}
			    best_distance = dst
			    if dst = 0 then
				return best
			    end if
			end if
		    end if
		end if
	    end if
	end if
    end for
    return best
end function