En geometría computacional , el problema de calcular la intersección de un poliedro con una línea tiene aplicaciones importantes en gráficos por computadora , optimización e incluso en algunos métodos de Monte Carlo . Puede verse como una versión tridimensional del problema de recorte de líneas . [1]
Si el poliedro se da como la intersección de un número finito de medios espacios , entonces se pueden dividir los medios espacios en tres subconjuntos: los que incluyen solo un extremo infinito de la línea, los que incluyen el otro extremo y los que incluyen ambos extremos. Los medios espacios que incluyen ambos extremos deben ser paralelos a la línea dada y no contribuyen a la solución. Cada uno de los otros dos subconjuntos (si no está vacío) contribuye con un único punto final a la intersección, que se puede encontrar intersecando la línea con cada uno de los planos de contorno de semiplano y eligiendo el punto de intersección más cercano al final de la línea. línea contenida por los medios espacios en el subconjunto. Este método, una variante del algoritmo de Cyrus-Beck, toma tiempo lineal en el número de planos faciales del poliedro de entrada. Alternativamente, probando la línea contra cada una de las facetas poligonales del poliedro dado, es posible detener la búsqueda antes de tiempo cuando se encuentra una faceta perforada por la línea. [1]
Si un solo poliedro debe intersecarse con muchas líneas, es posible preprocesar el poliedro en una estructura de datos jerárquica de tal manera que las intersecciones con cada línea de consulta se puedan determinar en tiempo logarítmico por consulta. [2]
Referencias
- ^ a b Kolingerová, Ivana (1994), "Algoritmos de recorte de líneas 3D: un estudio comparativo", The Visual Computer , 11 (2): 96-104, doi : 10.1007 / BF01889980.
- ^ Dobkin, David P .; Kirkpatrick, David G. (1983), "Detección rápida de intersección poliédrica", Informática teórica , 27 (3): 241-253, doi : 10.1016 / 0304-3975 (82) 90120-7 , MR 0731064.