I am developing a real-time strategy game where you are able to move a number of your units around a map. When a unit is selected, I draw a circle around that unit to represent that unit's vision range. However, when multiple units are selected their vision range circles overlap, and it ends up looking quite messy.
Here is an example of 72 units arranged in a box all selected: all units selected
And here is what it looks like zoomed out: zoomed out
What I would like is an equation so that I can represent just the outside borders of those circles, which in this example would look something like a rounded rectangle. My inputs would be the individual unit positions, represented in my case as lat,lng (but x,y I suppose would also be OK), as well as the diameter of each unit's circle (which in this case are all the same at 50 metres, but won't always be).
Is there any formula that can calculate and represent this polygon, such that it is drawable using common computer drawing APIs (such as HTML5 canvas)?
Many thanks, Arj
What you are seeking is called in the literature, computing the union of disks. There is no simple algorithm known. Here are two possible routes:
(1) Use the power diagram to construct the boundary of the union of disks, as explained in this paper:
(2) Use the CGAL package for Boolean operations on "general polygons": CGAL manual link.