Update rotatedRectangleIntersection function to calculate near to origin #19842

gasparitiago · 2021-04-02T14:35:54Z

This commit changes the rotatedRectangleIntersection function in order to calculate the intersection of two rectangles considering that they are shifted near the coordinates origin (0, 0).

This commit solves the problem in some assertions from rotatedRectangleIntersection when dealing with rectangles far from origin.

Original issue: #19824

Pull Request Readiness Checklist

See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request

I agree to contribute to the project under Apache 2 License.
To the best of my knowledge, the proposed patch is not based on a code under GPL or other license that is incompatible with OpenCV
The PR is proposed to proper branch
There is reference to original bug report and related work
There is accuracy test, performance test and test data in opencv_extra repository, if applicable
Patch to opencv_extra has the same branch name.
The feature is well documented and sample code can be built with the project CMake

force_builders=linux,docs

In the function that sets the points of a RotatedRect, the types should be double in order to keep the precision when dealing with RotatedRects that are defined far from the origin. This commit solves the problem in some assertions from rotatedRectangleIntersection when dealing with rectangles far from origin.

crackwitz · 2021-04-03T11:29:04Z

does this actually make a difference? it only applies double precision to the calculation itself but the result is still just FP32.

the demo code uses values like 4002326. there is simply not enough precision to go around (6-7 digits).

>>> [cx, cy, w, h, angle] = np.float32([ 246805.033  , 4002326.94   ,      26.40587,       6.20026,     -62.10156])
>>> _angle = angle * pi / 180
>>> a = np.sin(_angle)*0.5
>>> b = np.cos(_angle)*0.5
>>> f = np.float32; cx - f(a)*h - f(b)*w; cy + f(b)*h - f(a)*w
246801.6
4002340.2
>>> f = np.float64; cx - f(a)*h - f(b)*w; cy + f(b)*h - f(a)*w
246801.59334828143
4002340.119037186

gasparitiago · 2021-04-03T13:28:27Z

@crackwitz

does this actually make a difference?

Yes. When testing the code provided by @jbwintergest here: #19824:

import cv2 as cv
import numpy as np
def box(box):
    return ((box[0], box[1]), (box[2], box[3]), box[4])
box_1 = np.array([ 246805.033  , 4002326.94   ,      26.40587,       6.20026,     -62.10156])
box_2 = np.array([ 246805.122  , 4002326.59   ,      27.4821 ,       8.5361 ,     -56.33761])
try:
    print(cv.rotatedRectangleIntersection(box(box_1), box(box_2)))  # Assertion error
except Exception as e:
    print(e)
offset = (246805, 4002326, 0, 0, 0)
box_1 -= offset
box_2 -= offset
print(cv.rotatedRectangleIntersection(box(box_1), box(box_2)))  # that works

when the function rotatedRectangleIntersection, creates the pts1 and pts2 arrays and populate them, like this:

    Point2f pts1[4], pts2[4];
    ...
    rect1.points(pts1);
    rect2.points(pts2);

This is the content of rect1, rect2, pts1[0] and pts2[0] before and after this commit:

Before:

rect1.center.x
246805.03125
rect1.center.y
4002327
rect1.size.width
26.405870437622070312
rect1.size.height
6.200260162353515625
rect1.angle
-62.101558685302734375
rect2.center.x
246805.125
rect2.center.y
4002326.5
rect2.size.width
27.482099533081054688
rect2.size.height
8.5361003875732421875
rect2.angle
-56.33760833740234375
pts1[0].x pts1[0].y
246801.59375 4002340
pts2[0].x pts2[0].y
246801.0625 4002340.25

After:

rect1.center.x
246805.03125
rect1.center.y
4002327
rect1.size.width
26.405870437622070312
rect1.size.height
6.200260162353515625
rect1.angle
-62.101558685302734375
rect2.center.x
246805.125
rect2.center.y
4002326.5
rect2.size.width
27.482099533081054688
rect2.size.height
8.5361003875732421875
rect2.angle
-56.33760833740234375
pts1[0].x pts1[0].y
246801.59375 4002340.25
pts2[0].x pts2[0].y
246801.0625 4002340.25

When the function rotatedRectangleIntersection code considers if two points are the same or not, points that are too far away from the origin (high x or y) are considered overlapped in the before code.

crackwitz · 2021-04-03T13:53:15Z

the only difference between your two texts is that pts1[0].y is completely integer in the first and has a .25 decimal part in the second:

the algorithm itself will likely need fixes, not just the Rect::points() method

asenyaev · 2021-04-08T13:48:48Z

jenkins cn please retry a build

vpisarev · 2021-06-06T17:42:37Z

@gasparitiago, thank you for the contribution! I wonder if you could also modify rotatedRectangleIntersection function to shift intersected rectangles closer to the coordinate origin (and then shift the intersection back)? This way we will get much more robust algorithm

