Decidir eficientemente si alguno de un conjunto de cilindros en 3 espacios se interseca

Question

Digamos que tengo un set $C$ $N$ cilindros en un espacio de 3 dimensiones, $(c_1, ..., c_N) \in C$, donde cada uno de los cilindros, $c_i$, tiene asociado un radio de $r_i$ y dos coordenadas de la especificación de los extremos del segmento de recta que representa a su eje de simetría, $(x_{i,1},y_{i,1},z_{i,1})$ & $(x_{i,2},y_{i,2},z_{i,2})$.

¿Cómo puedo decidir rápidamente si la unión de volumen de los cilindros es igual a la suma de los volúmenes de los cilindros individuales? En otras palabras, ¿cómo puedo verificar rápidamente o refutar la existencia de una intersección entre dos cilindros? Me gustaría destacar que me refiero a esto como un problema de decisión - no estoy pidiendo un explícito de la unión cálculo de volumen o una manera de encontrar los puntos de intersección.

Answer 1

La unión en sí es bastante complicado, y ha sido el objeto de estudio de la geometría computacional. Por ejemplo, recientemente, fue establecido por Ester, Esdras que la unión es casi cuadrática en tamaño: "En la Unión de los Cilindros en Tres Dimensiones." Pero debido a que usted sólo desea decidir si una pareja se cruza, parece que el mejor método es simplemente revise todos los pares, y evitar la unión. Esta será una ecuación cuadrática algoritmo. Creo que no sería fácil para alcanzar subquadratic tiempo de complejidad. Por supuesto, usted puede pre-check para evitar el cálculo de que si, por ejemplo, su las cajas de contorno no se intersecan. Así que parece que su pregunta se reduce a: Cómo se cruzan un par de cilindros.

Ya no pido que, tal vez usted ya sabe que problema? Es fácil si los cilindros son infinitas, para, a continuación, se trata simplemente de informática de la la distancia entre sus ejes. Es necesario trabajar más cerca de los tapones para finito de cilindros. Ciertamente, si la distancia entre sus ejes supera la suma de sus radios, no se intersecan.

Afortunadamente, Dave Eberly de Herramientas Geométricas ha investigado este cilindro-cilindro la pregunta de fondo, en su documento "Intersección de Cilindros": PDF enlace.