# Geometry lessons needed (aka finding a rectangle inside a rotated one)

So I have this project where I need to crop axis aligned patches out of a bigger scanned picture, containing rectangular color patches. The scan template can be transformed slightly; I build a transformation matrix and thus have access to its scale, translation and rotation values.

In other words: I want to extract an axis aligned rectangular image out of another rectangle that can be transformed one way or another. For this, I found the following code I translated to Xojo, and while it is working somewhat ok for tiny angles, it breaks for an angle of about 4Â° I am testing, producing negative values/rects which do not really match the conditions I am thinking of.

Anyone with a better knowledge of geometry here who can help me?
Thanks a lot!

``````Public Function rotatedRectWithMaxArea(w as double, h as double, angle as double) As Rect
//https://stackoverflow.com/questions/16702966/rotate-image-and-crop-out-black-borders/16778797#16778797
//Given a rectangle Of Size wxh that has been rotated by 'angle' (in
//radians), computes the width And height Of the largest possible
//axis - aligned rectangle(maximal area)within the rotated rectangle.
If w <= 0 Or h <= 0 Then
Return New Rect
End If
var side_long, side_short As Double
var width_is_longer As Boolean = w >= h
side_long = max(w, h)
side_short = min(w, h)
var x, wr, hr As Double
//# since the solutions For angle, - angle And 180 - angle are all the same,
//# If suffices To look at the first quadrant And the absolute values Of sin, cos :
var sin_a As Double = abs(sin(angle))
var cos_a As Double = abs(cos(angle))
If side_short <= 2.0 * sin_a * cos_a * side_long Or abs(sin_a - cos_a) < 1e-10 Then
//# half constrained Case : two crop corners touch the longer side,
//# the other two corners are on the mid - line parallel To the longer line
x = 0.5 * side_short
If width_is_longer Then
wr = x / sin_a
hr = x / cos_a
Else
wr = x / cos_a
hr = x / sin_a
End If
Else
// fully constrained Case : crop touches all 4 sides
var cos_2a As Double
cos_2a = cos_a * cos_a - sin_a * sin_a
wr = w * (cos_a - h * sin_a) / cos_2a
hr = (h * cos_a - w * sin_a) / cos_2a
End If
var w_bb As Double = w * cos_a + h * sin_a
var h_bb As Double = w * sin_a + h * cos_a
Return New Rect((w_bb - wr) / 2, (h_bb - hr) / 2, wr, hr)
End Function
``````

This is why I say â€śitâ€™s somewhat workingâ€ť:
First image is from a scan thatâ€™s almost perfectly aligned. The color patches do not have black outlines; thatâ€™s the transformation matrix showing patch borders.
The smaller, more upright rectangle is the result of the algorithm above. Looks to me like the result could be wider, but sufficient for my purposes. On the original template both rectangles match exactly.

And hereâ€™s how the stronger transformed result looks like â€¦

Hmm. Since you have a transformation matrix for the image, maybe it would be easier to simply rotate your image so that the swatches are aligned sufficiently such that you can simply extract the samples directly using regular coordinates?

Iâ€™d love to do so. Especially as the matrix works really well; I do not see any misplacements.
But we need an exact histogram of the extracted patches (rather 75% of it), and customer is concerned transformation could lead to some interpolation. Thatâ€™s why I am (currently) looking for this tedious approach.

I knew you were going to say that. Iâ€™m all-too-familiar with color calibration swatches.

1 Like

Why donâ€™t you do this: run a quick experiment by transforming the image and extracting the color swatches manually, and compare them to extractions from the un-transformed image. If you keep your extractions away from the edges, any interpolations should be negligible â€“ the pixels in the extraction will be surrounded by pixels of the same swatch and shouldnâ€™t introduce any color distortion.

Iâ€™m willing to bet the results are virtually identical.

I wonder if I shouldnâ€™t go for a cheapo approach first. The scan will never be rotated extremely; I think that my experiment with 4Â° is more extreme than what any serious scan operator would produce. As I said I need only 75% of the patch, so I could just take the center of the translated patch and build a rectangle of the required size based on it.
Maybe, if I force my maths knowledge really hard, I could even implement some sanity checking for extreme angles.

And yes, I agree with your assumption. Otherwise rotating an object in an image processing app repeatedly would produce visible artefacts, I guess. But first letâ€™s see if I can meet customer expectations.
Talking helped. Thanks!

If you were to fit an X-Y aligned square inside the rotated scan square, the scan angle can be as much as 9Â° off while still allowing you to get 75% coverage. Thatâ€™s a pretty careless scan.

1 Like

Yes, works great! Thank you!

THAT looks gorgeous! Good job!

Thank you. Thanks to Christianâ€™s GraphicsMagickMBS plugin, thatâ€™s all pretty fast too. Getting full histogram data for almost 300 patches and their averaged color in just a few seconds.

Can I ask what kind of device you are calibrating?

Sure. And I am not sure in this case
This is part of my work for a color management company, and while we started this subproject with Xerox copy/scan stations and a variety of printers in mind, I donâ€™t know if it will be limited to these only in the end.
The main project supports a variety of measurement instruments mainly, but not limited to X-Rite, TechKon and Spectro.