Пересечение многогранника прямой - Википедия - Intersection of a polyhedron with a line

В вычислительная геометрия, проблема вычисления пересечение многогранника с линией имеет важные приложения в компьютерная графика, оптимизация, и даже в некоторых Методы Монте-Карло. Его можно рассматривать как трехмерную версию обрезка линии проблема.[1]

Если многогранник задан как пересечение конечного числа полупространства, то можно разделить полупространства на три подмножества: те, которые включают только один бесконечный конец линии, те, которые включают другой конец, и те, которые включают оба конца. Полупространства, включающие оба конца, должны быть параллельны данной линии и не вносить вклад в решение. Каждое из двух других подмножеств (если оно не пустое) вносит единственную конечную точку в пересечение, которое можно найти, пересекая линию с каждой из граничных плоскостей полуплоскости и выбирая точку пересечения, которая находится ближе всего к концу строка, содержащаяся в полупространствах в подмножестве. Этот метод, вариант Алгоритм Сайруса-Бека, занимает время, линейное по количеству плоскостей граней входного многогранника. В качестве альтернативы, проверяя линию на каждой из многоугольных граней данного многогранника, можно преждевременно остановить поиск, когда будет обнаружена грань, пронизанная линией.[1]

Если один многогранник должен быть пересечен множеством прямых, можно предварительно обработать многогранник в иерархическую структуру. структура данных таким образом, чтобы пересечения с каждой строкой запроса можно было определять в логарифмическом времени для каждого запроса.[2]

Рекомендации

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

внешняя ссылка