views:

327

answers:

5

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

For example, 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?

A: 

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.

mathmike
Yes, lattice points would be more appropriate terminology - let's go with "the rectangular lattice points which lie in two intersecting circles".Although it's not a bottleneck, per se, this function is being repeated at a considerable order of magnitude. The number of points it would exclude would be significant.
Dustin I.
A: 

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.
Daniel DiPaolo
It's quite clear from the question that only the 4th case applies
SilentGhost
The stated assumptions imply it, but what's wrong with listing other possibilities that may have failed to be considered?
Daniel DiPaolo
*Additionally, we already know the two points of intersection of the circles are `(xi1,yi1)` and `(xi2,yi2)`.* How is this can be considered *implying*?
SilentGhost
Thanks! I am only interested in case #4. The area is unimportant -- the list of points is what I'm after.
Dustin I.
Not meant to imply anything about the OP's coding skills, but it's always possible to plug numbers into a formula that have no business being plugged into that formula. The existence of values for xi1, yi1, xi2, and yi2 is independent of the values actually meaning anything. To ensure that they mean something, Daniel's checks need to be made first. Never hurts to clairfy that.
John at CashCommons
@SilentGhost And what if whatever process returns those points returns `(None, None)` (either for one point or both) because it's case #1 or #3? There's nothing wrong with covering your bases and verifying stated assumptions.
Daniel DiPaolo
All points are valid, but let's just assume I've already done the appropriate sanity checks. :)
Dustin I.
A: 

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.

Rob Goodwin
+1  A: 

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.

John at CashCommons
Correct, however this `w X h` rectangle is the "box" I'm trying to avoid using. I do like your idea of using symmetry though, it hadn't occurred to me.
Dustin I.
A: 

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.

Mike Dunlavey