Russian Qt Forum

Добрый вечер

Есть N вершин (точек в пр-ве) каждая знает с какими др вершинами она соединена, т.е. ребра известны. Нужно как-то удалить некоторые ребра так чтобы бредовая картинка (аттач) приобрела божеский вид. Новые ребра создавать нельзя. Конечно получить корректную поверхность было бы просто замечательно, но это вряд ли достижимо. Нужно просто "поприличнее".

Слушаю Ваши предложения

Спасибо

понятия «божеский вид» и «поприличнее» от математики довольно далёки. что конкретно нужно? (выпуклая оболочка вряд ли как я понимаю) что планируется делать с графом в дальнейшем?

Много чего, следующий шаг - разбиение некоторых ребер графа (используя значения записанные в вершинах).

Так ведь здесь "форум программистов" :) Ладно, давайте определим что такое "корректная поверхность"

- ребра не пересекаются
- любой внутренний контур имеет 3 ребра

Т.е просто нормальная 3D модель, mesh. Такой идеальный результат конечно желателен, но необязателен. Если будут пересечения (в разумных пределах) - переживу. Конечно можно продолжать придираться "а что такое в разумных пределах?" - но это не конструктивно.

Для планарных, помню есть "метод Сигуиямы" (http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CDgQFjAD&url=http%3A%2F%2Fsydney.edu.au%2Fengineering%2Fit%2F~visual%2Fcomp4048%2Fslides03.ppt&ei=RbaTUNj9Gaen4gTi7oFI&usg=AFQjCNE4FJlFlXOVvpneNmgMDYbGv3TN2Q&sig2=2lxpEuhlfcvD_2W74nrTcg&cad=rjt).

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

Да, и почему не слышно типовых "посмотри на..", "почитай статьи" и др вумных поучений? Как быстро все это исчезло - а ведь я готов и посмотреть и почитать..  Ну ладно, спасибо хоть за Сигуяму  :)

Я это когда-то смотрел у Алены С++, оттуда и вспомнил. Мне нужно было рисовать графы с минимум пересечений (ну там был автомат и состояний было не более 2-3 десятков), но потом я узнал, что graphviz это умеет и в итоге я просто писал граф в файл, а отображал уже graphvizом.

Кстати задача оказалось совсем несложной  :)

А можно посмотреть или хотя бы узнать решение сие задачи?

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