1
$\begingroup$

I have a set of 2D points in which each pair has a known Euclidean distance between them. How can I go about determining an arrangement of them?

I understand there is not a unique solution in general, but for the sake of my question, assume one point is fixed at the origin.

Mathematically, we have $P = \{p \vert p \in R^2\}$ and $D = \{d \in P \times P \vert \| d\| \text{is known} \}$. How can I find a valid arrangement? (Forgive my rustiness with proper set notation)

Note: I feel like least squares may be the best solution. This is related to bundle adjustment in photogrammetry.

$\endgroup$
  • $\begingroup$ I may not be understanding, but even if you fix one of the points at the origin, there is still no unique solution since only knowing the distance will give you a circle about the origin. $\endgroup$ – Carser Sep 23 '16 at 13:50
  • $\begingroup$ @Carser: That's fine. I guess I should have specified that. Or left out the fixed point. Or assume that a second point is fixed along the X axis as well (i.e. (X, 0)) $\endgroup$ – marcman Sep 23 '16 at 13:52
  • $\begingroup$ How many points do you have? $\endgroup$ – Paul Sep 23 '16 at 14:03
  • $\begingroup$ @Paul: >=3 points $\endgroup$ – marcman Sep 23 '16 at 14:19
  • $\begingroup$ Notice that you can fix two points, not just one. If you have the first point at the origin, you can also a set a second point at $(d_{12},0)$ where $d_{12}$ is the distance from the first and second points. If there are only 3 points, there are 2 locations that 3rd point can be (if there are any). For more than 3 points, you can iterate this process, although there is no guarantee of any solution. $\endgroup$ – Paul Sep 23 '16 at 15:45
1
$\begingroup$

This solution assumes that a solution exists; to check whether a solutions exists requires more iteration.

Notice that you can fix two points, not just one. If you have the first point at the origin, you can also a set a second point at $(d_{12},0)$ where $d_{12}$ is the distance from the first and second points. If there are only 3 points, there are 2 locations that 3rd point can be (if there are any). For more than 3 points, you can iterate this process, picking a pair of points to locate the third. Since for each step there are 2 possible locations, you may run into a situation that is impossible for a previous choice, so you have to go back and make the opposite choice.

$\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.