1

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?

daviestar
  • 4,531
  • 3
  • 29
  • 47
  • 2
    Check if all four corners of the inner rectangle are inside the outer rectangle. – alain Sep 14 '17 at 22:15
  • The naive method is to check each line segment of the smaller rectangle to see if it intersects any segment of the larger rectangle. You have the points for the rotated rectangle (assuming you know the rotation angle), so it's just 16 line intersection tests. Not optimum, but it's a start. And if you can make some assumptions (like the left side of the selection rectangle can't intersect the right side of the rotated rectangle), you can reduce the number of tests you have to make. – Jim Mischel Sep 14 '17 at 22:58

2 Answers2

3

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.)

  • thanks, this is ingenious :) the slightly more intensive counter-rotate operation can be made on mouse down, then on mouse move i can just check if all 4 corners are in the box. great! – daviestar Sep 27 '17 at 17:43
  • Intensive ? What do you mean ? This must be taking under 0.1 microsecond. –  Sep 27 '17 at 17:48
  • the native trig functions in javascript can be slow so it's nice that your answer allows me to cache those calculations strategically (on mousedown) and not fire them at 60fps (on mousemove).. every little helps in the browser! – daviestar Sep 27 '17 at 21:54
  • @daviestar: IMO, 60 fps is eternity compared to the time to evaluate the trigs. And as long as the angle is fixed, there is no need to recompute them. This hit-detection code is peanuts. –  Sep 28 '17 at 07:39
0

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.

m69's been on strike for years
  • 11,835
  • 3
  • 34
  • 57