Пересечение многогранника прямой
В вычислительной геометрии задача вычисления пересечения многогранника прямой имеет важные приложения в компьютерной графике , оптимизации и даже в некоторых методах Монте-Карло . Ее можно рассматривать как трехмерную версию проблемы отсечения линий . [1]
Если многогранник задан как пересечение конечного числа полупространств , то можно разбить полупространства на три подмножества: те, которые включают только один бесконечный конец прямой, те, которые включают в себя другой конец, и те, которые включают в себя оба конца. Полупространства, включающие оба конца, должны быть параллельны данной прямой и не вносить вклад в решение. Каждое из двух других подмножеств (если оно непусто) вносит в пересечение одну конечную точку, которую можно найти, пересекая линию с каждой из граничных плоскостей полуплоскости и выбирая точку пересечения, ближайшую к концу полуплоскости. строка, содержащаяся полупространствами в подмножестве. Этот метод, вариант алгоритма Сайруса-Бека , требует времени, линейного в зависимости от количества граней входного многогранника. В качестве альтернативы, проверив линию на соответствие каждой из многоугольных граней данного многогранника, можно досрочно остановить поиск, когда будет найдена грань, пронизанная линией. [1]
Если один многогранник должен пересекаться со многими линиями, можно предварительно преобразовать многогранник в иерархическую структуру данных таким образом, чтобы пересечения с каждой строкой запроса можно было определять за логарифмическое время для каждого запроса. [2]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Колингерова, Ивана (1994), «Алгоритмы отсечения 3D-линий – сравнительное исследование», The Visual Computer , 11 (2): 96–104, doi : 10.1007/BF01889980 .
- ^ Добкин, Дэвид П .; Киркпатрик, Дэвид Г. (1983), «Быстрое обнаружение многогранного пересечения», Theoretical Computer Science , 27 (3): 241–253, doi : 10.1016/0304-3975(82)90120-7 , MR 0731064 .