is within ... polygon shape?

[Alex Tweedly]

Jim Hurley wrote:

>
> Take a look at:
>
> go stack url "http://home.infostations.net/jhurley/CollidingPolygons.rev"
>
Sorry, Jim, but that doesn't work for all polygons. For example (excuse 
the ascii drawing ....)


        111111111
        1       1
        1       1
   22222222222222222222222
   2                     2
   22222222222222222222222
        1       1
        111111111

Even for 2  rectangles, it doesn't always work.  If I remember 
correctly, the most effective algorithm for overlap depends on edge 
intersections (with a special case test for one polygon entirely within 
the other). Any two polygons that overlap will have at least one case 
where their edges intersect - though you need to deal with the special 
cases where the edges touch; you can then test the mid-point of the 
edges adjacent to the point of touch to determine if they are within or 
outwith the other polygon (or alternatively, test the points 1 delta 
away from the point of touch - but then you need to be very careful 
about precision and rounding errors).

 And even then, you have some weird corner cases involved in 
self-reflexive polygons - far less Rev's "invisible edge" polygons which 
can produce disjoint areas.

(Is self-reflexive the right term ?  polygons that overlap themselves, like

     11111
     1   1
  111111111111111
  1             1
  111111111111  1
      1  1   1  1
      1  1   1  1
      1  11111  1
      1         1
      11111111111


You need to determine whether the points in the self-overlap area are 
within the polygon or not ...  and I can't remember which is the "right" 
decision, i.e. the one that makes the problem easier.

-- 
Alex Tweedly       http://www.tweedly.net



-- 
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.323 / Virus Database: 267.8.0/27 - Release Date: 23/06/2005