# Circle areas on squared grid

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.

-
Have you tried this with a square instead of a circle? That is probably easier to think about and give you insight into the syntax issues. – Paul Jun 7 '14 at 13:31
To achieve my goal i need circle – user2820173 Jun 7 '14 at 14:41
There isn't going to be some simple universal formula, and to further require it in SQL will be horrendous. Maybe if you know the 9 numbers are always consistent with an actual solution, there might be a simple(r) answer. The problem is also ill-posed since there generally won't (numerically) be a unique solution. – Victor Liu Jun 10 '14 at 19:11
Victor is spot-on. This is the sort of problem I'd solve only for paid consulting money, because it's messy and yet not likely to be interesting. One small idea: if you draw axes through the center of the circle, you divide the middle column into two columns, and the same for the middle row, so you now have a 4x4 grid of not-quite-squares, but ones that'll make your integrations nicer. 2nd small idea: you can probably do an inclusion-exclusion trick to alter the square-values so that all integrals are either half-space or quadrant integrals, making the thing a bit more reasonable. – John Hughes Jun 10 '14 at 19:18

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)$.

-

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.

-