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).
Intersecting a polygon with four points
-
1Why 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. – 2011-05-23
1 Answers
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.