OpenEuphoria

RE: finding if point is inside irregular rectangle

• Posted by bensler at mail.com Feb 25, 2002
• 435 views

I've been playing with intersectring polygons code, and my solution for 
the double counted vertices was to make my formula like this:

if (edge[x1] < point[x]) and (edge[x2] >= point[x]) then ...
if (edge[x2] <= point[x]) and (edge[x1] > point[x]) then ...

only vertex 2 is counted for each edge

Chris

BTW: I've tried implementing David's code using two shapes to check for 
instersections, and I can get it to work when shape1 is upper/leftmost. 
When shape2 is upper/leftmost, it fails. Can someone verify that code? 
David? I'm pretty sure I understand the algorithm.

Chris

Derek Parnell wrote:
> You're right David. I misunderstood the algorithm. When it said 
> 
> >1. imagine a horizontal line through the Point
> >2. compute the x-value where any polygon side crosses the imaginary line
> >(simple geometry using the slope of the side)
> >3. if the x-coordinate of the Point is greater than an odd number of
> >x-values then the Point is inside the polygon.  If it is less than the
> >lowest x-value or greater than an even number of x-values, then it is
> >outside the polygon
> >
> 
> I read it as , if the number of x-values is an odd number, then if the 
> x-coord is greater than any 
> of them, it is inside. Etcc...
> 
> Being a simple person, maybe it would have been clearer to me if it had 
> of said:
> 
>   "If the number of x-values that are less than the x-coord is odd, it is 
>   inside."
> 
> However, there is still the special case of x-values that are vertices. 
> 
> I'm not sure if they should be counted as two or one x-value.
> 
> Consider these two case:
> 
>   A polygon with vertices at  (0,0) (10,200) (20,50) and (200,100), and a 
>   point at (30,50).
> 
> If we count vertices as two x-values then the algo above is fine.
> 
> But:
> 
>   A polygon with vertices at  (0,50) (50,100) (100,50) and (50,0), and a 
>   point at (50,50).
> 
> If we count vertices as two x-values then the algo above fails.
> 
> Any ideas?
> ---------
> Derek
> 
> 
> 26/02/2002 2:25:26 PM, David Cuny <dcuny at LANSET.COM> wrote:
> 
> >
> >Derek Parnell wrote:
> >
> >> Not sure if this works for concave polygons.
> >
> >It should. Odd/Even edge crossing is pretty much the classic method. 
> >Plus, 
> >it's easy to optimize. You don't have to actually cast a ray, you just 
> >count 
> >the number lines that "cover" the point that lie above the point (ie: 
> >the x 
> >of the point lies between (x1, x2) and the one of (y1,y2) lies above the 
> >y of 
> >the point. Something like:
> >
> >-- p = {x,y}
> >-- l = { {x1,y1}, {x2,y2}}
> >function crosses( sequence p, sequence l )
> >   if l[1][2] >= p[1] or l[2][2] >= p[2] then
> >      if l[1][1] < l[2][1] then
> >         return l[1][1] <= p[1] and l[2][1] >= p[1]
> >      else
> >         return l[2][1] <= p[1] and l[1][1] >= p[1]
> >      end if
> >   end if
> >   return 0
> >end function
> >
> >Untested code, of course. 
> >
> >-- David Cuny
> >
> >
> ---------
> Cheers,
> Derek Parnell 
> 
>