0
$\begingroup$

This answer really nicely sums up the question of how to compute the number of pixels inside an inscribed circle. However, I am looking for a more generalized version of this in two ways.

1) I would like to be able to compute this to handle arbitrary centers (i.e. not the center of a pixel or right on the intersection of 4 pixels)

2) To generalize this to an axis-aligned ellipse inscribed in a $d_h \times d_w$ rectangle. That is an ellipse that is symmetric across the y-axis and across the x-axis.

How do I finish the derivation for the odd-number diameter case for circles at an arbitrary center below, and how might I extend this to an inscribed ellipse?


For the matter of arbitrary centers for circles, I believe I have the start below just by slightly modifying the derivation from the linked answer (for a $d \times d$ inscribing square with decimal offsets from the centers given by $(\mu_x, \mu_y)$):

Case I - $d = 2\ell + 1$ is odd.

When $d$ is odd, the center of the inscribed circle coincides with the center of one of the unit squares. The centers of the unit squares lie on an integer lattice and the number we want is

$$\mathcal{N}_{odd}(d) = \left| \left\{\; (x,y) \in \mathbb{Z}^2 : > \sqrt{ x^2 + y^2 } \le \frac{d}{2} \;\right\}\right|$$

$$\mathcal{N}_{odd}(d) = \left| \left\{\; (x,y) \in \mathbb{Z}^2, (\mu_x \mu_y) \in \mathbb{R}^2 : \sqrt{ (x - \mu_x)^2 + (y-\mu_y)^2 } \le \frac{d}{2} \;\right\}\right|$$

Notice the lattice points inside the inscribed circle has a $4$-fold rotational symmetry with respect to the center of $d\times d$ square. This give us $$\begin{align} \mathcal{N}_{odd}(d) &= 1 + 4 \left|\left\{ (x,y) \in \mathbb{Z}^2 : \sqrt{ x^2 + y^2 } \le \frac{d}{2}, x \ge 0, y > 0 \;\right\}\right|\\ &= 1 + 4 \sum_{y=1}^\ell \left|\left\{ x \in \mathbb{Z} : \sqrt{ x^2 + y^2 } \le \frac{d}{2}, x \ge 0 \;\right\}\right| \end{align} $$

$$\begin{align} \mathcal{N}_{odd}(d) &= 1 + 4 \left|\left\{ (x,y) \in \mathbb{Z}^2, (\mu_x \mu_y) \in \mathbb{R}^2 : \sqrt{ (x-\mu_x)^2 + (y-\mu_y)^2 } \le \frac{d}{2}, x \ge 0, y > 0 \;\right\}\right| \\ &= 1 + 4 \sum_{y=1}^\ell \left|\left\{ x \in \mathbb{Z}, (\mu_x \mu_y) \in \mathbb{R}^2 : \sqrt{ (x-\mu_x)^2 + (y-\mu_y)^2 } \le \frac{d}{2}, x \ge 0 \;\right\}\right| \end{align} $$

Although I'm not really sure how to make the leap parallel to this last reduction (I don't understand where the $1$ inside the floor function comes from):

$$ N_{odd}(d) = 1 + 4 \sum_{y=1}^\ell \left\lfloor 1 + \sqrt{\left(\frac{d}{2}\right)^2 - y^2} \right\rfloor $$

For the even case, it seems to follow that we simply replace the $\frac12$ with the decimal offsets:

Case II - $d = 2\ell$ is even.

When $d$ is even, the center of the inscribed circle coincides with the common corner of 4 unit squares. If we choose a coordinate system such that this center is the origin, the centers of the unit squares nows lies on an "half-integer" lattice. ...

One again, the lattice points inside the inscribed circle has a 4-fold rotation symmetry. This leads to $$\begin{align} \mathcal{N}_{even}(d) &= 4\left|\left\{\; (x,y) \in \mathbb{Z}_h^2 : \sqrt{x^2+y^2} \le \frac{d}{2}, x > 0, y > 0\;\right\}\right|\\ &=4\sum_{y=1}^\ell \left|\left\{\; x \in \mathbb{Z} : \sqrt{(x-\frac12)^2+(y-\frac12)^2} \le \frac{d}{2}, x > 0\;\right\}\right|\\ &= 4\sum_{y=1}^\ell \left\lfloor\frac12 + \sqrt{\left(\frac{d}{2}\right)^2 - \left(y-\frac12\right)^2}\right\rfloor \end{align} $$

$$\begin{align} \mathcal{N}_{even}(d) &= 4\left|\left\{\; (x,y) \in \mathbb{Z}_h^2, (\mu_x \mu_y) \in \mathbb{R}^2 : \sqrt{x^2+y^2} \le \frac{d}{2}, x > 0, y > 0\;\right\}\right|\\ &=4\sum_{y=1}^\ell \left|\left\{\; x \in \mathbb{Z},(\mu_x \mu_y) \in \mathbb{R}^2 : \sqrt{(x-\mu_x)^2 + (y-\mu_y)^2} \le \frac{d}{2}, x > 0\;\right\}\right|\\ &= 4\sum_{y=1}^\ell \left\lfloor\mu_x + \sqrt{\left(\frac{d}{2}\right)^2 - \left(y-\mu_y\right)^2}\right\rfloor \end{align} $$

$\endgroup$
  • 1
    $\begingroup$ There is an infinite number of different ellipses that can be inscribed in a given rectangle. $\endgroup$ – amd Jan 21 at 23:21
  • $\begingroup$ @amd: How is that the case? Wouldn't it be so that only one skew along the $x$ axis will result in the correct width and only one skew along the $y$ axis will result in the correct height? Isn't the general formula defined by $\frac{(x-\mu_x)^2}{a^2} + \frac{(y-\mu_y)^2}{b^2} = 1$? $\endgroup$ – marcman Jan 21 at 23:25
  • $\begingroup$ @amd: Ahh I think I see--the issue is one of alignment. I'll edit the question to refer specifically to an axis-aligned ellipse. $\endgroup$ – marcman Jan 21 at 23:30
  • $\begingroup$ You’ve got it. Note that in general, even nailing down the axis directions might not be enough. For example, there’s an infinite number of ellipses that can be inscribed in the unit square whose axes are the square’s diagonals. There are five degrees of freedom, so center and two independent tangent points with the tangent directions would suffice. $\endgroup$ – amd Jan 21 at 23:41
  • 1
    $\begingroup$ As long as the rectangle is also axis-aligned :) Under those conditions, the problem’s equivalent to the circle one with non-square pixels. $\endgroup$ – amd Jan 22 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.