¿Cómo comprobar si las polilíneas se pueden desenredar?

Question

En un programa que estoy escribiendo necesito poder comprobar si una recta entre dos puntos es homotópica a una polilínea entre ellos. Por ejemplo en el siguiente ejemplo la primera es equivalente a una línea recta entre los círculos, pero la segunda no lo es.

He intentado comprobar si los obstáculos están dentro o fuera del polígono, pero no es suficiente, ya que en el siguiente caso los obstáculos están ambos fuera del polígono, pero la línea sigue sin ser "intangible":

También he intentado fijarme en la dirección en la que la línea recorre un obstáculo, pero me parece que desde la perspectiva del obstáculo "2", los dos primeros ejemplos son indistinguibles.

¿Conoces algún algoritmo para hacer la comprobación anterior?

Actualización: Probablemente debería mencionar que las respuestas previstas para los siguientes ejemplos sencillos son "no" y "sí":

Actualización 2: Por eso no funciona el método de "todos los números de devanados = 0":

Answer 1

Creo que la respuesta adecuada es hacerlo por las malas.

Hay que calcular el elemento en el grupo fundamental $\pi_1$ asociado al polígono obtenido al completar su polilínea. Para $n$ obstáculos puntuales sobre $\mathbb{R}^2$ El camino difícil no es tan difícil en absoluto.

Dejemos que $A = \{\; a_1, a_2, \ldots, a_n\;\}$ sea $n$ obstáculos puntuales en $\mathbb{R}^2$ . Sea $B = \{\; p_1, p_2, \ldots, p_m\;\}$ sean los vértices de su polilínea. Dado que ambos $A$ y $B$ son finitos, hay puntos que no se encuentran en ninguna de las líneas abarcadas por elementos de $A \cup B$ . Elige uno de estos como origen $O$ y el punto base para el grupo fundamental $\pi_1(\mathbb{R}^2 \setminus A)$ que vamos a tratar.

Para cualquier punto $x \in \mathbb{R^2} \setminus \{ O \}$ , dejemos que $\theta(x)$ sea su ángulo en el sistema de coordenadas polares. Supondremos que $a_i$ están ordenados de tal manera que: $$0 \le \theta(a_1) < \theta(a_2) < \ldots < \theta(a_n) < 2\pi$$

Para cualquier $r$ puntos $u_1, u_2, \ldots u_r \in \mathbb{R^2} \setminus A$ utilizaremos la notación $\overline{ u_1 u_2 \ldots u_r}$ para denotar tanto la poligonal cerrada cerrado con vértices $u_i$ en ese orden y el elemento correspondiente en $\pi_1(\mathbb{R}^2 \setminus A)$ . Para cualquier $a_i \in A$ utilizaremos $\bar{a}_i$ para representar un bucle que se extiende alrededor de $a_i$ una vez en sentido contrario a las agujas del reloj. Para el bucle que da vueltas $a_i$ una vez en el sentido de las agujas del reloj, utilizaremos la notación $\bar{a}_i^{-1}$ en su lugar.

Para el polígono obtenido al completar su polilínea, su elemento correspondiente en $\pi_1$ tiene el siguiente desglose:

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

Veamos uno de estos triángulos $\overline{Op_ip_{i+1}}$ . Para simplificar, consideremos el caso de que el interior de la misma sea disjunta del positivo $x$ -eje. Si $a_{j_1}, a_{j_2}, \ldots, a_{j_{s(i)}}$ son elementos de $A$ "dentro" $\overline{Op_ip_{i+1}}$ ordenados según su ángulo, entonces

$$\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} $$ En general, se puede leer el elemento correspondiente al polígono recogiendo todos los $\bar{a}_j$ o $\bar{a}_j^{-1}$ en los triángulos $\overline{Op_ip_{i+1}}$ , clasifícalos en el orden apropiado y "multiplícalos" juntos.

El grupo fundamental $\pi_1(\mathbb{R}^2 \setminus A)$ es un grupo libre generado por los bucles $\bar{a}_i$ . En cualquier producto de $\bar{a}_i$ y $\bar{a}_j^{-1}$ la única anulación permitida es la sustitución de los vecinos $\bar{a}_i \bar{a}_i^{-1}$ o $\bar{a}_i^{-1} \bar{a}_i$ a la identidad. Si y sólo si todos $a_i$ puede cancelarse de esta manera, el producto se convierte en el "bucle trivial" y uno puede desenredar su polilínea.

Utilizando su caso de desenredo como ejemplo

$a$ y $b$ ahí están sus obstáculos puntuales. Su polilínea corresponde al polígono $\overline{p_1 p_2\ldots p_{12}}$ . Entre todos los triángulos $\overline{Op_ip_{i+1}}$ Sólo tres de ellos contienen $a$ y/o $b$ :

• $\overline{Op_2p_3}$ contiene $b$ y $\theta(p_2) > \theta(p_3)$ Esto nos da un factor $\bar{b}^{-1}$ .
• $\overline{Op_6p_7}$ contiene $a$ y $\theta(p_6) > \theta(p_7)$ Esto nos da un factor $\bar{a}^{-1}$ .
• $\overline{Op_{10}p_{11}}$ contiene tanto $a$ y $b$ . Desde $\theta(p_{10}) < \theta(p_{11})$ y $\theta(b) < \theta(a)$ Esto lleva a un factor $\bar{b}\bar{a}$ .

En consecuencia, la polilínea de su ejemplo corresponde a un elemento no trivial $\bar{b}^{-1} \bar{a}^{-1} \bar{b}\bar{a}$ en $\pi_1(\mathbb{R}\setminus A)$ y por lo tanto, no se puede desenredar.

Tenga en cuenta que en su ejemplo, si uno forma el grupo abeliano libre de $\bar{a}$ y $\bar{b}$ en lugar del grupo libre, la expresión $\bar{b}^{-1} \bar{a}^{-1} \bar{b}\bar{a}$ puede reducirse a la identidad. Esto se corresponde con el hecho de que los números de enrollamiento de su polígono con respecto a ambos $a$ y $b$ desaparecer.

Answer 2

Añadiendo una línea recta desde el punto final al punto inicial, se obtiene una polilínea cerrada. Una primera comprobación sería calcular el número de vueltas alrededor de cualquier obstáculo, ¡pero eso no es suficiente! Es posible que al eliminar o bien de los obstáculos hace que la línea sea imposible de cruzar, pero con todos los obstáculos presentes no lo es (ver tu ejemplo de arriba a la derecha).

Así que lo que yo sugeriría es: Tratar de desenredar realmente. Es decir, buscar repetidamente los vértices $b$ tal que el triángulo $abc$ dado por él y sus dos vecinos $a,c$ no tiene obstáculos en su interior (asumo por simplicidad que todos los puntos están en posición general, es decir, no hay tres colineales) y si es así sustituye $ab, bc$ con el acceso directo $ac$ . Repite la operación hasta que hayamos alcanzado la línea recta o no exista tal vértice.

¿Funciona esto o es posible que una polilínea sea realmente inalcanzable pero que tenga un obstáculo en cada uno de esos triángulos? La respuesta es: sí funciona, pero no es tan obvio como parece.

Editar: Pensándolo bien, esto no es realmente obvio simplemente porque está mal en esta forma:

Me temo que hay que tener en cuenta los refinamientos de la polilínea, por lo que todavía me lo estoy replanteando. Parece que la adición de vértices redundantes donde la línea directa se cruza con la epolínea resuelve esto, pero todavía no estoy seguro y prefiero el enfoque de achille_hui