Minimum Bounding Quadrilateral
The fitting of a minimum area quadrilateral to a set of points is an uneasy problem, and I believe that simpler approaches are good enough.

Notice that the corners are rounded and cannot be used as such. So you'd better fit straight edges and intersect them to obtain the quadrilateral.

One approach is by the Hough transform. To make it maximally efficient, I would recommend to process four tight areas or interest around the edges of the axis-aligned bounding box. This will make processing much faster, avoid false positives and avoid any ambiguity on the correspondences.

You can also sample points on the four sides and fit a straight line by total-least squares, or by some robust line fitting method.

If you want to make sure that the fitted lines don't cross the shape at all, you can handle the four sides independently and consider a partition of the plane in the four quadrants delimited by the diagonals (even if they are approximate). In every quadrant, you will find the minimum area triangle formed by the line against an edge of the convex hull. Just try every edge of the convex hull in turn.

[Technically, it is possible that the minimum is achieved with a line through some vertex of the convex hull, with an intermediate angle, i.e. not in the direction of a hull side. We should also check if the area function is always unimodal in terms of the line angle. IMO these refined considerations can come later.]