Circle areas on squared grid

Question

There is a circle. On 9 equal squares. Every square has some value assigned to it. Every square gets weight, depending of what percentage of it is circle (area-wise). I need to find circle radius, such that sum(weight of square * value of square) = some Y. We know circle center (which is inside the middle square), values of squares and height (width) of square. Circle borders can't exceed these 9 squares.

I need some universal formula so I could implement it using SQL syntax.

Answer 1

Once the weights of your squares are fixed. Your sum turn into a weight sum of the area of intersection of your circle with each of the squares.

The intersection area between a circle and a square can further breakdown and expressed in terms of the area of intersection between a circle with four quadrants. i.e. those set of the form $$(-\infty, u] \times (-\infty,v ] = \big\{\; (x,y) \in \mathbb{R}^2 : x \le u, y \le v \;\big\}$$

Let $C$ be your circle. For any $(u,v) \in \mathbb{R}^2$, let

$$\Delta_C(u,v) = \text{Area}(\;C \cap (-\infty,u] \times (-\infty,v]\;)$$

For any rectangle $[a_1, a_2] \times [b_1,b_2]$, we have following identity:

$$\text{Area}( C \cap [a_1, a_2] \times [b_1, b_2 ] ) = \Delta_C( a_1, b_1 ) - \Delta_C( a_1, b_2 ) - \Delta_C( a_2, b_1 ) + \Delta_C( a_2, b_2 )$$

Assume your circle is centered at $(p,q)$ with radius $r$ and $C_0$ is the unit circle, By translation symmetry and scaling argument, we have $$\Delta_C(a, b) = r^2 \Delta_{C_0}\left(\frac{a-p}{r},\frac{b-q}{r}\right)$$

At the end, we just need to figure out what $\Delta_{C_0}( x, y )$ are. For simplicity of presentation, we will drop the $C_0$ subscript from $\Delta_{C_0}$ from now on.

For any $u \in \mathbb{R}$, let $h(u)$ be the area of intersection between the unit disk $C_0$ with the half plane $(-\infty, u)\times(-\infty,\infty)$. It is not hard to work out

$$h(u) = \Delta(u,\infty) = \begin{cases} \pi,& u \in [1,\infty)\\ \pi - \cos^{-1}(u) + u\sqrt{1-u^2},& u \in (-1,1)\\ 0,& u \in (-\infty, -1] \end{cases}$$

To determine the value of $\Delta(u,v)$, one can use following table.

$$\begin{array}{rcc} \hline \verb/Condition/ && \Delta(u,v)\\ \hline u^2 + v^2 \le 1 && \frac{h(u) + h(v)}{2} - \frac{\pi}{4} + uv\\ u \le -1 \vee v \le -1 && 0\\ u \ge 1 \wedge v \ge 1 && \pi\\ u \ge 1 && h(v)\\ v \ge 1 && h(u)\\ u \ge 0 \wedge v \ge 0 && h(u) + h(v) - \pi\\ u \ge 0 \wedge v \le 0 && h(v)\\ u \le 0 \wedge v \ge 0 && h(u)\\ \verb/otherwise/ && 0\\ \hline \end{array}$$

One look at the conditions in this table one by one. If $(u,v)$ satisfy a condition, then $\Delta(u,v)$ will be given by the expression at the right. If not, move to next condition.

Finally, here is a picture illustrating in which range, one should use which formula for $\Delta(u,v)$.

Answer 2

You can decompose your intersections into circular segments, triangles and rectangles. The exact arrangement of these different shapes depends on where the circle intersects which side of each square. So you'll need a lot of case distinctions. There is nothing really complicated about this, but nevertheless an ugly and boring amount of work. That's the reason I don't go into more detail here.