How to find collision center of two rectangles? Rects can be rotated

Question

I've just implemented collision detection using SAT and this article as reference to my implementation. The detection is working as expected but I need to know where both rectangles are colliding.

I need to find the center of the intersection, the black point on the image above (but I don't have the intersection area neither). I've found some articles about this but they all involve avoiding the overlap or some kind of velocity, I don't need this.

The information I've about the rectangles are the four points that represents them, the upper right, upper left, lower right and lower left coordinates. I'm trying to find an algorithm that can give me the intersection of these points.

I just need to put a image on top of it. Like two cars crashed so I put an image on top of the collision center. Any ideas?

Answer 1

You need to do the intersection of the boundaries of the boxes using the line to line intersection equation/algorithm.

http://en.wikipedia.org/wiki/Line-line_intersection

Once you have the points that cross you might be ok with the average of those points or the center given a particular direction possibly. The middle is a little vague in the question.

Edit: also in addition to this you need to work out if any of the corners of either of the two rectangles are inside the other (this should be easy enough to work out, even from the intersections). This should be added in with the intersections when calculating the "average" center point.

Answer 2

There is another way of doing this: finding the center of mass of the collision area by sampling points.

Create the following function:

bool IsPointInsideRectangle(Rectangle r, Point p);

Define a search rectangle as:

TopLeft = (MIN(x), MAX(y))
TopRight = (MAX(x), MAX(y))
LowerLeft = (MIN(x), MIN(y))
LowerRight = (MAX(x), MIN(y))

Where x and y are the coordinates of both rectangles.

You will now define a step for dividing the search area like a mesh. I suggest you use AVG(W,H)/2 where W and H are the width and height of the search area.

Then, you iterate on the mesh points finding for each one if it is inside the collition area:

IsPointInsideRectangle(rectangle1, point) AND IsPointInsideRectangle(rectangle2, point) 

Define:

Xi : the ith partition of the mesh in X axis.
CXi: the count of mesh points that are inside the collision area for Xi.

Then:

And you can do the same thing with Y off course. Here is an ilustrative example of this approach:

Answer 3

This one's tricky because irregular polygons have no defined center. Since your polygons are (in the case of rectangles) guaranteed to be convex, you can probably find the corners of the polygon that comprises the collision (which can include corners of the original shapes or intersections of the edges) and average them to get ... something. It will probably be vaguely close to where you would expect the "center" to be, and for regular polygons it would probably match exactly, but whether it would mean anything mathematically is a bit of a different story.

I've been fiddling mathematically and come up with the following, which solves the smoothness problem when points appear and disappear (as can happen when the movement of a hitbox causes a rectangle to become a triangle or vice versa). Without this bit of extra, adding and removing corners will cause the centroid to jump.

Here, take this fooplot.

The plot illustrates 2 rectangles, R and B (for Red and Blue). The intersection sweeps out an area G (for Green). The Unweighted and Weighted Centers (both Purple) are calculated via the following methods:

(0.225, -0.45):   Average of corners of G
(0.2077, -0.473): Average of weighted corners of G

A weighted corner of a polygon is defined as the coordinates of the corner, weighted by the sin of the angle of the corner.

This polygon has two 90 degree angles, one 59.03 degree angle, and one 120.96 degree angle. (Both of the non-right angles have the same sine, sin(Ɵ) = 0.8574929...

The coordinates of the weighted center are thus:

( (sin(Ɵ) * (0.3 + 0.6) + 1 - 1)   / (2 + 2 * sin(Ɵ)),  // x
  (sin(Ɵ) * (1.3 - 1.6) + 0 - 1.5) / (2 + 2 * sin(Ɵ)) ) // y
= (0.2077, -0.473)

With the provided example, the difference isn't very noticeable, but if the 4gon were much closer to a 3gon, there would be a significant deviation.

Answer 4

If you don't need to know the actual coordinates of the region, you could make two CALayers whose frames are the rectangles, and use one to mask the other. Then, if you set an image in the one being masked, it will only show up in the area where they overlap.