algorithm - hit detection of rectangle inside rotated rectangle

539 Views Asked by At

screenshot of cropbox inside rotated image

I am working on an image editor project, where you can rotate and crop an image.

The problem I'm currently facing is once I've rotated the image, I'd like to be able to drag the crop box anywhere inside the boundaries of the rotated image. So far I've been looking at the Liang-Barsky and Cohen-Sutherland line-clipping algorithms, and Separating Axis Theorem, but I'm struggling to see how I can implement these for my use case.

Can anyone point me in the right direction? Am I barking up the wrong tree?

2

There are 2 best solutions below

4
On BEST ANSWER

Use the comment by Alain. To check insideness of the corners, it suffices to counter-rotate the image to make its edges axis-aligned. Then you have an easy point-in-axis-aligned-box problem.

enter image description here

(I don't mean that you really have to rotate the image, just the geometry.)

0
On

If the movement that the user tries to make is [dx,dy] then consider the line segments from the corners of the selection to those points translated by [dx,dy] (the yellow lines in the example below). These lines may intersect with the rotated image boundaries (green lines) at certain points (the red dots). If there are no intersections, then the movement is legal. If there are one or more intersections, these will tell you up to which point the movement was legal; the intersection point which is closest to its original position (checking either horizontal or vertical distance is enough to establish this) determines the maximum movement (the bottom right corner in the example). You can then limit the translation to this point.

translation of rectangular selection

Depending on which quadrant the direction of the movement is in (towards top right in the example) you can skip checking one of the corners (the bottom left corner in the example); the other corners will always bump into the boundaries first.
You can also skip checking two of the boundaries (bottom and left in the example), by comparing the direction of the movement with the rotation angle of the image.
So you need to check for intersections of 3 line segments with 2 line segments. For line segment intersection code, see e.g. this question.

If the user is dragging only one side, and extending the rectangle instead of moving it, then you only have to check the two corners that are moving.