Solving for Intersections of many lines algebraically

48 Views Asked by At

The context:

In the analysis of beam structures, one can gain insight from the rigid body kinematics, which show the possible infinitesimal displacements of a given structure. To determine the center of instant rotation for infinitesimal displacements, one can utilize the Polplan (I haven't found a english equivalent for it.) I have been given the task to construct it within a program, for easing the effort to grade students work, as well as designing new tasks for them.

To construct the Polplan, there are two types of centers: absolute centers, being denoted with the two same indices $(i,i)$ and relative centers with two different indeces $(i,j)$. The order of the indeces doesn't matter, therefore $(i,j)$ and $(j,i)$ denote the same center.

Due to the notion of centers "being at infinity" (corresponding to a translation in the euclidiean plane), the construction takes place in the projective plane. Therefore each center has the homogenious coordinates $[x:y:1]$.

The Polplan gives us rules how these centers relate to one another. The 2 Rules from whom the complete Polplan can be constructed given some initial centers are:

Two absolute centers $(i,i)$ and $(j,j)$ and their relative center $(i,j)$ are on a line. $(i,i)-(i,j)-(j,j)$.

Three relative centers $(i,j)$, $(i,k)$ and $(j,k)$ lie on a line. $(i,j)-(i,k)-(j,k)$.

The question:

To solve for the centers efficiently, I tried to write down equations for the two rules, which can be put in a linear system of equations where the unknowns are the coordinates of the centers.

I know that intersections of two lines of the form $a_1x+b_1y+c_1=0$ and $a_2x+b_2y+c_2$ in homogenious coordinates can be computed by $$ \begin{bmatrix}a_1 \\ b_1 \\ c_1 \\\end{bmatrix}\times\begin{bmatrix}a_2 \\ b_2 \\ c_2 \\\end{bmatrix} $$

The problem is, in order to know the coefficients $a_1,b_1,c_1$ and $a_2,b_2,c_2$, I already need to know two points of the two lines! If I compute $a,b,c$ from two points I have to multiply the coordinates of them together, for example: $$ c = x_1 y_2 - x_2 y_1 $$ But If I do not know the coordinates $x_1,y_1,x_2,y_2$ I cannot write down this as a set of linear equations.

My question being: Given $n$ rules, which denote incident relations of $m$ points, can I write down a linear system of equations which can be solved for the coordinates of all points, given some initial points? If this is not possible, I'd like to know why it isn't.