Determine if two rasterized circles on a grid overlap or intersect

Question

I am interested in determining whether two rasterized circles (e.g. using the Midpoint circle algorithm) intersect. The two circles are defined by a center (x-y coordinate) on the grid, and a radius. For example, a circle with centre (6, 6) and radius 3 is plotted here: https://docs.opencv.org/3.0-beta/_images/fast_speedtest.jpg . Note that points are all on a 2d plane, with centers on the gridlines.

Two circles overlap if there exists at least point (aka pixel) that belongs to both their circumferences. Here is a simple plot showing in black the center of an arbitrary circle along with an arc of its circumference, in red the centres of circles that overlap the black circle, and in green the centres of circles that do not overlap the black circle:

I am trying to determine a formula that, given the definitions for both circles, can determine whether they overlap.

I am particularly only interested in circles of radius 3, although a generalized formula is suitable.

I have tried simply checking that the Manhattan distance between the centre points is greater than the sum of the radii, but that does not seem to work.

Answer 1

In your particular example:

if the two circles have centres $(x_1,y_1)$ and $(x_2,y_2)$ then they seem to overlap if both

• $|x_1-x_2|+|y_1-y_2| \le 8$
• $\max(|x_1-x_2|,|y_1-y_2|) \le 6$

or alternatively, using a version of Euclidean distance, a single test

• $(x_1-x_2)^2+(y_1-y_2)^2 \le 40$

since the points $(0,0)$ and $(2,6)$ seem to lead to an overlap, while the points $(0,0)$ and $(4,5)$ do not

Answer 2

Here's what a heuristic-based answer for radius of 3 might look like.

Let $h$, $v$ be the horizontal and vertical distances between the centres, respectively.

Let $l$, $m$ be the minimum and maximum of $h$ and $v$, respectively.

Then there are four cases:

1. $m \ge 7$

The circles do not overlap.

2. $m = 6$

The circles overlap $\iff$ $l < 3$.

3. $m = 5$

The circles overlap $\iff$ $l < 4$.

4. $m \le 4$

The circles overlap.