algorithm - tunear - Encontrar el camino recto vacío más ancho a través de un conjunto de puntos

motos ruckus mexico

Question

Estoy creando un juego simple y presenté este problema al diseñar AI para mi juego: dado un conjunto de N puntos dentro de un rectángulo en la coordenada cartesiana, necesito encontrar la ruta más ancha a través de este rectángulo. La ruta debe estar vacía (es decir, que no contiene ningún punto).

Me pregunto si hay algún algoritmo eficiente para resolver este problema. ¿Puede sugerir alguna palabra clave / documento / algo relacionado con este problema?

EDITAR: El rectángulo siempre está definido por 4 puntos en su esquina. Agregué una imagen para ilustración. el camino en las imágenes de arriba es el determinado por dos líneas rojas

Answer 1

Este es el problema más amplio del corredor vacío. Houle y Maciel dieron un algoritmo O (n ² ) -time, O (n) -space en un informe técnico de 1988 titulado "Encontrar el corredor vacío más ancho a través de un conjunto de puntos", que parece no estar disponible en línea. Afortunadamente, Janardan y Preparata describen este algoritmo en la Sección 4 de sus problemas en papel de Pasillo más amplio , que está disponible.

Answer 2

Pasa por todos los pares de puntos. Construye una línea l a través del par. (^ 1) En cada lado de l , o hay otros puntos, o no. Si no, entonces no hay un camino en ese lado de l . Si hay otros puntos, recorra los puntos calculando la distancia perpendicular d desde l hasta cada punto. Registre el mínimo d . Ese es el camino más amplio en ese lado de l . Continúe recorriendo todos los pares, comparando la ruta más ancha para ese par con la ruta más ancha anterior.

Este algoritmo puede considerarse ingenuo y se ejecuta en O(n^3) tiempo.

Editar: el algoritmo anterior pierde un caso. En ^ 1 arriba, inserte: "Construye dos líneas perpendiculares a l a través de cada punto del par. Si no hay un tercer punto entre las líneas, registra la distancia d entre los puntos. Esto constituye un camino". Continúa el algoritmo en ^ 1. Con caso adicional, el algoritmo sigue siendo O(n^3)

Answer 3

Yo mismo, comenzaría mirando la triangulación de Delaunay del conjunto de puntos: http://en.wikipedia.org/wiki/Delaunay_triangulation

Parece que hay muchos recursos allí en algoritmos eficientes para construir esto - el algoritmo de Fortune, en O (n log n), para los principiantes.

Mi intuición me dice que tu camino más ancho estará definido por uno de los bordes de este gráfico (es decir, que se extendería perpendicularmente al borde, y su ancho sería igual a la longitud del borde). Cómo ordenar los bordes, verificar los candidatos e identificar la ruta más ancha que queda. Me gusta esta pregunta, y voy a seguir pensando en eso. :)

EDITOR 1: ¡Mi intuición me falla! Un simple triángulo equilátero es un contraejemplo: la trayectoria más ancha es más corta que cualquiera de los bordes de la triangulación. Sigue pensando...

EDIT 2: Entonces, necesitamos un algoritmo de caja negra que, dados dos puntos en el conjunto, encuentre la ruta más ancha a través del conjunto de puntos que está limitado por esos dos puntos. (Visualice dos líneas paralelas que atraviesan los dos puntos, rótelas en armonía entre sí hasta que no haya puntos entre ellas). Vamos a llamar el tiempo de ejecución de este algoritmo ''R''.

Dado tal algoritmo, podemos hacer lo siguiente:

1. Construya la triangulación de Delaunay del conjunto de puntos: O (n log n)
2. Clasifique los bordes por ancho: O (n log n)
3. Comenzando con el borde más grande y moviéndose hacia abajo, use el algoritmo de recuadro negro para determinar el camino más ancho que involucre esos dos puntos; almacenándolo como X: O (nR))
4. Deténgase cuando el borde que se está examinando sea más corto que el ancho de X.

Los pasos 1 y 2 son agradables, pero el O (nR) es un poco aterrador. Si R resulta ser O (n), eso ya es O (n ^ 2) para todo el algoritmo. Lo bueno es que, para un conjunto general de puntos aleatorios, esperaríamos que no tuviéramos que pasar por todos los bordes.