Fit fixed rectangle to set of points

1
votes

i was wondering if someone every tried to fit a rectangle with a fixed size to a given set of points.

Imagine you have a set of points which is unsorted and not always showing a full hull of a rectangle. The image below should demonstrate the problem: enter image description here

The set of points can vary and points could be missing. I would like to find a least squares method to find the best fitting rectangle with fixed side lengths.

Maybe I could find regression lines first but it seams to be possible to go a different way.

I'd appreciate any kind of hint.

3
pythonmathcomputational-geometrycurve-fittingleast-squares
Is the rectangle upright? – Aguy
no it could be rotated – GeoGecco
There are three degrees of freedom. Shouldn't be too hard to find a solution with some non-linear least-squares solver. Maybe start with the centroid and the principal axes of the points as the initial guess. – Nico Schertler

3 Answers

1
votes

Just an outline of the solution:

  1. The height and width of your rectangle is fixed, so you can define it with three parameters (x0, y0, theta): say the lower left corner and rotation.
  2. Use a distance function like pnt2line given here http://www.fundza.com/vectors/point2line/index.html
  3. Now write a wrapper function: for each point, calculate the distance from all four edges of the rectangle, and assign distance[i] as the minimum of these four distances
  4. Use this distance array in scipy.optimize.curve_fit to find your best-fit parameters
0
votes

If there are outliers, RANSAC can be your good friend. To perform a fit, you need three points taken from different sides. So just pick three random points and hypothesize that two of them belong to one side and the other to an orthogonal side. Finding the pose parameters is no big deal. You can compute the fitting error from the distance function as described by @VBB (for every point take the shortest distance to a side).

Depending on your taste, you can use the same three points once, with an arbitrary side assignment, or try different assignments and keep the best.

For the final fit of the inliers, you can use a trick.

  • Assign every inlier to the closest side;

  • Center the cluster of every side on its respective centroid;

  • Rotate the clusters of every other side by 90°;

  • This yields a single cluster with a single orientation; perform ordinary line fitting to get that orientation.

0
votes

Define the distance d(R(P), Q) between the fixed-size rectangle R(P) at position P and a point Q to be the length of the shortest straight line connecting the two. This is very easy to define as a function reasoning by cases.

Now just use some form of gradient descent to find the optimal P* such that the sum of d(R(P*), Q)^2 for Q in your point set is minimized.