Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If your problem was just for pairs of circles, you'll use the known result about <a href="http://mathworld.wolfram.com/Circle-CircleIntersection.html" rel="nofollow">Circle-Circle intersection areas</a>. The formula for the pairwise area between any two circles, based on a standard parameterization of all circles involved, is given there. But as <code>n</code> gets large, the formulas for these areas are not commonly known. There might be a clever way to use recursion to compute the formulas for the intersection of two circles (<code>n=2</code>), the intersection of two asymmetric lens shapes (<code>n=3</code>), the intersection of two instances of whatever shape is the intersection of two asymmetric lens shapes (<code>n=4</code>), and so on. If you can derive formulas for those areas, you can always use <a href="http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle" rel="nofollow">inclusion-exclusion</a> to figure out the intersection. The key insight is that the intersection of <code>n</code> instances of the previous shape is really the intersection of <code>n-1</code> instances of intersections-of-previous-shape. But like the commenter above has said, that question really belongs at Math Overflow.</p> <p><strong>Practical Aside</strong></p> <p>For anyone reading who is interested in a practical way to solve this problem, Monte Carlo integration is an excellent choice. All you need to do is compute a large rectangle that bounds all of the circles, and then draw points uniformly in that rectangle. For each circle, check if the point is inside or outside. If it is ever inside, then increment a counter and break out of doing any more checks. At the end, the proportion of that counter to the total points drawn, multiplied by the area of the rectangle, will give the area.</p> <p>If we assume that for each <code>n</code>-wise intersection area, we need to do <code>n</code> different <code>O(1)</code> steps (assuming we get an analytical formula that we can just plug the radii and center data straight into, which might be optimistic), then this analytical method is still <code>O(n^2)</code>.</p> <p>Monte Carlo is worse, <code>O(Mn)</code> where <code>M</code> is the number of points we draw, if we make the pessimistic assumption that we have to check against all <code>n</code> circles for every point. For moderate <code>n</code>, while <code>M</code> won't need to be intractably large, it certainly won't be close to <code>n</code>. However, we get the added benefit that our function automatically generalizes to the case of mixed radii (for which the general solution is much harder). From a practitioner's point of view, the analytical solution here is not very useful unless the circles barely overlap and the bounding rectangle contains a large amount of empty space.</p>
    singulars
    1. This table or related slice is empty.
    1. POArea of Union of n circles(MATLAB code)
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USely
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POArea of Union of n circles(MATLAB code)
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload