Хорошие и плохие стены

[Igors]

Добрый день

Надоело мелкотемье, вот задача которая давным-давно нужна, но все еще нет никаких идей как это сделать. Первый рисунок - все стены "хорошие", ребра в местах соприкосновения совпадают. Второй рисунок - дальняя (синий wireframe) "плохая". Требуется (просто-напросто) свести второй случай к первому, т.е. разбить зеленые и красные треугольники так чтобы новые ребра совпали с синими.

Доп требование: задается величина зазора. Напр синяя стена может быть приподнята, но если расстояние до красной не превышает зазор - все равно триангулировать красные треугольники.

Трудность в том что треугольников много (миллионы) и как искать "кто с кем" - хз. Хорошо известна немного др задача: булевские операции над полигонными объектами, есть хорошие open-sources. Но там рассматривается случай "пересеклось или нет", а не касание и тем более зазор, для картинок ниже никаких пересечений не будет найдено. Да, здесь можно использовать raytracer, хотя не видно зачем.

Есть мысли - поделитесь, хотите сделать за деньги - обсуждается, пишите в личку.

Спасибо