# Deterministic algorithm to fit rhombus to set of points

I'm looking for a deterministic algorithm to obtain the best fitting rhombus out of a set of user-drawn points. It need not necessarily be optimal (simple would be better).

Thanks.

-
Do you mean to choose 4 points in a set so that they are the corners of a rhombus, or choose the corners of a rhombus, so that some points in the set are on it's edges? –  Karolis Juodelė Aug 14 '12 at 12:43
The vertices of the rhombus need not be part of the initial point set. As when using the least squares method to determine the best-fitting line from a point data set, the target shape should be the one that minimises the error. (When I said "it need not necessarily be optimal", I meant in terms of computing time.) –  Tamori Aug 14 '12 at 12:52
How many points are provided? Does the rhombus have to have any of its sides parallel to any of the axes? How is the error measured? –  marty cohen Aug 14 '12 at 15:06
A number of points greater than 4 is provided (the user draws the shape using a digital stylus). The rhombus does not necessarily have sides parallel to the main axes. There is no specification for the error, one of the usual metrics such as least squares can be used. –  Tamori Aug 14 '12 at 16:13
$$x = (A^T A)^{-1} A^T b$$
Thanks for the answer but could you maybe me a little bit more specific? AFAIU, for least squares you have to minimise an equation of the form $\sum\limits_{i=1}^n [y_{i} - f(x_i,a_1,a_2,...,a_n)]^2$ where f is the function defining the curve to be approximated, in my case the rhombus. I'm not sure how f would be defined here exactly, though. Maybe the Cartesian system is not appropriate? –  Tamori Aug 15 '12 at 9:48
@Tamori - The solution I gave is one that minimizes $b = Ax$ for a given $x$. You first have to find the form of the matrix $A$, which is the one relating between the coordinates, and the five unknown parameters. Once you know that, you use the user input as $b$, and then solve for $x$ - the five rhombus parameters. –  nbubis Aug 15 '12 at 10:22