Форум программистов, компьютерный форум CyberForum.ru

Построение графа (карты узлов) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
Union
 Аватар для Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
06.08.2012, 23:03     Построение графа (карты узлов) #1
Задача такая, есть 10 вершин, представляющих из себя круги диаметром 10 мм каждый. Есть таблица, в которой определено расстояние от каждой до каждой вершины (всего соответственно 100 значенией). Важное условие - круги не должны пересекаться. При этом при построении графа для выполнения данного условия разрешается несоответствие расстояний, но нарушение заданного расстояния между вершинами должно быть минимальным, для сохранения объективности графа.
Как рассчитать позиции этих кругов не учитывая пересечения, я понимаю. Но вот как рассчтать так, чтобы пересечений не происходило - не понятно.
Кто занимался подобными задачами - расскажите вкратце, как решается подобная задача, или посоветуйте статью/литературу.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
6901 / 5141 / 252
Регистрация: 10.12.2010
Сообщений: 22,604
Записей в блоге: 17
06.08.2012, 23:35     Построение графа (карты узлов) #2
Важное условие - круги не должны пересекаться
Круги или соединяющие линии?
Union
 Аватар для Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
06.08.2012, 23:47  [ТС]     Построение графа (карты узлов) #3
В каждой вершине круг заданного диаметра. Круги не должны пересекаться.
Может выйти так, имеется 4 вершины: a, b, c и d.
a от d отстоит на расстояние n
b от a и от b отстоит на расстояние n/2
с от a и от b отстоит тоже на расстояние n/2
Выходит такая картина:
a-----------bc-----------d
То есть точки b и c пересеклись (совпали)...
Avazart
 Аватар для Avazart
6901 / 5141 / 252
Регистрация: 10.12.2010
Сообщений: 22,604
Записей в блоге: 17
06.08.2012, 23:58     Построение графа (карты узлов) #4
Повторяю
Круги или соединяющие их линии?
Если круги, то при чем тут граф ?
Union
 Аватар для Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
07.08.2012, 02:13  [ТС]     Построение графа (карты узлов) #5
Важное условие - круги не должны пересекаться.
, т.ч. круги. Вот приведу пример. На первом рисунке строго соблюдены длины. Круги пересеклись. Нужно составить такой алгоритм, который будет при минимальном изменении заданных длин дуг строить граф с непересекающимися кругами (рисунок 2).

Я уже написал алгоритм, который расставляет точки, но некоторые круги пересеклись. Проблема состоит в том, что их нужно как-то передвинуть в свободные области...

Нашел немного здесь: http://habrahabr.ru/post/148351/ но в математике не силен, а описания принципа как такового нет
Миниатюры
Построение графа (карты узлов)  
Kojt
73 / 69 / 2
Регистрация: 19.05.2010
Сообщений: 167
07.08.2012, 08:42     Построение графа (карты узлов) #6
Можно попробовать реализовать физическую модель с пружинами
Т.е. представить соединительные линии как пружины, тогда за несколько итераций круги расставятся по местам так, что пересекаться они не будут.
В модели следует ввести функцию силы отталкивания такую, что если круги не пересекаются, то эта сила равна нулю.
К сожалению сейчас у меня доступа к этим материалам нет, но вроде бы здесь есть пример подобной модели, или где-то в других документах блога.
Avazart
 Аватар для Avazart
6901 / 5141 / 252
Регистрация: 10.12.2010
Сообщений: 22,604
Записей в блоге: 17
07.08.2012, 10:23     Построение графа (карты узлов) #7
Почему нельзя просто привязать круги к сетке.
Kojt
73 / 69 / 2
Регистрация: 19.05.2010
Сообщений: 167
07.08.2012, 10:39     Построение графа (карты узлов) #8
Цитата Сообщение от Avazart Посмотреть сообщение
Почему нельзя просто привязать круги к сетке.
Наверно потому, что есть условие минимального изменения длин
Union
 Аватар для Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
07.08.2012, 20:05  [ТС]     Построение графа (карты узлов) #9
Да. У меня даны вершины a, b, c, d и такая табличка расстояний:
a - b = 100
a - c = 88
a - d = 3
b - c = 10
b - d = 55
c - d = 77
На самом деле вершин больше. Каждая вершина - центр круга. Нужно расположить круги так, чтобы расстояния изменились минимально. Круги не должны пересекаться.
Вот такая задача
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.08.2012, 20:15     Построение графа (карты узлов)
Еще ссылки по теме:

Построение ориентированного графа C++
ввести порядковый номер карты из колоды и выводит в консоль масть и достоинство карты C++
C++ Написать программу, которая предлагает пользователю ввести порядковый номер карты из колоды и выводит в консоль масть и достоинство карты

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Avazart
 Аватар для Avazart
6901 / 5141 / 252
Регистрация: 10.12.2010
Сообщений: 22,604
Записей в блоге: 17
07.08.2012, 20:15     Построение графа (карты узлов) #10
Диаметр окружности одинаков у всех вершин?
Соединяющие линии могут пересекаться ?

Наверно потому, что есть условие минимального изменения длин
Ну так привязывать к сетке только проблемные.
Yandex
Объявления
07.08.2012, 20:15     Построение графа (карты узлов)
Ответ Создать тему
Опции темы

Текущее время: 03:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru