Fitting a rectangle to a point set

Question

I have an ordered list of (2d-)points that are forming a (not axis aligned) rectangle and I'd like to recover that rectangle. Approximations like a minimal enclosing rectangle can't be used so that I'm looking for an algorithm that minimizes the least-squares norm or the hausdorff distance.

The rectangle can be a square or rather narrow. The set contains several hundred points and the points cover at least three sides.

My current idea looks like that:

Initial estimation of center, rotation and lenghts from doing a PCA on the point set. (Rotation estimation will be especially bad for squares).

Then the points will be assigned to the closest side and the mean (rmse?) error recorded. This can be used as an optimization value for a following iterative LM-Optimization.

Answer 1

Some thoughts, to be refined with computational trials:

1. Start with an estimate for the center $X_C,Y_C$, either by PCA as suggested in the OP, or by using the center of a bounding box or circle (fairly cheap computations, and I think we only need an estimate of the center whose error is small relative to the dimensions of the rectangle).

2. Sweep through the data points to calculate angle and distance relative to the estimated center, $(\theta_i,r_i)$.

3. This derived data can be fitted as a periodic function $\theta$ vs. $r$. Intuitively the "local" maximum values occur at the corners of the rectangle and would be equal if all four corners were well-represented in the data (and thus would be global maxima in the ideal case).

4. To help with any "missing" side for the rectangle in the data, we reflect all the points through the estimated center, thus achieving more complete coverage of the perimeter. It seems that we don't need to actually compute those reflections, since the effect on the angle vs. distance derived data is simply to impose a period of $\pi$ rather than $2\pi$ on the model.

5. Fit (by least-squares) a two segment trigonometric model to the angle vs. distance data, using the half-interval of length $\pi$ that begins and ends at one of the maxima. (The other intervening maximum separates the two segments.) That is, an edge of a rectangle with Cartesian equation $y = mx+b$ would have an angle vs. distance relation of the form: $$ r = \frac{b}{\sin \theta - m \cos \theta} $$

6. Analyze the errors in fitting for systematic bias in the data points from the two half-intervals. That is, if the data points in one half-interval for one segment have predominantly positive errors and data points in the other half-interval for the same segment have predominantly negative errors, this is an indication our estimated center needs to move toward the original points that are now giving positive errors (actual radius from estimated center minus the fitted model's predicted radius).

7. Rinse. Lather. Repeat.