Algorithm for best fit rectangle

Question

I'm looking for an algorithm to do a best fit of an arbitrary rectangle to an unordered set of points. Specifically, I'm looking for a rectangle where the sum of the distances of the points to any one of the rectangle edges is minimised. I've found plenty of best fit line, circle and ellipse algorithms, but none for a rectangle. Ideally, I'd like something in C, C++ or Java, but not really that fussy on the language.

The input data will typically be comprised of most points lying on or close to the rectangle, with a few outliers. The distribution of data will be uneven, and unlikely to include all four corners.

Answer 1

Here are some ideas that might help you.

We can estimate if a point is on an edge or on a corner as follows:

1. Collect the point's n neares neighbours
2. Calculate the points' centroid
3. Calculate the points' covariance matrix as follows:
   1. Start with Covariance = ((0, 0), (0, 0))
   2. For each point calculate d = point - centroid
   3. Covariance += outer_product(d, d)
4. Calculate the covariance's eigenvalues. (e.g. with SVD)
5. Classify point:
   • if one eigenvalue is large and the other very small, we are probably on an edge
   • otherwise we should be on a corner

Extract all corner points and do a segmentation. Choose the four segments with most entries. The centroid of those segments are candidates for the rectangle's corners.

Calculate the normalized direction vectors of two opposite sides and calculate their mean. Calculate the mean of the other two opposite sides. These are the direction vectors of a parallelogram. If you want a rectangle, calculate a perpendicular vector to one of those directions and calculate the mean with the other direction vector. Then the rectangle's direction's are the mean vector and a perpendicular vector.

In order to calculate the corners, you can project the candidates on their directions and move them so that they form the corners of a rectangle.

Answer 2

The idea of a line of best fit is to compute the vertical distances between your points and the line y=ax+b. Then you can use calculus to find the values of a and b that minimize the sum of the squares of the distances. The reason squaring is chosen over absolute value is because the former is differentiable at 0.

If you were to try the same approach with a rectangle, you would run into the problem that the square of the distance to the side of a rectangle is a piecewise defined function with 8 different pieces and is not differentiable when the pieces meet up inside the rectangle.

In order to proceed, you'll need to decide on a function that measures how far a point is from a rectangle that is everywhere differentiable.