How to distribute points across the panel based on distance data?

Question

So, I'm not sure how to properly explain this one, so if something is unclear ask in the comments, I'll try to use the exam question layout so you can easily spot restrictions.

Problem:

You're given an input of Panel (with fixed size), an array of PointF[] of fixed size n, and the distance data that contains distances between each pair of points in indexed arrays of size n which are accessed via DistanceData field in the following way:

DistanceData[i].getDistances(k) returns int which represents the distance between i-th and k-th point. As a corollary, the DistanceData[k].getDistances(i) returns the same value. If i==k, it returns 0.

Your task is to update the Panel so that it honestly represents the DistanceData i.e. if DistanceData[1].getDistances(3) < DistanceData[1].getDistances(4) then the panel should display 1st and 3rd point closer than the 1st and 4th point etc.

Note: The distance data is inputted independently of the Points previously drawn on the Panel. Or rather, the Panel only contains the number of Points and you need to distribute them according to the values found in DistanceData.

Note#2: The tag "travelling-salesman" is there to remind you that all the points are dependent on each other i.e. all pairs have unique distance.

My take: The problem I'm facing is if I iteratively solve this - point by point, I find that I break the solution I did in the previous steps. To illustrate this: If I run a loop for 4 points and in the first iteration I draw the points based on the distances from the first point, the next step will almost certainly scrap that solution if it looks at the distances from the second point and so on...

Answer 1

If all you have is distance data, then there is more than one valid distribution of points.

You can translate your collection of points any distance in any direction, and the comparative distances will be the same. Therefore, we're free to choose whatever location we like to place the first point. Place point 1 at the origin, (0, 0).

You can rotate your collection of points about any axis, and the comparative distances will be the same. Therefore, we're free to choose any location to place the second point, as long as it's the correct distance from the first point. Place point 2 at (DistanceData[0].getDistances(1), 0).

There are two places where point 3 can go while still satisfying the distances with respect to points 1 and 2:

We can use the Circle-Circle intersection formula to determine point 3's x coordinate.

d = distance between point 0 and point 1
R = distance between point 1 and point 3
r = distance between point 2 and point 3
x = (d^2 - r^2 + R^2)/(2*d)

There are two possible solution for point 3's y coordinate. You can find them by rearranging the terms in the Pythagorean formula.

y = sqrt(R^2 - x^2)
or
y = -sqrt(R^2 - x^2)

You can flip your collection of points over the x axis, and the comparative distances will be the same, so you can choose whichever of these y values you like. I prefer the positive one.

You now know the position of three points. You can then use trilateration to find the position of all other points.