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.

Assuming you have four points in general position in the plane and a (possibly non-convex) polygon. How do you find the parameters of a transformation [s*R, t] (homogenous scaling, rotation and translation) of the corners of the polygon, so that the four points mentioned at the beginning each lie on some edge (or on a corner) of the polygon (all points have a distance of 0 to the polygon).

share|improve this question
    
Why should this be possible? If the four points have one inside the triangle formed by the other three, and the polygon is convex, then I don't see how it can be done. –  Henry May 23 '11 at 9:26
    
I agree that sometimes it should be impossible. But clearly it is also sometimes possible. How could you distinguish between these two cases? I think this is mainly equation solving - and there obviously you also have the cases of: no solution, one/many solutions. It would be nice two know what situation we have for a given set of points and a given polygon - and find a specific solution if there is one or many. –  Peter Sheldrick May 23 '11 at 9:34
add comment

1 Answer

up vote 4 down vote accepted

Dear Peter, you denote the points $A,B,C,D$ and the line intervals making up the polygon $I_1, I_2, \dots I_n$. You write down the $n$ equations for the straight lines into which the edges of the polygon belong.

It's helpful to use complex coordinates. The positions of the points $A,B,C,D$ are $z_A, z_B, z_C, z_D$. After the transformation you described, they get mapped to general linear functions $$z'_A = M z_A + N$$ and similarly for $B,C,D$ - with the same complex parameters $M,N$. You substitute these expressions for $z'_A, \dots z'_D$ to the equations for the lines containing the edges.

The equations for these lines of edges may be written as $${\rm Re} (z Q_i) = R_i $$ where $Q_i$ is a known and fixed complex parameter and $R_i$ is a known and fixed real parameter for each edge. Now, you must try all combinations of choices into which edges the points $A,B,C,D$ belong. So you have four labels $i_A,i_B,i_C,i_D$ that go between $1$ and $n$ and identify the edge and with these labels, you may finally start to solve equations.

The equations are for the two complex unknowns $M,N$, and their equations of the form $${\rm Re} (z_A Q_{i_A}) = R_{i_A} $$ plus three similar equations with $A$ replaced by $B,C,D$. These are equations saying that the points $A,B,C,D$ belong to the edges number $i_A,i_B,i_C,i_D$. Indeed, these are four real equations for two complex variables, so you do expect to find solutions in many cases.

When you find a solution, you must still check that the points $A,B,C,D$ belong not only to the infinite lines but to the actual line interals making up the polygon's boundary. That's 8 inequalities to be checked.

To summarize, you take $n^4$ different combinations of the labels $i_A\dots i_D$ identifying which edges should contain which points $A,B,C,D$; for each of these $n^4$ choices, you solve the set of 4 real equations for 4 real unknowns; and then you finally check 8 inequalities for each of these $n^4$ cases. You also eliminate all (singular) solutions with $M=0$ that would like to shrink the whole group of 4 points $A,B,C,D$ to a single point.

share|improve this answer
    
Thanks that is a good answer. I'm actually trying to implement this as an algorithm - and i was trying other ways to solve this as well. But i think i will try to implement this solution. –  Peter Sheldrick May 23 '11 at 13:11
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.