Получите горизонт для точки во время инкрементального выпуклого корпуса 3D

Я реализую добавочный CH 3D в C ++ с помощью Qt, но я не могу преодолеть эту проблему:

Я должен найти горизонт обзора данной точки:

горизонт

У меня есть Карта со списком всех видимых граней данной точки «pr», но я не знаю, как получить только горизонт без изменения сложности алгоритма (это O (nlogn)).

Моя идея заключалась в том, чтобы: по краям всех видимых лиц проверить, является ли видимое лицо близнеца видимым или нет. Если он не виден, то добавьте его в список границ горизонта, но сложность алгоритма этого изменения (я думаю).

Обратите внимание, что у меня есть другой список, где у меня есть набор всех точек, которые могут просматривать данное лицо (возможно, это помогает).

Действительно спасибо заранее

2

Решение

Если у вас есть только выпуклые многогранники, ваша идея должна это сделать (это сложность O (1), у вас уже есть результаты). Да, вы бы сделали дополнительный поиск со сложностью O (n).

1

Другие решения

Других решений пока нет …