Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

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$$

share|improve this answer
    
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
    
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. –  nbubis Aug 16 '12 at 6:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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