Re: [Algorithms] 2d circular union nav-mesh

[Manuel M. <m.m...@wa...>]

Hi Paul,

checking for full containment seems like a good early-exit
strategy (always check against the last circle fully containing
the player).

The second case, i.e. the case where the player is fully contained
in the union of "land" circles (disks actually), but not fully contained 
in any single land disk, can probably be solved by circle->circle
intersection.

	For each land circle intersecting the player:

	1) Find the two intersection points of player and land circle
        (ignoring the special case of circles touching in one point) 
        
        The two intersection points are the start- and end-point of
        a segment on the player circle.

     2) Use an appropriate data structure to store the union of all the 
        segments spanned by the intersections of player<->land circles

     3) If the full circumference of the circle has been marked as
        intersected, the circle is fully contained in the union of land 
        disks.
        This, however, does not guarantee that the player _disk_ is
        fully contained! But if you start at a valid position (i.e. full
        containment of player), I don't think the player circle can hit 
        this case.

just based on a few back-of-the-envelope drawings, so take with a grain
of salt :-)

cheers,

   Manuel