|
Название: Отфильтровать граф Отправлено: Igors от Октябрь 31, 2012, 21:13 Добрый вечер
Есть N вершин (точек в пр-ве) каждая знает с какими др вершинами она соединена, т.е. ребра известны. Нужно как-то удалить некоторые ребра так чтобы бредовая картинка (аттач) приобрела божеский вид. Новые ребра создавать нельзя. Конечно получить корректную поверхность было бы просто замечательно, но это вряд ли достижимо. Нужно просто "поприличнее". Слушаю Ваши предложения Спасибо Название: Re: Отфильтровать граф Отправлено: kambala от Октябрь 31, 2012, 23:15 понятия «божеский вид» и «поприличнее» от математики довольно далёки. что конкретно нужно? (выпуклая оболочка вряд ли как я понимаю) что планируется делать с графом в дальнейшем?
Название: Re: Отфильтровать граф Отправлено: Igors от Ноябрь 01, 2012, 10:48 что конкретно нужно? (выпуклая оболочка вряд ли как я понимаю) что планируется делать с графом в дальнейшем? Много чего, следующий шаг - разбиение некоторых ребер графа (используя значения записанные в вершинах). понятия «божеский вид» и «поприличнее» от математики довольно далёки. Так ведь здесь "форум программистов" :) Ладно, давайте определим что такое "корректная поверхность"- ребра не пересекаются - любой внутренний контур имеет 3 ребра Т.е просто нормальная 3D модель, mesh. Такой идеальный результат конечно желателен, но необязателен. Если будут пересечения (в разумных пределах) - переживу. Конечно можно продолжать придираться "а что такое в разумных пределах?" - но это не конструктивно. Название: Re: Отфильтровать граф Отправлено: Disa от Ноябрь 02, 2012, 15:05 Для планарных, помню есть "метод Сигуиямы" (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).
Название: Re: Отфильтровать граф Отправлено: Igors от Ноябрь 02, 2012, 23:22 Для планарных, помню есть "метод Сигуиямы" (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). Вот-вот :) Примерно такое обычно и находится при гуглении. Не, ну конечно нельзя сказать "не по теме" - там вроде есть нечто подобное на картинке. Но как делать (хоть на словах) - указаний ноль. А взять готовое (дабы "не изобретать велосипед") - об этом можно только мечтать...Да, и почему не слышно типовых "посмотри на..", "почитай статьи" и др вумных поучений? Как быстро все это исчезло - а ведь я готов и посмотреть и почитать.. Ну ладно, спасибо хоть за Сигуяму :) Название: Re: Отфильтровать граф Отправлено: Disa от Ноябрь 02, 2012, 23:43 Я это когда-то смотрел у Алены С++, оттуда и вспомнил. Мне нужно было рисовать графы с минимум пересечений (ну там был автомат и состояний было не более 2-3 десятков), но потом я узнал, что graphviz это умеет и в итоге я просто писал граф в файл, а отображал уже graphvizом.
Название: Re: Отфильтровать граф Отправлено: Igors от Ноябрь 04, 2012, 19:28 Кстати задача оказалось совсем несложной :)
Название: Re: Отфильтровать граф Отправлено: Bepec от Ноябрь 04, 2012, 21:22 Цитировать 00.01 Ник: Как заработать миллион ничего не делая? 00.05 Ник: А, всё понятно. Кстати задача оказалась несложной! *srv: Ник exit. Reason: "Всё итак понятно". Название: Re: Отфильтровать граф Отправлено: IGreench от Март 23, 2013, 13:09 А можно посмотреть или хотя бы узнать решение сие задачи?
Название: Re: Отфильтровать граф Отправлено: Igors от Март 23, 2013, 15:01 А можно посмотреть или хотя бы узнать решение сие задачи? Наверное "сей" :) Для каждой вершины сортируем все выходящие из нее ребра по углу (по часовой или против - как нравится). Для каждого ребра берем предыдущее и следующее, угол между смежными не должен быть > 180. Три ребоа образуют четырехугольник, парим его по Борису Николаевичу: проверяемое ребро должно оказаться лучшей диагональю, иначе подлежит удалению. |