[Algorithms] 2d circular union nav-mesh

[<Pau...@sc...>]

-----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-----