1
$\begingroup$

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.

  • 0
    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?2012-08-14
  • 0
    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.)2012-08-14
  • 0
    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?2012-08-14
  • 0
    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.2012-08-14

1 Answers 1

0

Well a rhombus is well defined by two slopes and three intercepts, so you have five unknowns to solve for. The problem is of course that your inputs (i.e. the matrix coefficients) are not exact. In this case, least squares leads to:

$$x = (A^T A)^{-1} A^T b$$

  • 0
    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?2012-08-15
  • 0
    @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.2012-08-15
  • 0
    To whomever downvoted, mind adding an explanation on why you think this won't work / or where I'm wrong? It's an interesting problem to me, and if you have a better solution, I'll be the first to upvote it.2012-08-16