5
$\begingroup$

As part of a larger problem, I am trying to detect based on the distance matrix which segments intersect in the original 2D space that originated the matrix. I don´t have coordinates (lat/long, x/y or any other for the points).

As an example, on the image below, the answer to the question for the top graph would be: AD, BC. While for the bottom graph would be AC, BD.

The information that we have is just the distance matrix:

DISTANCE MATRIX TOP

$ \begin{align} && A && B && C && D \\ A&& 0 && 1 && 1 && \sqrt{2} \\ B&& 1 && 0 && \sqrt{2} && 1 \\ C&& 1 && \sqrt{2} && 0 && 1 \\ D&& \sqrt{2} && 1 && 1 && 0 \end{align} $

DISTANCE MATRIX BOTTOM

$ \begin{align} && A && B && C && D \\ A&& 0 && 1 && 1 && \sqrt{2} \\ B&& 1 && 0 && \sqrt{2} && \sqrt{5} \\ C&& 1 && \sqrt{2} && 0 && 1 \\ D&& \sqrt{2} && \sqrt{5} && 1 && 0 \end{align} $

enter image description here

I have tried so far to use the triangular inequality and some other (probably) naive geometric knowledge but I can´t figure out what conditions must be met.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

First assume that you know where $A,B,C,D$ are. In this case, you can write $D$ uniquely in the form $\alpha_A A + \alpha_B B + \alpha_C C$, with $\alpha_A + \alpha_B + \alpha_C = 1$. The tuple $(\alpha_A,\alpha_B,\alpha_C)$ are called the barycentric coordinates of $D$. You can read off which of the segments $Dx$ ($x\in \{A,B,C\}$) cross a side of the triangle $ABC$ from the sign pattern of the barycentric coordinates.

It's not particularly difficult to find suitable coordinates either. You can just assume that $A=(0,0)$, $B=(d(A,B),0)$, and $C$ is either intersection point of the appropriate circles around $A$ and $B$. This will then uniquely determine $D$ by intersecting three circles.

Improve this answer
$\endgroup$
4
  • $\begingroup$ For me personally, OP's question and this answer has been particularly interesting. I would love to see a pseudo implementation. Do any exist off-the-shelf? If not, I will undertake an attempt myself. $\endgroup$
    – Auberon
    Mar 27, 2016 at 8:45
  • $\begingroup$ So, are the alphas vectors? Can you give an example of the sign patterns you refer? $\endgroup$
    – Picarus
    Mar 27, 2016 at 12:58
  • 1
    $\begingroup$ The $\alpha$s are numbers. How to get them is explained at the wikipedia link on barycentric coordinates. The sign pattern is just which of the $\alpha$s are positive and which are negative. (For example, all positive means inside the triangle $ABC$. Generally speaking, $\alpha_A > 0$ means that $D$ is on the same side of the line through $BC$ as $A$, etc.) $\endgroup$
    – Louis
    Mar 27, 2016 at 14:26
  • $\begingroup$ Thanks Louis, now that I have a bit more time to look at the links I find it highly useful. Do you know of any implementations of this? Java, Python, R would be great. I accept your answer as Best. $\endgroup$
    – Picarus
    Apr 14, 2016 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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