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

[Jeremy <jsw...@gm...>]

Assuming you have a choice in the method, would it not be easier to use the
interior of any circles as walkable space, rather than the unions, and
construct 'portals' between the line formed between the intersection points
of each overlapping circle? Alternatively to reduce the number of circles
significantly, circles can represent walkable space, circles can be
explicitly linked together, and it could be assumed that the corridor built
between the circles along their tangents is valid walkable space as well.

On Wed, May 26, 2010 at 8:16 AM, Manuel Massing
<m.m...@wa...>wrote:

> 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
>
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>