Find the midpoint of overlap between circle and rectangle
I'm working on a small game geometry library, and among a bunch of other methods, I want to be able to find the midpoint of intersection between a circle and a rectangle. However, I'm having difficulty thinking of a fast algorithm to do so. Does anyone know of a good algorithm to do this?
I'm willing to sacrifice perfect accuracy if it means the algorithm will be significantly faster.
The basic way I represent each shape is:
Circle :
Rectangle :
EDIT:
Since there seems to be confusion over what I mean by "midpoint," let me clarify:
Given that the circle and the rectangle intersect, there is an area created by their overlap. I wish to determine the geographic center of this area (either exactly, or to determine a close approximate).
Example: http://en.wikipedia.org/wiki/Centroid
EDIT #2:
You guys have given me some ideas, let me work on implementing some of them and I'll get back to you.
Closing Thoughts:
I marked Gareth's answer as the accepted one, because it gave me the ideas for what I ended up going with, but my final implementation is different that his, so I'll explain it here.
I came up with two general ways of doing this: one that would have been completely accurate (but required more complex programming and more math), and another, simpler/faster way that was fairly close all the time. I ended up going with the latter, but here are the two methods:
Method 1: Shape Fragmentation:
Basically, the idea is to break up the overlapping area into discrete segments that can have their midpoint and area be easily computed, and then take the weighted average for the entire result.
The example shown here had three sub-pieces: A center rectangle taking up the bulk of the area, and two curved segments for the edges of the circle.
Method 2: Line Interpolation
First off, you need to calculate a point in the rectangle which will be the base location. This should be a point that is easy to calculate and is in the overlap. What I use for this point is the average of all edge intersections of the circle and the rectangle (if no edge intersections exist, I default to the location of the circle as it means one shape is contained within the other).
Ccalculate the line between the center of the circle and that point. Then, calculate the segment that lies within the overlapping area. The midpoint of the area is taken to be the midpoint of that line segment.
This method is inaccurate, but always produces a point within both objects, and the resulting point is generally close to the middle (so it "looks" good to the casual eye). It's also far simpler and faster, so I went with it.
If you're happy with an approximation, try sampling. Divide the rectangle into some number of squares, and for each square estimate if it is mostly inside the circle (perhaps just by testing if its center is inside the circle).
Then apply the centroid formula,
The centroid of a plane figure can be computed by dividing it into a finite number of simpler figures, computing the centroid Ci and area Ai of each part, and then computing Σ Ci Ai / Σ Ai.
which is particularly simple in this case because the centroid of a square is its centre, and all the Ai are equal.
(Geometric dissection as suggested by Vaughn Cato will get the exact answer, but this approximate method has the advantage of simplicity: it will be much harder to program it incorrectly.)
CodeBunny asks in comments for a "simpler, equation-based result". Here's how to compute the result using equations, but I don't think it's "simpler".
First, you have to determine which geometric case you're in, by intersecting the circle with each edge of the rectangle and counting the number of intersections. That leaves you, I believe, with one of the following fourteen cases:
Then for each case you dissect the intersection into a sum of circular segments and convex polygons. Compute the area and centroid for each of these (see Wikipedia for the formulae: area and centroid of circular segment; area and centroid of convex polygon) and combine them using the centroid formula I gave above.
This is by no means simple: enumeration of geometric cases is tricky (I could very easily have missed a case or two: on my first attempt I only spotted eleven of the cases), and programming the computations is delicate (it's easy to make a mistake in just one of the cases and not notice).
One way is to break it into cases:
Then, find the centroid in each case. For example, in the third case, the intersection is a circular segment, and you can find the centroid of that using a standard formula. In the fourth case, you will end up with a triangle and a circular segment. You can find the centroid of the combined area by multiplying the area of each piece by its respective centroid and then dividing by the total area.
If I understand your requirement correctly you wish to find the centre of the area where two shapes overlap?
Is that correct?
There is a circle with centre (x,y) and radius r. There is a rectangle with centre (x,y), width w and height h
So here is the first gap:
You cannot define a rectangle in an x,y plane with it's centre point and width and height only. Which direction is the rectangle facing?
The equation of a circle as described above is (xa)^2 + (yb)^2=r^2
It is possible to solve this equation simultaneously with an equation for a line to get the points of intersection.
Second gap:
A line may intersect a circle at 2 points, one point or no points - do you know for sure that the circle and rectangle will always overlap so there are two points of the line intersecting the circle?
Assuming yes, it shouldn't be too difficult from this point (having found the two points of intersection) to calculate the midpoint between the points of intersection and then the mid-point of the line drawn at the perpendicular to that midpoint to the edge of the circle (the midpoint of the area of intersection of the shapes)
This isn't by any means a 'this is the answer' answer, but I hope this helps a little?
Steve
链接地址: http://www.djcxy.com/p/84982.html上一篇: 蟒蛇圈周围的多边形区域，周长和边长
下一篇: 找到圆和矩形之间重叠的中点