Finding all points common to two circles

In Python, how would one find all integer points common to two circles?

For example,开发者_C百科 imagine a Venn diagram-like intersection of two (equally sized) circles, with center-points (x1,y1) and (x2,y2) and radii r1=r2. Additionally, we already know the two points of intersection of the circles are (xi1,yi1) and (xi2,yi2).

How would one generate a list of all points (x,y) contained in both circles in an efficient manner? That is, it would be simple to draw a box containing the intersections and iterate through it, checking if a given point is within both circles, but is there a better way?

Keep in mind that there are four cases here.

1. Neither circle intersects, meaning the "common area" is empty.
2. One circle resides entirely within the other, meaning the "common area" is the smaller/interior circle. Also note that a degenerate case of this is if they are the same concentric circle, which would have to be the case given the criteria that they are equal-diameter circles that you specified.
3. The two circles touch at one intersection point.
4. The "general" case where there are going to be two intersection points. From there, you have two arcs that define the enclosed area. In that case, the box-drawing method could work for now, I'm not sure there's a more efficient method for determining what is contained by the intersection. Do note, however, if you're just interested in the area, there is a formula for that.

You may also want to look into the various clipping algorithms used in graphics development. I have used clipping algorithms to solve alot of problems similar to what you are asking here.

If the locations and radii of your circles can vary with a granularity less than your grid, then you'll be checking a bunch of points anyway.

You can minimize the number of points you check by defining the search area appropriately. It has a width equal to the distance between the points of intersection, and a height equal to

r1 + r2 - D

with D being the separation of the two centers. Note that this rectangle in general is not aligned with the X and Y axes. (This also gives you a test as to whether the two circles intersect!)

Actually, you'd only need to check half of these points. If the radii are the same, you'd only need to check a quarter of them. The symmetry of the problem helps you there.

You're almost there. Iterating over the points in the box should be fairly good, but you can do better if for the second coordinate you iterate directly between the limits.

Say you iterate along the x axis first, then for the y axis, instead of iterating between bounding box coords figure out where each circle intersects the x line, more specifically you are interested in the y coordinate of the intersection points, and iterate between those (pay attention to rounding)

When you do this, because you already know you are inside the circles you can skip the checks entirely. If you have a lot of points then you skip a lot of checks and you might get some performance improvements.

As an additional improvement you can pick the x axis or the y axis to minimize the number of times you need to compute intersection points.

So you want to find the lattice points that are inside both circles?

The method you suggested of drawing a box and iterating through all the points in the box seems the simplest to me. It will probably be efficient, as long as the number of points in the box is comparable to the number of points in the intersection.

And even if it isn't as efficient as possible, you shouldn't try to optimize it until you have a good reason to believe it's a real bottleneck.

I assume by "all points" you mean "all pixels". Suppose your display is NX by NY pixels. Have two arrays

int x0[NY], x1[NY]; initially full of -1.

The intersection is lozenge-shaped, between two curves. Iterate x,y values along each curve. At each y value (that is, where the curve crosses y + 0.5), store the x value in the array. If x0[y] is -1, store it in x0, else store it in x1.

Also keep track of the lowest and highest values of y.

When you are done, just iterate over the y values, and at each y, iterate over the x values between x0 and x1, that is, for (ix = x0[iy]; ix < x1[iy]; ix++) (or the reverse).

It's important to understand that pixels are not the points where x and y are integers. Rather pixels are the little squares between the grid lines. This will prevent you from having edge-case problems.