I have 5 {x,y} points randomly placed on a grid
Each of the points do not know the {x,y} coordinates of the other points
Each of the points do know the distance of each of the other points from their {x,y} position
Each of the points exchanges this distance information with every other point
So every point knows every distance of every other point
Using this distance information every point can calculate (by finding the angles) triangles for every other point using itself as a reference point
Example, point 1 can calculate the following triangles: 1-2-3, 1-2-4, 1-2-5, 1-3-4, 1-3-5, 1-4-5, and using the distance data recieved from the other points it can also calculate 2-3-4, 2-3-5, 2-4-5, 3-4-5
I would like to build a map of the location of every other point relative to a single point
How should I go about doing this? I am asuming it would be some kind of triangulation algorithm but these mainly seem to compute the location of a point from three other points, not the other way around where the other points {x,y} coordinates are discovered based on only the distance information.
I have tried plotting the two possible triangles for every 3 triangle points and then rotating them on a fixed known point to try and align them, but I think this avenue will end up with too many possibilities and errors
Ultimately I would like every point to end up with {x,y} coordinates of every other point relative to itself
You know the distance from one point to every other, dij
. Thus, point 2 lies in a circumference of center point 1 and radius = d12. Point 3 lies in a circumference of center point 1 and R=d13 and it also lies in another circumference of center point 2 and R=d23.
See this picture:
I've set point 2 in X-axis for simplicity.
As you see, point 3 is on the intersection of two cicrcumferences centered at P1 and P2. There is a second intersection, P3a
. Let's choose the one that is upwards and continue.
For P4
we can use three circumferences, centered at P1, P2 and P3. Again we get two solutions.
The same process can be done with the rest of points. For Pn
you have n-1
circumferences.
I'm sure you can find the maths for circle-circle intersection.
Some remarks must be observed:
1) The construction is simpler if you first sort the points by distance to P1
.
2) Not all distances generate a solution. For example, increase d13
an there's no intersection between the two circumferences for P3
. Or increase d14
and now the three circumferences don't intersect in just the two expected points 4
and 4a
.
3) This fact can be overworked by considering the average of intersections and the distance from each solution to this average. You can set a tolerance in these distances and tell if the average is a solution or else some dij
is wrong. Since two solutions are possible, you must consider two averages.
4) The two possible triangulations are symmetric, over X-axis in the case I've drawn.
The real solution is obtained by a rotation around P1
. To calculate the angle of rotation you need the {x,y}
coordinates of another point.