How to get the minimum frame of a curved path along the borders of the path?

Question

Algorithms

There is a contour, I can easily make a rectangular vertical frame. (Second) but it may not be optimal in many cases. The area will be larger. Then how can you make a rotated one with a smaller area. There are optimal algorithms. The input is the vertices of all points of the curve.

Answer 1

There is an O(n log n) algorithm, where n is the number of points in the curve.
First, one can complete the curve to a convex hull. Get a convex polygon. The frame described around the curve will also be circumscribed around the convex hull. There are algorithms, for example, on Habré , or here there is with an implementation.
Second, it can be proven (see comments on this answer, thanks to Alexandroppolus for the idea) that the frame must pass through at least one side of the convex hull. Otherwise, it can be rotated, reducing the area until it touches the side.
Further, if the frame is slightly rotated, then the touch points either do not change at all, or go to the next vertex in the convex hull. Therefore, you can find four touch points for a vertical-horizontal frame simply by sorting through all the vertices of a convex polygon, and then instead of iterating, you can just look to see if you need to move any touch points forward.
It is convenient to implement this if we take the angles of inclination of all sides of the shell, shifted by 90, 180 and 270 degrees and sort them. Next, you need to sort through the frames with such angles of inclination of the first side (it is possible within [0.90) degrees). Find the first frame by enumeration, and then some points will need to be shifted.
So, the whole algorithm:
1) build a convex hull
2) add the angles of all sides and their copies rotated by 90, 180 and 270 degrees to the array and sort, but do not add angles not in [0,90).
3) for the first corner in the array, find 4 touch points of the frame.
4) For each segment of corners in the sorted array, check whether it is necessary to move the touch points forward (each of the four points with its own angle), then find the frame area at known points with a known slope.
Instead of working with angles, which requires trigonometric functions, you can work with vectors on the unit circle. On a segment of angles, you can easily take the middle by simply adding two boundary vectors and normalizing. For ternary search, it is not necessary to take 1/3 and 2/3 on the segment, so you can just as easily sum the vectors with coefficients 1 and 2 and normalize again (v1+2*v2). You can also sort by angle by comparing vectors through the cross product of vectors (sometimes called pseudoscalar).
To find a frame with a given angle on the points, you do not need to cross anything (except for the answer at the end, if you need to display the coordinates of the frame, and not just find the area). It is necessary to represent the lines in the form cosa*x + sina*y + c = 0. From here, knowing the point (x, y) and the angle of the line (a), we can find c. cosa and sina do not need to be calculated - these are the coordinates of the vector perpendicular to the known slope vector of the line. When you have found two values ​​of c for two parallel sides, these coefficients can be added - this will be the distance between the sides (you must add, because cosa and sina in these two lines will have different signs, because one right angle has half a turn more) . It remains to calculate this twice for perpendicular lines and multiply.
The code for crossing lines at the end can be found here .

Answer 2

Open the OpenCV sources and see how it's done in the minAreaRect function. All.