Algorithm for matching position and size of two rectangles

Question

I'm looking for a algorithm that computes the following: I have an image with a predefined area (the green one on the attached image). The user draws the red rectangle and the algorithm should compute whether the red rectangle matches approximately the green one. For example the position of the red rectangle on the attached picture would be ok.

What is a good way to compute this? Is there any best practice algorithm?

My idea is to compute the middle of the red rectangle and then to determine whether the middle is inside the green rectangle. In addition, I would calculate if the length and height match approximately the length and height of the green one (25% more or less).

Is this a good idea? Any other suggestion?

Answer 1

Investigating the problem, I tend to think about the conditions that should make the comparison of the green and the red rectangles fail, together with reasoning about the failing conditions, separately about each condition.

What I mean above, practically, is that I would like the following responses from the algorithm, making clear what aspect of the comparison fails:

1. Your rectangle's width is way off.
2. Your rectangle's height is way off.
3. Your rectangle's horizontal placement is way off.
4. Your rectangle's vertical placement is way off.

Let us call the conditions above "failing conditions". These failing conditions suggest my view of the comparison, which unavoidably directs my approach. One could view it differently ("Your rectangle's area is way off."). The user, of course, could get more generic responses like the following:

• Your rectangle's dimensions are way off.
• Your rectangle's placement is way off.
• Your rectangle is way off. Try again.
• Dude, are you drunk?

In the following I use green to refer to the green rectangle as an object and red to refer to the red rectangle as an object. All conditions are based on relative errors, that is absolute errors normalized with respect to the actual values, i.e. the values of the green rectangle.

One thing that needs to be specified is what "way off" means for horizontal and vertical placement. It means that there is a divergence between the location of a key point of the green rectangle and the location of the corresponding key point of the red rectangle. Let us choose the center of a rectangle as the key point for comparisons (one could choose the top-left corner of the rectangle).

Another thing that needs to be specified is how you may compare two points in a relative way, separately for each axis. You need a reference value. What you can do is calculate the absolute offset between the two points in each axis. Then you can calculate the relative offset with respect to the green rectangle's corresponding dimension. For instance, you can calculate the relative horizontal offset as the absolute offset between the centers in the x-axis divided by the width of the green rectangle. All in all, for a comparison to succeed, I would like the rectangles to have almost the same dimensions and almost the same center. Where "almost" should be quantified as a percentage.

Concerning failing condition (1), assuming that the maximum allowed relative error for the rectangle's width is 25%, the boolean value that we have to calculate is:

| green.width - red.width | / green.width > 0.25

If the value above is true, then failing condition (1) goes off. The Dude may be drunk. We may exit and notify.

Concerning failing condition (2), assuming that the maximum allowed relative error for the rectangle's height is 30%, the boolean value that we have to calculate is:

| green.height - red.height | / green.height > 0.30

If the value above is true, then failing condition (2) goes off. We may exit and notify.

Concerning failing condition (3), assuming that the maximum allowed relative error for the rectangle's horizontal offset is 15%, the boolean value that we have to calculate is:

| green.center.x - red.center.x | / green.width > 0.15

If the value above is true, then failing condition (3) goes off. We may exit and notify.

Concerning failing condition (4), assuming that the maximum allowed relative error for the rectangle's vertical offset is 20%, the boolean value that we have to calculate is:

| green.center.y - red.center.y | / green.height > 0.20

If the value above is true, then failing condition (4) goes off. We may exit and notify.

If at least one failing condition goes off, then the comparison fails. If no failing condition is true, then the comparison is successful, the green and the red rectangles are almost the same.

I believe that the approach above has a lot of advantages, such as reasoning for separate aspects of the comparison, as well as defining different thresholds for the failing conditions. You can also tune the thresholds according to your taste. In extreme cases more parameters may need to be taken into account, though.

Answer 2

• Take the average distance between vertices as the criteria for mismatch.
• Lets assume first rectangle's vertices are [x1,y1], [x2,y2], [x3,y3], [x4,y4] and for second one are [a1,b1],[a2,b2],[a3,b3],[a4,b4]
• Get euclidiean distance between these points
• Lower distance means better match, e.g exact overlap will give 0, a shape shift or offset shift of any rectangle would increase the average distance of vertices.

Answer 3

Compute the area of the intersection and divide by the average of the areas of the two rectangles (arithmetic or geometric). You will get a fraction. The closer to 1, the better the match.