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.

  • $\begingroup$ Is the rectangle in general position, or is it known that the sides are oriented to $x$ and $y$ axes? $\endgroup$ – hardmath Feb 5 '16 at 18:41
  • 1
    $\begingroup$ It's arbitrarily rotated, I updated the question. $\endgroup$ – FooBar Feb 5 '16 at 18:41
  • $\begingroup$ Not guaranteed. Are you thinking about a PCA? $\endgroup$ – FooBar Feb 5 '16 at 19:17
  • $\begingroup$ Yes, you read my mind. How big will the data set be and how well scattered will the points be around the perimeter? $\endgroup$ – hardmath Feb 5 '16 at 19:18
  • 1
    $\begingroup$ Are the points on the perimeter of the rectangle or all over the area of it? $\endgroup$ – nicoguaro Feb 5 '16 at 21:13

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.

  • 2
    $\begingroup$ @FooBar: Would you care to post a sample data set of a few dozen points for the sake of illustration? $\endgroup$ – hardmath Feb 6 '16 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.