Algorithm for comparing the position and size of two rectangles

I am looking for an algorithm that calculates the following: I have an image with a predefined area (green on the attached image). The user draws a red rectangle, and the algorithm must calculate whether the red rectangle is approximately green. For example, the position of the red rectangle in the attached image will be in order.

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

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

Is that a good idea? Any other suggestion?

enter image description here

+5
source share
3 answers

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

+11
source
  • Take the average distance between the vertices as a criterion for the mismatch.
  • Suppose that the first rectangular vertices are [x1,y1], [x2,y2], [x3,y3], [x4,y4] , and for the second - [a1,b1],[a2,b2],[a3,b3],[a4,b4]
  • Get the Euclidean distance between these points
  • A lower distance means a better match, for example an exact match will give 0, a shape shift or offset of any rectangle will increase the average distance of the vertices.

enter image description here

+1
source

Studying the problem, I am inclined to think about conditions that should lead to the fact that the comparison of green and red rectangles does not work, and the discussion of unsuccessful conditions, separately about each condition.

What I mean above, in practice, is that I would like to get the following answers from the algorithm, clearly defining which aspect of the comparison fails:

  • Your rectangle width is disabled.
  • The height of your rectangle is disabled.
  • Your horizontal placement of the rectangle is disabled.
  • Your vertical placement of the rectangle does not work.

Let us call the conditions above “unsuccessful conditions”. These unsuccessful conditions testify to my view of comparison, which inevitably guides my approach. You could view it in different ways ("Your rectangle area is off"). The user, of course, could get more general answers, such as:

  • Your rectangle sizes go away.
  • Your rectangle layout does not work.
  • Your rectangle is off. Try again.
  • Dude, are you drunk?

In what follows, I use green to indicate a green rectangle as an object and red to indicate a red rectangle as an object. All conditions are based on relative errors, which are absolute errors, normalized with respect to actual values, i.e. Values ​​of the green rectangle.

One thing that needs to be indicated is what “exit” means for horizontal and vertical placement. This means that there is a discrepancy between the location of the key point of the green rectangle and the location of the corresponding key point of the red rectangle. Select the center of the rectangle as the key point for comparison (you can select the upper left corner of the rectangle).

Another thing that needs to be pointed out is how you can compare two points relative to each other, separately for each axis. You need a reference value. What you can do is calculate the absolute offset between the two points of each axis. Then you can calculate the relative offset relative to the green rectangle corresponding to the size. For example, you can calculate the relative horizontal offset as the absolute offset between the centers along the x axis, divided by the width of the green rectangle. In general, for comparison, in order to succeed, I would like the rectangles to be almost the same size and almost the same center. Where "almost" should be quantified as a percentage.

As for the failure condition (1), assuming that the maximum allowable relative error for the width of the rectangle is 25%, the Boolean value that we must calculate is:

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

If the value is higher than true , the failure condition (1) is disabled. Dude may be drunk. We can go out and notify.

Regarding the failure condition (2), assuming that the maximum allowable relative error for the height of the rectangle is 30%, the logical value that we must calculate is as follows:

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

If the value is higher than true , then the failure condition (2) is disabled. We can go out and notify.

Regarding the failure condition (3), assuming that the maximum permissible relative error for the horizontal offset of the rectangle is 15%, the logical value that we must calculate is the following:

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

If the value is higher than true , then the failure condition (3) is disabled. We can go out and notify.

Regarding the failure condition (4), assuming that the maximum permissible relative error for the vertical displacement of the rectangle is 20%, the logical value that we must calculate is the following:

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

If the value is higher than true , then the failure condition (4) is disabled. We can go out and notify.

If at least one failure condition is disabled, the comparison is not performed. If the failure condition is not true , the comparison is successful, the green and red rectangles are almost the same.

I believe that the above approach has many advantages, such as argumentation for individual aspects of the comparison, as well as the definition of different threshold values ​​for unsuccessful conditions. You can also adjust the thresholds to suit your taste. In extreme cases, it may be necessary to consider a larger number of parameters.

+1
source

All Articles