# How to detect intersecting segments based on length of the segments

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}

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.

## 1 Answer

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.

• 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. Mar 27, 2016 at 8:45
• So, are the alphas vectors? Can you give an example of the sign patterns you refer? Mar 27, 2016 at 12:58
• 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.) Mar 27, 2016 at 14:26
• 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. Apr 14, 2016 at 2:30