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

[Marius E. <mar...@go...>]

Hey,

I'm pretty sure you cannot get away without clipping the test circle against
the container circles, tho I do not have proof.
You can probably use a slightly modified polygon clipping routine, storing
the edges as circle-arcs or NURBs and test for intersection with those.

Regards,
Marius



On Wed, May 26, 2010 at 1:11 PM, <Pau...@sc...> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> Hi guys,
>
> Does anyone have any references or pointers for how to constrain a small
> character (represented by a circle) within the interior of the union of a
> set of larger circles?
>
> The background is, the larger circles define regions of land where the
> small circle can navigate around (like a nav mesh), and the union of the
> these circles defines the entire nav-mesh. The character is not allowed to
> leave the interior of the nav-mesh and must remain wholly inside it at all
> times.
>
> Some diagrams:
>
> The general case, the filled circle represents the character and the
> hollow circles the land
>
> http://www.pfirth.co.uk/ex1.png
>
> My first attempt was to ensure the character was wholly inside at least
> one land circle, but that fails in this case:
>
> http://www.pfirth.co.uk/ex2.png
>
> In that example, if the character moves any further up, it will not be
> wholly contained in either circle and will fail, yet it should be able to
> navigate between them.
>
> Cheers, Paul.
> **********************************************************************
> This email and any files transmitted with it are confidential and intended
> solely for the use of the individual or entity to whom they are addressed.
> If you have received this email in error please notify pos...@sc...
> This footnote also confirms that this email message has been checked for
> all known viruses.
> Sony Computer Entertainment Europe Limited
> Registered Office: 10 Great Marlborough Street, London W1F 7LP, United
> Kingdom
> Registered in England: 3277793
> **********************************************************************
> P Please consider the environment before printing this e-mail
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP Universal 2.9.1 (Build 287)
> Charset: US-ASCII
>
> wsBVAwUBS/0BJ3ajGqjtoMHxAQg3qwf/Tm6Az23UjEAY74p59oYl/orGaER6D8e+
> 5fIBti3CPtE6S0+BgwA5r9BRmh4gEC8D67ZloK4C+XuGIHhdJ5VOf4lvr/dtT8FZ
> YwrDbAi7lWMsZQc8eEzTzNWMhay530ZoCT185yRD2EvPnqQPWvKDw4gW+LbK+FlB
> Cuefhck6JWG24qLZLnnbU5r8NBMjDYKJLf8AuBguR9zsNvNas0SWjwPWAiUPYYgd
> 9cw7lEM6rATI84Bpp+emZGWy8nasK+9MfLOcOtXF7bbUo+x2QSkOC6JzDAq56eHZ
> pK8tDhcfX3iH2s1+Tf6GORIiHvockZKxYZ5jt/vNoSuVOfawQlSNgw==
> =mS+v
> -----END PGP SIGNATURE-----
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> 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
>