algorithm - jarvis - Algoritmo asintóticamente óptimo para calcular si una línea cruza un polígono convexo

divide and conquer convex hull python (5)

Creo que este artículo da una solución clara O (log n). Encuentra los extremos en la dirección perpendicular a la línea dada.

Un algoritmo O (n) para detectar si una línea se interseca con un polígono convexo consiste en verificar si algún borde del polígono se interseca con la línea, y ver si el número de intersecciones es impar o par.

¿Existe un algoritmo asintóticamente más rápido, por ejemplo, uno O (log n)?

La respuesta de lhf es casi correcta. Aquí hay una versión que debería solucionar el problema con la suya.

Deje que el polígono tenga vértices v0, v1, ..., vn en el orden contrario a las agujas del reloj. Deje los puntos x0 y x1 en la línea.

Tenga en cuenta dos cosas: primero, puede encontrar la intersección de dos líneas (y determinar su existencia) en un tiempo constante. En segundo lugar, determinar si un punto está a la izquierda o a la derecha de una línea se puede hacer en tiempo constante.

Seguiremos la misma idea básica de lhf para obtener un algoritmo O (log n). Los casos base son cuando el polígono tiene 2 o 3 vértices. Ambos pueden ser manejados en tiempo constante.

Determine si la línea (v0, v (n / 2)) cruza la línea (x0, x1).

Caso 1: No se entrecruzan.

En este caso, la línea en la que estamos interesados es a la izquierda o a la derecha de la línea que divide el polígono, por lo que podemos ocupar esa mitad del polígono. Específicamente, si x0 está a la izquierda de (v0, v (n / 2)) entonces todos los vértices en la "mitad" derecha, {v0, v1, ... v (n / 2)} están en el mismo lado de (x0, x1) y así sabemos que no hay intersección en esa "mitad" del polígono.

Caso 2: Se intersectan.

Este caso es un poco más complicado, pero aún podemos reducir la intersección a una "mitad" del polígono en tiempo constante. Hay 3 subcasas:

Caso 2.1: La intersección se encuentra entre los puntos v0 y v (n / 2)

Hemos terminado. La línea intersecta el polígono.

Caso 2.2: La intersección está más cerca de v0 (es decir, fuera del polígono en el lado de v0)

Determine si la línea (x0, x1) se interseca con la línea (v0, v1).

Si no lo hace, entonces hemos terminado, la línea no se cruza con el polígono.

Si lo hace, encuentra la intersección, p. Si p está a la derecha de la línea (v0, v (n / 2)), vuelva a ocupar la "mitad" derecha del polígono, {v0, v1, ..., v (n / 2)}, de lo contrario a la izquierda "half" {v0, v (n / 2), ... vn}.

La idea básica en este caso es que todos los puntos en el polígono están a un lado de la línea (v0, v1). Si (x0, x1) se aleja de (v0, v1) en un lado de su intersección con (v0, v (n / 2)). Sabemos que en ese lado no puede haber intersección con el polígono.

Caso 2.3: La intersección está más cerca de v (n / 2)

Este caso se maneja de manera similar al caso 2.2, pero usando el vecino apropiado de v (n / 2).

Hemos terminado. Para cada nivel, esto requiere dos intersecciones de línea, una comprobación de izquierda a derecha y la determinación de dónde está un punto en una línea. Cada recursión divide el número de vértices por 2 (técnicamente los divide por al menos 4/3). Y así obtenemos un tiempo de ejecución de O (log n).

Los cuadros delimitadores pueden resultar útiles.

Recuerde que una parte convexa de un espacio afín es la intersección de todos los hiperplanos de su envolvente: puede obtener una aproximación de su polígono (lea un "polígono convexo delimitador") considerando solo la intersección de un subconjunto de los hiperplanos de la envolvente. intersección de su línea con esta aproximación, y refinar si es necesario.

Todo esto funciona mejor si espera un número bajo de intersecciones.

Solo necesita encontrar un punto A que esté en el lado izquierdo de la línea y otro punto que esté en el lado derecho. La pregunta restante es cómo encontrar esos puntos rápidamente.

toma al azar dos puntos A y B del polígono convexo.

si están en un lado diferente de la línea, se intersecan
si están en el mismo lado, en ambas partes de poligon (digamos AB y BA en el sentido de las agujas del reloj) haga:
- Crea una línea paralela a tu línea l que pase por A
- encuentre el punto a una distancia máxima de 1 en el polígono, que es lo mismo que encontrar el máximo en la función que primero es monotónico, no disminuye y luego, monótonamente, no aumenta. Esto se puede hacer en O (log n) por búsqueda ternaria

Si esos dos puntos más lejanos están en el lado diferente de su línea, la línea se cruza con poligon, de lo contrario no

Por cierto, también puede encontrar puntos de intersección reales en O (log n).