Segmento de línea de contenedores para una rápida intersección Ray? (2D)

Question

Tengo un rayo, necesito encontrar el segmento de línea más cercano que golpea. Creo que es posible hacer esto en O (log n) tiempo si puedo ordenar primero los segmentos de línea, pero no puedo recordar cómo ordenar ellos ... Creo que una especie de árbol que funcionaría mejor, pero ¿Cómo puedo ordenar ellos por tanto inicial y el punto final? También me gustaría inserciones rápidas en esta estructura de datos, si es posible.

Hay un montón de código para un rayo contra un segmento de línea, pero necesito algo por un rayo vs muchos segmentos de línea ... No sé qué términos a Google para.

Un enlace a un artículo apropiado es buena, código C ++ es aún mejor. ¡Gracias! :)

PS: Los segmentos de línea son en realidad los bordes de un polígono no autointerseca, ordenados en orden CCW ... pero creo que puede haber alguna ventaja para ordenarlas de una manera diferente

Esto es todo 2D.

---

En el segundo pensamiento, no estoy del todo seguro de que este es posible. Algún tipo de partición espacial podría ayudar, pero por lo demás, no puedo pensar en ninguna manera de ordenar las líneas de modo que pudieran ser comparados con un rayo arbitrario.

Answer 1

Usted podría tomar un recuadro de delimitación del polígono (x min-max, las coordenadas Y) y construir una red dentro de la caja. Luego, para cada celda, recuerde todas las líneas que atraviesan la célula.

Encontrar un intesection como esto:

• Para saber qué celda el rayo golpea primero (O (1))
• Uso cuadrícula traversal algoritmo para "dibujar" un rayo a través de la rejilla . Al llegar a la célula que no está vacía, todas sus líneas, comprobar si la intersección está dentro de la célula y recoge la intersección más cercana. Si todas las intersecciones son fuera de la célula, continuar (esto es O (longitud grid)).

También puede hacer que la rejilla jerárquica (es decir, árbol cuádruple -. Una árbol que estaban pidiendo), y caminar usando el mismo algoritmo. Esto se hace en el trazado de rayos en 3D y la complejidad del tiempo es O (sqrt ( N)).

---

O, utilice el enfoque que hice en mi trazador de rayos:

• árbol cuádruple que contiene las líneas (edificio árbol cuádruple está en el desribed artículo) - dividir nodos (= áreas) si contienen demasiados objetos en 4 sub-nodos (subáreas)

• Recoge todas nodos hoja del árbol de cuatro ramas que están alcanzado por el rayo:

  Calcular intersección de rayos-rectángulo (no es difícil) para la raíz. Si la raíz es golpeado por el rayo, proceder con sus hijos de forma recursiva.

Lo bueno de esto es que cuando un nodo del árbol es no golpe, te has saltado el procesamiento de sub-árbol entero (potencialmente una gran área rectangular).

Al final, esto es equivalente a atravesar la red - recoja las células más pequeñas en la trayectoria del rayo, y luego probar todos los objetos en ellos para la intersección. Sólo tienes que probar todos ellos y recoger la intersección más cercana (por lo que explorar todas las líneas en la trayectoria del rayo).

Este es O (sqrt (N)).

En el recorrido rejilla, cuando se encuentra una intersección, se puede detener la búsqueda. Para lograr esto con el recorrido árbol cuádruple, que tendría que seach los niños en el orden correcto - o bien ordenar los 4 intersecciones rect por la distancia o inteligentemente atravesar la rejilla de 4 celdas (una volvemos a atravesar)

.

Esto es sólo un enfoque diferente, comparativamente misma difíciles de implementar que pienso, y funciona bien (he comprobado en datos reales - O (sqrt (N))). Una vez más, sólo se beneficiarán de este enfoque si tiene al menos un par de líneas, cuando el polígono tiene 10 bordes del beneficio en comparación con sólo probar todos ellos sería poco creo.

Answer 2

¿Está buscando métodos borde de la mesa de línea de exploración / activo basado? Puede echar un vistazo a la entrada de Wikipedia para Scanline representación o buscar en la directorio de gráficos Gems para los algoritmos (principalmente C, pero algo de código C ++ también) .

Answer 3

Tenga en cuenta que la clasificación es un O (n log n) la operación en el mejor. Usted puede ser mejor simplemente comprobando cada uno individualmente.

Answer 4

¿Cómo está usted seguro de que llegarás a alguna de ellas? Si son líneas, es poco probable.

Si es realmente un polígono (es decir, plana) que usted está tratando de probar, la forma habitual de hacer este tipo de cosas es intersecta con el plano primero, y luego probar ese punto (en las coordenadas 2D) para interior / exterior polígono.

Tal vez no he entendido bien lo que estás haciendo realmente.

En las intersecciones de aceleración generales con figuras complejas se realiza con particionamiento espacial (y luego técnicas como de encasillado, si sus pruebas son caros).

[Actualización: Me leído mal la intención original] Puede seguir utilizando (2d) de partición espacial, sino la sobrecarga puede no valer la pena. prueba individual son baratos, si los polígonos no son complicados podría ser más barato para simplemente caminar ellos. Es difícil de decir de la descripción.

Answer 5

pedir una aclaración, es esto correcto?

• Usted tiene un conjunto dinámico de segmentos de línea L .
• Consulta: dada cualquier punto (x, y) y e cualquier dirección del rayo desde este punto, se desea determinar la línea más cercana en L (si los hay)?

Así que el punto (x, y) se soluciona? (Podría ser cualquier punto, y cualquier dirección?)