5
$\begingroup$

I am able to measure my distance to a set of (about 6 or 7) fixed but unknown points from many positions.

The difference in position between measurements is also unknown.

I believe that I should be able to work out the relative position of the fixed points, and therefore where I measured from and the path I took.

I have looked at the wiki page for trilateration, but it only gives examples working from known points.

Any help?

  • 0
    I understand that, but it doesn't get me any closer to a solution. I will need to use differences in the distance sets of two or more readings.2010-12-12

2 Answers 2

5

For each distance measured, you can write an equation for the distance between that point on your path and that fixed point, both of which are unknown. In two dimensions (on a flat plane), each unknown point has two unknown coordinates. If you have $n$ fixed points and you measure from $k$ points on your path, you will have $nk$ distances and equations and $2n+2k$ unknowns. As long as $nk\ge 2n+2k$, this should yield a system that can be solved (if the distances are exact), but it probably helps to have $nk$ be more than $2n+2k$ because the system when $nk=2n+2k$ might have multiple solutions (because the equations are nonlinear). (If you are working in three dimensions, then $2n+2k$ changes to $3n+3k$.)

  • 0
    Since the whole setup is invariant under isometric transformations, there are three degrees of freedom which you can't conclude from the variables. Fixing them in an arbitrary way corresponds to an arbitrary choice of coordinate system. It makes sense to think of these three degrees of freedom as origin and orientation of the coordinate system. [This newer question](http://math.stackexchange.com/q/972462/35416) referenced the one here, which is how I noticed your answer.2014-10-14
1

I'm elaborating on the answer Isaac already gave, so I'll adopt his notation. I'm posting a second answer to elaborate the point of isometric transformations, but also because the question has been asked again and the author of that newer question found the existing answer insufficient.

Suppose you have $n$ fixed points and perform $k$ distance measurements to all of these, taken from different points. Also suppose that you are working in the plane, althgough the ideas can be easily generalized to 3D space. Let's assume the fixed point with index $i$ is at position $(a_i,b_i)$ and the measurements with index $j$ were taken from position $(x_j,y_j)$, then the equations are of the form

$(a_i-x_j)^2 + (b_i-y_j)^2 = d_{ij}^2$

where $d_{ij}$ is the distance you measured to fixed point $i$ from position $j$ along the trajectory. So you have $2n$ variables $a_i,a_j$ and $2k$ variables $x_i,y_i$ together with $n\cdot k$ equations.

But the whole setup is invariant under isometric transformations. Which means you can't know the origin or orientation of your coordinate system, since that coordinate system is completely arbitrary. Therefore you might simply fix some coordinate system, by choosing $x_1=y_1=y_2=0$. So the origin of the coordinate system is defined as your starting point, and the $x$ axis of the coordinate system is the direction from the first to the second point of your trajectory. This adds three more equations. (If you were operating in 3D instead of 2D, then you'd end up with 6 parameters you may choose arbitrarily, three for position and three for orientation.)

A system of $n\cdot k+3$ equations with $2n+2k$ will often have a finite number of solutions if $2n+2k=n\cdot k+3$. At least if the equations are sufficiently independent. If the equations were linear, that solution would be unique, but as the equations are non-linear, there may be multiple solutions. If you have more than the required number of equations, that might help you pick one of these. I'll not discuss techniques of how to solve systems on non-linear polynomial equations, but I suggest you let some computer algebra system or some numerical tool designed for the task handle that.

Of course, if you have more equations than absolutely required, and if your measurements are subject to some error (measurement error, rounding error, …) then you may end up with no matching solution at all. So you'll want the solution which is closest to your measurements, even though it doesn't exactly reproduce the observed measurements. This would place the problem in the domain of unconstrained non-linear optimization. You'd definitely want to tackle this numerically, and would be well advised to use a tool designed for that task.

  • 0
    I have ended up with the same problem as above, and have been struggling to think of a method for optimising a solution. In my case $i$ is large (10s of thousands potentially) and $j$ is small (e.g. 4). The quadratic programming tools all tend to have high computational complexity, and so I was wondering about a statistical method for an approximation. (I've realised I can drop the degrees of freedom of the solution by defining an orthonormal coordinate system along $x_j x_{j+1}$)2018-08-28