# Intersecting a polygon with four points

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).

-
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

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.

-
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