Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Отрисовка графа - как? 20.02.07 15:05
Автор: Yurii <Юрий> Статус: Elderman
|
Нужен алгоритм отрисовки графа, причем так, чтобы вершины располагались оптимальным образом, т.е. чтобы ребра пересекались минимальное число раз.
Т.е. дали на вход матрицу схемы московского метрополитена, на выходе получили что-то отдаленно ее напоминающее, а не исчерканный экран. :)
Скажите,плз, в каком направлении двигаться?
|
|
Соображения в общих чертах 20.02.07 15:29
Автор: Heller <Heller> Статус: Elderman
|
Пусть координаты двух разных вершин, соединенных разными графами равны соответствено (x1;y1), (x2;y2), (x3;y3), (x4;y4). Соединены первые две точки и последние две. Можно сформулировать логическое условие их пересечения. Тут либо комбинация множества <>, либо ищешь точку пересечения двух прямых, проведенных через точки и смотришь, чтобы ее координаты попадали внутрь прямоугольника, построенного по этим точкам.
Короче должно получиться при пересечении 1, а при отсутствии оного 0.
Проверяешь пересечения для каждой пары ребер, получаешь количество пересечений, то есть критерий, который будет являться функцией кучи переменных - координат вершин. Далее применяешь любой алгоритм многомерной оптимизации и находишь оптимальное расположение точек на плоскости.
|
| |
Отлично, но если узлов будет хотя бы сотня, боюсь я зависну надолго... 21.02.07 19:52
Автор: Yurii <Юрий> Статус: Elderman
|
|
|
|
|
подробно о проекте
Анализ криптографических сетевых...
