Прямоугольные ограничения в триангуляции Делоне без ребер внутри

Я использую библиотеку триангуляции, чтобы вычислить ограниченную триангуляцию Делоне для набора прямоугольников в пределах некоторой большой границы. Алгоритм возвращает все ребра, но также добавляет ребра внутри прямоугольников, которые определяют ограничения.

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

Я спрашиваю: есть ли какой-нибудь быстрый способ получить CDT, чтобы ребра не появлялись внутри какого-то многоугольника? Я хочу, чтобы прямоугольники были пустыми от краев, но я не уверен, как быстро это сделать.

В случае, если это поможет, библиотека, которую я использую, — это TriPath от Marcello Kallmann, и она написана на c ++ (http://graphics.ucmerced.edu/software/tripath/). Мое приложение на Java, и я использую JNI.

РЕДАКТИРОВАТЬ: В соответствии с просьбой, вот несколько изображений, которые помогут вам визуализировать то, что я пытаюсь описать. Этот CDT построен с черными линиями, являющимися ограничениями. Как видите, каждое ограниченное ребро является частью прямоугольника. Синие линии — безусловные края Делоне. Я пытаюсь удалить любые синие неограниченные края Делоне из черных ограниченных прямоугольников.