Кто-нибудь знает какие-либо алгоритмы (ссылка на исследовательскую статью, если вы знаете), которые создают ограниченную триангуляцию с задержкой в O (nlogn) и любые алгоритмы, позволяющие удалить и добавление ограничений и вершин, которые не требуют повторного вычисления всего CDT?Fast (O (nlogn)) Ограниченные алгоритмы триангуляции Delaunay
Chew 1989 представляет алгоритм для генерации CDT O(nlogn), равно как и Sloan 1992. Я нахожу алгоритм Слоана легче, но ваш пробег может отличаться.
Для динамических обновлений лучший алгоритм, который я знаю, представлен Kallmann et al. IIRC их алгоритм довольно чувствителен к числу ограничений, и поэтому не подходит для, например, pathfinding в мире, подобном Minecraft, где пространство ограничений велико и очень динамично.
Все эти документы охватывают двумерные пространства; если вы хотите это в 3D, я подозреваю, что вам придется сделать некоторые оригинальные исследования. В любом случае, удачи.
Я только что нашел, что бумага Каллмана! Я использую это для создания navmesh для игры RTS, поэтому количество ограничений останется довольно маленьким (<1000, скорее всего). Спасибо за ресурсы, ты огромная плохая задница – zaloo