?

Log in

 
 
21 July 2006 @ 01:31 pm
Ну шо, программеры.  
Условие:
Есть прямоуголная область(картинка), в ней заданы координаты нескольких точек. По точкам производится разбиение на треугольники. Часть/все точки перемещаются на новые координаты.(т.е. выполняется морфинг картинки)

Задача:
Описать алгоритм разбиения на треугольники таким способом, чтобы ни до, ни после перетяжки на новые координаты не существовало пересечения сторон этих треугольников и не нарушался порядок обхода вершин каждого треугольника*.
Оценить затраты алгоритма на решение задачи.

* Имеется в виду чтобы при выполнении морфинга визуально треугольники не переворачивало на другую сторону.

Реализовывать наЯВУ не обязательно, можно и на пальцах.

Приз: Две бутылки Гиннеса или Две пачки сока Sandora или Jaffa круглых.
 
 
 
Festerfester_ua on July 21st, 2006 10:38 am (UTC)
Подумаем-с :)
Дон Карлосkastaneda on July 21st, 2006 10:42 am (UTC)
Хм. Будем ффтыкать. =)
Discovering Software Engineerfenikso on August 10th, 2006 12:05 pm (UTC)
Навскидку - если нет никаких ограничений на преобразование координат при морфинге, то алгоритм не существует.
Festerfester_ua on August 10th, 2006 03:11 pm (UTC)
Задача NP-полная, я это всегда утверждал. Но NP-полнота задачи не обозначает невозможность решения, она всего лишь утверждает отсутствие единственного эффективного метода решения. Т.е. перебором, к примеру, решить можно, но она будет работать до синих веников.
Discovering Software Engineerfenikso on September 4th, 2006 11:24 pm (UTC)
кстати, алгоритм морфинга и все параметры преобразования системы координат - на входе задачи известны? или предлагается построить Великое Разбиение? (такого несуществует - при любом наперёд заданном разбиении я могу подкрутить морфинг так, чтобы он ломал картинку)
Bruce Weirdanweirdan on August 11th, 2006 07:47 am (UTC)
если под "по точкам производится разбиение на треугольники" означает, что точки являются вершинами треугольников, и ограничений на морфинг не существует, то (начиная с нек. количества точек) искомого алгоритма разбиения не существует.

Доказывается от противного.