gasparitiago · 2021-06-06T18:36:26Z

Hello @vpisarev, I'm doing it. When I finish I will update this PR and let you know.

To be honest I will need some help on how to test the solution.

gasparitiago · 2021-06-06T20:11:21Z

@vpisarev can you take a look at my last commit?

modules/imgproc/src/intersection.cpp

This commit changes the rotatedRectangleIntersection function in order to calculate the intersection of two rectangles considering that they are shifted near the coordinates origin (0, 0). This commit solves the problem in some assertions from rotatedRectangleIntersection when dealing with rectangles far from origin.

alalek

Thank you for update!

modules/imgproc/src/intersection.cpp

modules/core/src/types.cpp

alalek

Looks good!
Please update PR's title and description before merge.

modules/core/src/types.cpp

alalek

Thank you for contribution 👍

gasparitiago changed the title ~~In the function that sets the points of a RotatedRect, the types~~ Change type used in points function from RotatedRect Apr 2, 2021

This was referenced Apr 2, 2021

Change type used in points function from RotatedRect #19840

Closed

Change type used in points function from RotatedRect #19841

Closed

Assertion error when running rotatedRectangleIntersection #19824

Closed

gasparitiago force-pushed the 3.4 branch from 3d252c5 to 9fab890 Compare April 2, 2021 15:09

added proper type casts

649f999

asmorkalov added the category: core label May 28, 2021

vpisarev self-assigned this Jun 6, 2021

Merge branch 'opencv:3.4' into 3.4

7530d2a

alalek reviewed Jun 7, 2021

View reviewed changes

modules/imgproc/src/intersection.cpp Show resolved Hide resolved

gasparitiago force-pushed the 3.4 branch from be1abf6 to 72857ef Compare June 7, 2021 20:40

alalek reviewed Jun 7, 2021

View reviewed changes

modules/imgproc/src/intersection.cpp Outdated Show resolved Hide resolved

modules/imgproc/src/intersection.cpp Outdated Show resolved Hide resolved

modules/imgproc/src/intersection.cpp Show resolved Hide resolved

modules/core/src/types.cpp Outdated Show resolved Hide resolved

Revert type changes in types.cpp and adequate code to c++98

bd379d5

alalek reviewed Jun 7, 2021

View reviewed changes

modules/core/src/types.cpp Outdated Show resolved Hide resolved

gasparitiago force-pushed the 3.4 branch from aa8a736 to 0b527fb Compare June 8, 2021 11:22

gasparitiago changed the title ~~Change type used in points function from RotatedRect~~ Update rotatedRectangleIntersection function to calculate near to origin Jun 8, 2021

Revert unnecessary casts on types.cpp

31e03e6

gasparitiago force-pushed the 3.4 branch from 0b527fb to 31e03e6 Compare June 8, 2021 11:25

alalek approved these changes Jun 12, 2021

View reviewed changes

alalek unassigned vpisarev Jun 12, 2021

alalek merged commit 3cf4375 into opencv:3.4 Jun 12, 2021

alalek mentioned this pull request Jun 19, 2021

(4.x) Merge 3.4 #20282

Merged

alalek mentioned this pull request Oct 15, 2021

(5.x) Merge 4.x #20886

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Update rotatedRectangleIntersection function to calculate near to origin #19842

Update rotatedRectangleIntersection function to calculate near to origin #19842

Uh oh!

gasparitiago commented Apr 2, 2021 •

edited

Loading

Uh oh!

crackwitz commented Apr 3, 2021 •

edited

Loading

Uh oh!

gasparitiago commented Apr 3, 2021

Uh oh!

crackwitz commented Apr 3, 2021

Uh oh!

asenyaev commented Apr 8, 2021

Uh oh!

vpisarev commented Jun 6, 2021

Uh oh!

gasparitiago commented Jun 6, 2021

Uh oh!

gasparitiago commented Jun 6, 2021

Uh oh!

Uh oh!

alalek left a comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

alalek left a comment

Uh oh!

Uh oh!

alalek left a comment

Uh oh!

Uh oh!

Uh oh!

Update rotatedRectangleIntersection function to calculate near to origin #19842

Update rotatedRectangleIntersection function to calculate near to origin #19842

Uh oh!

Conversation

gasparitiago commented Apr 2, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Readiness Checklist

Uh oh!

crackwitz commented Apr 3, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gasparitiago commented Apr 3, 2021

Uh oh!

crackwitz commented Apr 3, 2021

Uh oh!

asenyaev commented Apr 8, 2021

Uh oh!

vpisarev commented Jun 6, 2021

Uh oh!

gasparitiago commented Jun 6, 2021

Uh oh!

gasparitiago commented Jun 6, 2021

Uh oh!

Uh oh!

alalek left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

alalek left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

alalek left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

gasparitiago commented Apr 2, 2021 •

edited

Loading

crackwitz commented Apr 3, 2021 •

edited

Loading