   Total area of overlapping circles
  I want to calculate the overall unique coverage of my units' FOV (which are all circular). Luckly I don't need to do this every frame, but I can expect to have up to several dozens of circles that can overlap each other partially, fully ot not at all, although as a game-specific dynamic, there should not be any disjoint circles (that is, there can be, but I'm interested in the total coverage of all circles that are chain-connected to one control circle).I'm having some trouble coming up with a a solution that is both fast and reasonably exact. Truth be told, since this is for a game, I'm not bound by any ground rules and could simply opt for a tile coverage count (which should be doable in linear time); however, the problem itself intrigues me and I'm wondering if I could do away with the N^2 intersection tests that I'm guessing I'm stuck with if I want an exact method.PS - even though this might seem like a school assignment, it is not.   
I want to calculate the overall unique coverage of my units' FOV (which are all circular). Luckly I don't need to do this every frame, but I can expect to have up to several dozens of circles that can overlap each other partially, fully ot not at all, although as a game-specific dynamic, there should not be any disjoint circles (that is, there can be, but I'm interested in the total coverage of all circles that are chain-connected to one control circle).I'm having some trouble coming up with a a solution that is both fast and reasonably exact. Truth be told, since this is for a game, I'm not bound by any ground rules and could simply opt for a tile coverage count (which should be doable in linear time); however, the problem itself intrigues me and I'm wondering if I could do away with the N^2 intersection tests that I'm guessing I'm stuck with if I want an exact method.PS - even though this might seem like a school assignment, it is not.You don't have to do N^2 intersection tests if you have a scenegraph of some sort, for a 2D game you could simply split the level into section, then you simply only run tests against units in the same or neighbouring sections. (It will reduce the worst case scenario slightly, and depending on section size (Which would have to be atleast as big as the biggest FoV for the method to work).also, checking if 2 circles intersect eachother is extremely fast (just compare the sqared distance with the squared sum of the circles radius) (The reason for comparing squared values is that it eliminates the need to calculate the square root in the distance calculation)   ;  irreversible, do you actually need the area of their overlap, or just a boolean value which tells whether they overlap or not?If you actually need the area, then I think a simple way to do it is:- compute the intersection points of all pairs of circles- discard points that lie outside any other circle- compute the convex hull of these points- compute the area as the area of the convex hull polygon, plus the area of the parts between each edge of the convex hull, and the corresponding circular arc.There are probably many ways to do the first two steps quicker than N^2Let me know if this is clear. I can probably draw some pictures to clarify things a bit.But if you only need to know whether they intersect at all, then there are probably easier solutions.[quote name='irreversible' timestamp='1303644073' post='4802267']I want to calculate the overall unique coverage of my units' FOV (which are all circular). Luckly I don't need to do this every frame, but I can expect to have up to several dozens of circles that can overlap each other partially, fully ot not at all, although as a game-specific dynamic, there should not be any disjoint circles (that is, there can be, but I'm interested in the total coverage of all circles that are chain-connected to one control circle).I'm having some trouble coming up with a a solution that is both fast and reasonably exact. Truth be told, since this is for a game, I'm not bound by any ground rules and could simply opt for a tile coverage count (which should be doable in linear time); however, the problem itself intrigues me and I'm wondering if I could do away with the N^2 intersection tests that I'm guessing I'm stuck with if I want an exact method.PS - even though this might seem like a school assignment, it is not.You don't have to do N^2 intersection tests if you have a scenegraph of some sort, for a 2D game you could simply split the level into section, then you simply only run tests against units in the same or neighbouring sections. (It will reduce the worst case scenario slightly, and depending on section size (Which would have to be atleast as big as the biggest FoV for the method to work).also, checking if 2 circles intersect eachother is extremely fast (just compare the sqared distance with the squared sum of the circles radius) (The reason for comparing squared values is that it eliminates the need to calculate the square root in the distance calculation)[/quote]You can have a set of circles that all mutually intersect, but which still have an empty total intersection.   ;  Thanks for the replies, guys!To start off, I actually did opt for a tile count as I do need the area in a numeric form and doing a tile count is so much more cost-effective if precision isn't a priority (which it isn't for me).quasar3d - yes, I need the surface area, not intersection information, which by itself is trivial to obtain. I'm using the surface area as a metric for map control upon which I'm making several game state decisions. I am having some trouble understanding the last point you mentioned; however, since I won't be implementing it to save time and energy, I won't ask for further clarification. Which isn't to say that if someone is interested in actually solving this problem, the discussion cannot go on . However, I'm not even sure how efficient a truly precise method would be since doing the intersection tests looks pretty daunting once the number of circles hits double or triple figures. At the end of the day I think the best option in a realtime application is still some form of flood-fill to calculate the rough coverage. For more precise results simply cut the map into sections and use higher resolution look-up maps.Since I'm perfectly happy with a 20% error (since this metric is fictional anyway), I'll just be using my existing map granularity to get a very rough estimate instead, especially in lieu of the fact that in worst case situations I might end up doing this up to a few times per second, which is no longer that cheap.   ;  [s]Basic framework for the code. Last two lines not finished. [/s](The big circle is circle 1 and the smaller circle in the example is circle 2).Now the last problem for you to solve is the problem on the bottom right of the image. Given a value x (which is distance1 and distance2 in the algorithm linked) and a radius what is the area of the circular region. Multiply that value by 2 to get the full circle region. If you do this for each circle and add the result that's the value for the total area in the sub-region.I might have made a simple mistake, but that's the basic idea.// edit I did make a mistake with how I calculated distance1 and distance2. It depends on the location of the circles. I drew both scenarios. The bottom left and top images represent two scenarios.In the bottom left distance1 is simply radius1 - (position3 - position1) and distance2 is radius2 - (position3 - position0), but in the case of the top left image it's different and that solution doesn't work.A generic solution that does work for calculating distance1 and distance2 is to create a radius vector pointing to the other circle's center and do:distance1 = ((position2 - position1).Normalize() * radius1 - (position3 - position1)) .Length();distance2 = ((position1 - position2).Normalize() * radius2 - (position3 - position2)) .Length();// edit 2, integral sqrt(r^2 - (x - r)^2) dxSo the area under a semicircle given a range from 0 to x is simply:area = 2 * (2 * r * r * sqrt(x) * sqrt(2 * r - x) * tan^-1(sqrt(x) / sqrt(2 * r - x)) - x * (2 * r * r - 3 * r * x + x * x)) / (2 * sqrt(x * (2 * r - x)));Here is the working code.;Here is a Javascript and Canvas Example Just move the mouse around and the overlapped region is in green with the displayed area.I will point out that you want to be careful with atan and floats. You should be using some kind of epsilon value in places. I'll leave that to you though.   