How to check if polylines can be untangled?

Question

In a program I'm writing I need to be able to check whether a straight line between two points is homotopic to a polyline between them. For example in the below example the first one is equivalent to a straight line between the circles, but the second one is not.

I have tried to check if the obstacles are inside or outside the polygon, but it is not sufficient, since in the following case the obstacles are both outside the polygon, but the line is still not 'untangible':

I have also tried to look at the direction in which the line runs around an obstacle, but it seems to me that from the perspective of obstacle '2', the first two examples are indistinguishable.

Do you know any algorithms for doing the above check?

Update: I should probably mention that the intended answers for the following simple examples are 'no' and 'yes':

Update 2: This is why the "all windings numbers = 0" method doesn't work:

Answer 1

I think the proper answer is do it the hard way.

One should compute the element in the fundamental group $\pi_1$ associated with the polygon obtained by completing your polyline. For $n$ point obstacles over $\mathbb{R}^2$, the hard way isn't that hard at all.

Let $A = \{\; a_1, a_2, \ldots, a_n\;\}$ be $n$ point obstacles in $\mathbb{R}^2$. Let $B = \{\; p_1, p_2, \ldots, p_m\;\}$ be the vertices of your polyline. Since both $A$ and $B$ are finite, there are points that didn't lie on any of the lines spanned by elements of $A \cup B$. Pick one of this as the origin $O$ and the base point for the fundamental group $\pi_1(\mathbb{R}^2 \setminus A)$ we are going to deal with.

For any point $x \in \mathbb{R^2} \setminus \{ O \}$, let $\theta(x)$ be its angle in polar coordinate system. We will assume $a_i$ are ordered in a way such that: $$0 \le \theta(a_1) < \theta(a_2) < \ldots < \theta(a_n) < 2\pi$$

For any $r$ points $u_1, u_2, \ldots u_r \in \mathbb{R^2} \setminus A$, we will use the notation $\overline{ u_1 u_2 \ldots u_r}$ to denote both the closed polygonal path with vertices $u_i$ in that order and the corresponding element in $\pi_1(\mathbb{R}^2 \setminus A)$. For any $a_i \in A$, we will use $\bar{a}_i$ to represent a loop looping around $a_i$ once in counter-clockwise direction. For the loop looping around $a_i$ once in clockwise direction, we will use the notation $\bar{a}_i^{-1}$ instead.

For the polygon obtained by completing your poly-line, its correspond element in $\pi_1$ has following breakdown:

$$\overline{p_1 p_2 \ldots p_m} = \overline{O p_1 p_2 \ldots p_m p_1} = \overline{O p_1 p_2}\;\overline{O p_2 p_3} \cdots \overline{O p_m p_1} $$

Let's look at one of these triangles $\overline{Op_ip_{i+1}}$. For simplicity, let us consider the case the interior of it is disjoint from the positive $x$-axis. If $a_{j_1}, a_{j_2}, \ldots, a_{j_{s(i)}}$ are elements of $A$ "inside" $\overline{Op_ip_{i+1}}$ sorted according to its angle, then

$$\overline{Op_ip_{i+1}} = \begin{cases} \bar{a}_{j_1}\;\bar{a}_{j_2}\;\cdots\;\bar{a}_{j_{s(i)}} &\text{ if } \theta(p_i) < \theta(p_{i+1})\\ \bar{a}_{j_{s(i)}}^{-1}\;\cdots\;\bar{a}_{j_2}^{-1}\;\bar{a}_{j_1}^{-1}, &\text{ if } \theta(p_i) > \theta(p_{i+1})\\ \end{cases} $$ In general, one can read off the element corresponds to the polygon by collecting all $\bar{a}_j$ or $\bar{a}_j^{-1}$ in the triangles $\overline{Op_ip_{i+1}}$, sort them in appropriate order and "multiply" them together.

The fundamental group $\pi_1(\mathbb{R}^2 \setminus A)$ is a free group generated by the loops $\bar{a}_i$. In any product of $\bar{a}_i$ and $\bar{a}_j^{-1}$, the only cancellation allowed is replacing nearby $\bar{a}_i \bar{a}_i^{-1}$ or $\bar{a}_i^{-1} \bar{a}_i$ to identity. If and only if all $a_i$ can be cancelled in this manner, the product becomes the "trivial loop" and one can untangle your poly-line.

Using your untangleable case as an example

$a$ and $b$ there are your point obstacles. Your poly-line corresponds to polygon $\overline{p_1 p_2\ldots p_{12}}$. Among all the triangles $\overline{Op_ip_{i+1}}$, only three of them contains $a$ and/or $b$:

• $\overline{Op_2p_3}$ contains $b$ and $\theta(p_2) > \theta(p_3)$, this give us a factor $\bar{b}^{-1}$.
• $\overline{Op_6p_7}$ contains $a$ and $\theta(p_6) > \theta(p_7)$, this give us a factor $\bar{a}^{-1}$.
• $\overline{Op_{10}p_{11}}$ contains both $a$ and $b$. Since $\theta(p_{10}) < \theta(p_{11})$ and $\theta(b) < \theta(a)$, this leads to a factor $\bar{b}\bar{a}$.

As a result, the poly-line in your example corresponds to a non-trivial element $\bar{b}^{-1} \bar{a}^{-1} \bar{b}\bar{a}$ in $\pi_1(\mathbb{R}\setminus A)$ and hence cannot be untangled.

Please note that in your example, if one form the free abelian group from $\bar{a}$ and $\bar{b}$ instead of the free group, the expression $\bar{b}^{-1} \bar{a}^{-1} \bar{b}\bar{a}$ can be reduced to identity. This corresponds to the fact the winding numbers of your polygon w.r.t to both $a$ and $b$ vanish.

Answer 2

By adding a straight line from end point to start point, you get a closed polyline. A first check woul dbe to compute the winding number around any obstacle, but that is not enough! It is possible that removing either of the obstacles makes the line untanglable, but with all obstacles present it is not (see your top right example).

So the thing I'd suggest is: Try to actually untangle. That is, repeatedly look for vertices $b$ such that the triangle $abc$ given by it and its two neighbours $a,c$ has no obstacles in its interior (I assume for simplicity that all points are in general position, i.e. no three collinear) and if so replace $ab, bc$ with the shortcut $ac$. Repeat until either we have reached the straight line or no such vertex exists.

Does this work or is ot possible for a polyline to actually be untanglable but to have an obstacle in each such triangle? The asnwer is: It does work, but it is not as obvious as it seems.

Edit: On second thought, this is really not obvious simply because it is wrong in this form:

I'm afraid one has to consider refinements of the polyline, so I'm still rethinking this. It looks like adding redundant vertices wherever the direct line intersects th epolyline resolves this, but I'm still not sure and prefer achille_hui's approach ..