<p>The first thing to notice is that an $n$-vertex polygon polygon $B$ is inside circle $A$ if and only if all of the vertices of $B$ are inside $A$. (1) </p>

<p>So the solution to your problem is exactly the area of $n$ arbitrary intersecting circles, each of radius $r$ and centered at a vertex of $B$. (You then divide by $S$ to get the final probability).  There's an interesting blog about this problem <a href="http://www.benfrederickson.com/calculating-the-intersection-of-3-or-more-circles/" rel="nofollow noreferrer">here</a> which includes some heuristic solutions which may be sufficient for your use case.  </p>

<p>From a theoretical point of view, the <a href="http://www.cs.wustl.edu/~pless/546/lectures/lecture24.pdf" rel="nofollow noreferrer">furthest-point Voronoi diagram</a> gives us a good starting point.  Let's look at a point $p$ inside a cell of the furthest-point Voronoi diagram.  We want to know if the circle $A$ centered at $p$ contains $B$.  By the above, this happens if and only if all vertices of $B$ are within distance $r$ of $p$.  Now, since we're inside a cell of the furthest-point Voronoi diagram, we can just test whether or not $p$ is within distance $r$ of that furthest point.</p>

<p>In particular, the area we want within a given Voronoi cell is the intersection of that Voronoi cell with a single circle of radius $r$.  This can be easily calculated in time linear in the number of edges of the cell.  Since the furthest-point Voronoi diagram has $O(n)$ cells with $O(n)$ total edges, this takes $O(n)$ time in total.</p>

<p>Then the total running time is dominated by the time to calculate the furthest-point Voronoi diagram, which is $O(n \log n)$. A similar strategy gives you an explicit region $C$ in the same amount of time.</p>

<p>(1): The "only if" direction is obvious.  To see the "if" direction, we can first note that by convexity if all vertices of $B$ are inside $A$, then all edges of $B$ must be as well.  The same argument then extends to all interior points of $B$ since they must lie on a line between two vertices or edges.</p>

CC BY-SA 3.0
2018-02-06T16:03:34.013Z
2018-02-06T16:09:05.377Z
2018-02-06T16:09:05.377Z
SamM
<p>I have two shapes, one is a circle, let's call it Circle A, and another irregularly shaped Polygon B. A will always have a greater area than B. Both of these polygons exist inside an area S.</p>

<p>My task is to compute the inclusion probability of Polygon B in a random sample, where inclusion is defined as Polygon B being entirely inside of Circle A (the circle). </p>

<p>My assumption is that the inclusion probability of Polygon B is the area of another Polygon C, which equates to the area in which Circle A can be placed so that it can enclose Polygon B divided by the total area of S.</p>

<p>If this assumption is correct, then computing Polygon C seems computationally intensive.</p>

<p>Is there an efficient method for finding Polygon C?</p>

CC BY-SA 3.0
2018-02-06T03:57:31.020Z
In what sense is a circle a polygon?
David Eppstein
<computational-geometry>
Inclusion probability of irregularly shaped polygon
Bryce Frank
# Inclusion probability of irregularly shaped polygon

(Asked by: username_0 on 2018-02-06)

I have two shapes, one is a circle, let's call it Circle A, and another irregularly shaped Polygon B. A will always have a greater area than B. Both of these polygons exist inside an area S.

My task is to compute the inclusion probability of Polygon B in a random sample, where inclusion is defined as Polygon B being entirely inside of Circle A (the circle).

My assumption is that the inclusion probability of Polygon B is the area of another Polygon C, which equates to the area in which Circle A can be placed so that it can enclose Polygon B divided by the total area of S.

If this assumption is correct, then computing Polygon C seems computationally intensive.

Is there an efficient method for finding Polygon C?

**Tags:** computational-geometry
> **Comments:**
> **username_1**: In what sense is a circle a polygon?  

---

## 1 answers

### Answer by username_2 on 2018-02-06. Score: 1 | Accepted answer

The first thing to notice is that an $n$-vertex polygon polygon $B$ is inside circle $A$ if and only if all of the vertices of $B$ are inside $A$. (1)

So the solution to your problem is exactly the area of $n$ arbitrary intersecting circles, each of radius $r$ and centered at a vertex of $B$. (You then divide by $S$ to get the final probability). There's an interesting blog about this problem [here](http://www.benfrederickson.com/calculating-the-intersection-of-3-or-more-circles/) which includes some heuristic solutions which may be sufficient for your use case.

From a theoretical point of view, the [furthest-point Voronoi diagram](http://www.cs.wustl.edu/~pless/546/lectures/lecture24.pdf) gives us a good starting point. Let's look at a point $p$ inside a cell of the furthest-point Voronoi diagram. We want to know if the circle $A$ centered at $p$ contains $B$. By the above, this happens if and only if all vertices of $B$ are within distance $r$ of $p$. Now, since we're inside a cell of the furthest-point Voronoi diagram, we can just test whether or not $p$ is within distance $r$ of that furthest point.

In particular, the area we want within a given Voronoi cell is the intersection of that Voronoi cell with a single circle of radius $r$. This can be easily calculated in time linear in the number of edges of the cell. Since the furthest-point Voronoi diagram has $O(n)$ cells with $O(n)$ total edges, this takes $O(n)$ time in total.

Then the total running time is dominated by the time to calculate the furthest-point Voronoi diagram, which is $O(n \log n)$. A similar strategy gives you an explicit region $C$ in the same amount of time.

(1): The "only if" direction is obvious. To see the "if" direction, we can first note that by convexity if all vertices of $B$ are inside $A$, then all edges of $B$ must be as well. The same argument then extends to all interior points of $B$ since they must lie on a line between two vertices or edges.


---

