Radius of a circle yielding the largest IntersectionOverUnion (IoU) with a unit square

Question

There is a unit square with coordinates ((0,0), (1,1)). I need to find a radius of a circle with a center at (0.5, 0.5) such that the IoU of the circle and the unit square is at maximum. What is the maximal IoU?

I can approximate it numerically (this is sufficient for the job), but what is the right way to do it analytically?

---

Update

show your work

Once again. For my work it is sufficient to find a numerical estimate. Here is how you can do it. We should start with a good rational approximation of sqrt(2). We can use 577/408 ~ sqrt(2)

import numpy as np

eps = 1e-10
center = 577
square_half_size = 408
square = np.zeros((center*2, center*2))
square[center-square_half_size:center+square_half_size, center-square_half_size:center+square_half_size] = 1


def iou(c):
    overlap = c * square
    union = (c + square).clip(0,1)
    return np.sum(overlap)/(np.sum(union) + eps)


best_iou = 0

for i in range(center - square_half_size, center):
    c1 = np.zeros((center*2, center*2))
    for h in range(center*2):
        for w in range(center*2):
            if (center-h)**2 + (center-w)**2 < i**2:
                c1[h,w] = 1

    current_iou = iou(c1)
    if current_iou > best_iou:
        best_iou = current_iou
        print(i, best_iou)

One can use binary search to accelerate the computation. This approach works: I only need the result to two digit accuracy. But I want to go an extra mile to see, how to approach these tasks analytically.

---

Update: r = 0.549468, IoU = 0.8370325 when using another good approximation of sqrt(2) 8119/5741

center = 8119
square_half_size = 5741

Takes about 12 hours to compute. Grid refinement (binary search) would speed up the computation drastically.

Answer 1

Let $O$ be the center of the square that we will take as the origin of coordinates. For symmetry reasons, it is sufficient to work on the $1/8$ part of the square, represented by right isosceles triangle AOB in the equivalent square $[0,1/2] \times [0,1/2]$ as shown below :

It is clear that

• if $r \le OA=\frac12$ : IoU=$\pi r^2 \le \frac{\pi}{4}<0.7854 ;$

• if $r \ge OB=\frac{\sqrt{2}}{2}$ : IoU= $\frac{1}{\pi r^2} \le \frac{2}{\pi}<0.6366.$

• But, for $\frac12 < r < \frac{\sqrt{2}}{2}$, we are going to show that the IoU value can be made larger than the bounds established above, with maximum value given by (3).

For this range of values ($\tfrac12 < r < \frac{\sqrt{2}}{2}$) where the circle intersects the square's border in a point $C$, the ratio IoU can be expressed in terms of angle $\alpha := \angle AOC$ :

$$IoU(\alpha)=\frac{\tfrac{\pi}{4}-\alpha+\sin(\alpha)\cos(\alpha)}{\alpha+(\cos(\alpha)-\sin(\alpha))\cos(\alpha)}$$

(see explanations below.)

This function has indeed a maximum for a certain $\alpha = \alpha_0$ which is found by equating its derivative to zero which is equivalent to equation :

$$\pi(\cos(2 \alpha) + \sin (2\alpha)-1)=4 \alpha \sin 2\alpha \tag{1}$$

whose solution in the domain $0<\alpha < \pi/4$ is

$$\alpha_0 \approx 0.427536 \ \text{radians}$$

giving the following value of $r_0$:

$$r_0=\frac{1}{2\cos(\alpha_0)}\approx 0.549457\tag{2}$$

for which IoU is maximal with max. value $$IoU_{max}=0.83703 \tag{3}.$$

Explanations :

$$IoU=\frac{[COD]+[AOC]}{[EOC]+[COB]}$$

with

• (area of) triangle $[AOC]$ = $\frac12 r^2\cos \alpha \sin \alpha.$

• (area of) triangle $[COB]$ = $\frac12 \frac{\sqrt{2}}{2} r \cos \beta.$

• (area of circ. sector) $[EOC]$ = $\frac12 \alpha r^2.$

• (area of circ. sector) $[COD]$ = $\frac12 \beta r^2.$

with $\beta=\frac{\pi}{4}-\alpha$ and $r \cos \alpha = \frac12$.

Remarks :

1. Using "half-angle formulas" (see below), $(1)$ can be transformed into a simpler equation :

$$\tan\left(\tfrac{\pi}{4}(1-t)\right)=t \tag{4}$$

where $t:=\tan(\alpha)$ and $\sin(2\alpha)=\tfrac{2t}{1+t^2}, \cos(2\alpha)=\tfrac{1-t^2}{1+t^2}$

The solution of (4) is $t=0.455643162...$

which gives value $\alpha=\operatorname{atan}(t)=0.42753686...$ as awaited.

2. It is known that egyptians were approximating the area of a disk by the area of a square (they didn't have a concept equivalent to our $\pi$) ; in our case, the radius of a disk having the same area as a square with area $1$ should be :

$$\frac{1}{\sqrt{\pi}}\approx 0.56419,$$

which is not very far from value (3)...