2
$\begingroup$

Assume that we have a plane $P(a,b,c,d)$ whose equation is unknown.
We know that there is a point set $N = \{n_1, n_2, ...\}$ and $\forall n_i \in N$, $n_i$ is on $P$.
Also, $\forall n_i, n_j \in N$, we know the euclidian distance between $n_i$ and $n_j$.

Now, let us assume we have another point set $M = \{m_1, m_2, ...\}$ and $\forall m_i \in M$, we know the coordinates of $m_i$.

How many pairwise distances $d(n_i,m_j)$ do we need to find the equation of $P$ and the most important part; how do we calculate it?

I'm going to write a Java code for this, so please help me to solve this problem step by step.

Here is what I have acheived so far:

A plane has 3 unknowns: $a,b,c,d$ I need a linear system that has 4 equations.
Assume that we have 4 point-to-point connections.
Namely: $(n_1, m_1)$, $(n_2, m_2)$, $(n_3, m_3)$ and $(n_4, m_4)$
Knowns:

  • $d(n_1, m_1)$
  • $d(n_2, m_2)$
  • $d(n_3, m_3)$
  • $d(n_4, m_4)$
  • $d(n_1, n_2)$
  • $d(n_1, n_2)$
  • $d(n_1, n_3)$
  • $d(n_1, n_4)$
  • $d(n_2, n_3)$
  • $d(n_2, n_4)$
  • $d(n_3, n_4)$
  • $coplanar(n_1, n_2, n_3, n_4)$
  • $x,y,z$ coordinates of $m_1$
  • $x,y,z$ coordinates of $m_2$
  • $x,y,z$ coordinates of $m_3$
  • $x,y,z$ coordinates of $m_4$

Unknowns:

  • a
  • b
  • c
  • d

That seems easy, but I could not build a linear system.

Important notice: Because of quadratic equations, there might be two solutions. Two solutions are OK. But in some cases, there are infinitely many solutions.
The question may be asked: What are the characteristics of the distance measurements $d(m_i, n_j)$ to localize $P$?

$\endgroup$
9
  • $\begingroup$ If you already have points $M$ on $P_2$, then don't you already know the equation of that plane? $\endgroup$ – Victor Liu Apr 21 '14 at 17:19
  • $\begingroup$ I only know the number of points and their relative poisitons on the plane. Since I don't know the equation of the planes, I don't know the coordinates of the points. $\endgroup$ – padawan Apr 21 '14 at 17:23
  • $\begingroup$ What do you mean relative positions on the plane? So you know the pair-wise difference vectors $m_2-m_1$, etc.? That does not fix the positions globally, but it is enough to compute the normal vector of the plane. $\endgroup$ – Victor Liu Apr 21 '14 at 18:20
  • $\begingroup$ @VictorLiu I mean, if you assume that plane is $z = 0$ plane, all the coordinates are known. $\endgroup$ – padawan Apr 21 '14 at 18:23
  • $\begingroup$ Ok, so it seems that you mean you only know the $x,y$ coordinates, and not $z$? And your plane is restricted to be a graph in the $x,y$ plane? $\endgroup$ – Victor Liu Apr 21 '14 at 19:10
1
+50
$\begingroup$

Assuming every known distance corresponds to a rod, you need $M\ge3$, otherwise the system is a mechanism (you can rotate it around $m_1m_2$).

Knowing three $m$ points allows you to directly obtain the absolute position of any point $n$ by solving a system of 3 quadratic equations in 3 unknowns. You will find two solutions, symmetric wrt the plane $m_1m_2m_3$. http://en.wikipedia.org/wiki/Trilateration

From 9 $d(m_i,n_j)$ distances, you can retrieve 3 $n_j$ points and construct the plane. You can reject some of the solutions (among $2^3=8$ combinations) by checking compatibility with the $d(n_j,n_k)$ distances. But this deserves deeper analysis.

Using a fourth $m_4$ point not coplanar with the other three shoud allow you to always resolve ambiguity.

If computing the $d(m_i,n_j)$ is more "costly" than the $d(n_j,n_k)$, you can do with less evaluations by constructing $n_1$ from $m_1, m_2, m_3$, then $n_2$ from $n_1, m_2, m_3$ and $n_3$ from $n_1, n_2, m_3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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