В настоящее время я работаю над инструментом рендеринга ландшафта. Мне нужно отрезать кусок от заданной триангуляции Делоне. Предположим, что дана следующая триангуляция:
Красный квадрат показывает область, которую нужно вырезать из исходной триангуляции, т. е. найти субтриангуляцию, которая имеет те же точки, что и исходная триангуляция, плюс точки на границе квадрата.
Есть ли какой-нибудь эффективный алгоритм для выполнения такого разреза?