Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
#1

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

06.08.2012, 23:03. Просмотров 1966. Ответов 9
Метки нет (Все метки)

Задача такая, есть 10 вершин, представляющих из себя круги диаметром 10 мм каждый. Есть таблица, в которой определено расстояние от каждой до каждой вершины (всего соответственно 100 значенией). Важное условие - круги не должны пересекаться. При этом при построении графа для выполнения данного условия разрешается несоответствие расстояний, но нарушение заданного расстояния между вершинами должно быть минимальным, для сохранения объективности графа.
Как рассчитать позиции этих кругов не учитывая пересечения, я понимаю. Но вот как рассчтать так, чтобы пересечений не происходило - не понятно.
Кто занимался подобными задачами - расскажите вкратце, как решается подобная задача, или посоветуйте статью/литературу.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.08.2012, 23:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Построение графа (карты узлов) (C++):

Напечатать номера всех узлов заданного графа, соседних по отношению к указанному узлу - C++
Дан неориентированный граф из n узлов и m рёбер. Напечатать номера всех узлов, соседних по отношению к заданному узлу a. Не печатать один ...

Построение графа - C++
Помогите пожалуйста написать программу вот задание:Построить копию заданного графа. граф произвольный на ваш выбор. Добавлено через...

построение графа - C++
Задача: "Задан граф дерево с корневой вершиной. Нужно, начиная с корневой вершины, обойти все концевые вершины (концевая вершина имеет...

Построение графа - C++
Вершины и ребра графа назовем его элементами. По графу G построить граф T(G), у которого в качестве вершин взяты элементы G, а две вершины...

Построение графа лица - C++
Всех приветствую. Помогите пожалуйста в следующем деле.Имеется исходная фотография человеческого лица, нужно сравнить его с другой...

Построение ориентированного графа - C++
Привет!) Покажу код, то что я делал. На выходе нету расстояний(стоимости). Как добавить расстояние на графе. #include...

9
Avazart
Эксперт С++
7246 / 5418 / 297
Регистрация: 10.12.2010
Сообщений: 24,042
Записей в блоге: 17
06.08.2012, 23:35 #2
Важное условие - круги не должны пересекаться
Круги или соединяющие линии?
0
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 пересеклись (совпали)...
0
Avazart
Эксперт С++
7246 / 5418 / 297
Регистрация: 10.12.2010
Сообщений: 24,042
Записей в блоге: 17
06.08.2012, 23:58 #4
Повторяю
Круги или соединяющие их линии?
Если круги, то при чем тут граф ?
0
Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
07.08.2012, 02:13  [ТС] #5
Важное условие - круги не должны пересекаться.
, т.ч. круги. Вот приведу пример. На первом рисунке строго соблюдены длины. Круги пересеклись. Нужно составить такой алгоритм, который будет при минимальном изменении заданных длин дуг строить граф с непересекающимися кругами (рисунок 2).

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

Нашел немного здесь: http://habrahabr.ru/post/148351/ но в математике не силен, а описания принципа как такового нет
0
Миниатюры
Построение графа (карты узлов)  
Kojt
73 / 69 / 2
Регистрация: 19.05.2010
Сообщений: 167
07.08.2012, 08:42 #6
Можно попробовать реализовать физическую модель с пружинами
Т.е. представить соединительные линии как пружины, тогда за несколько итераций круги расставятся по местам так, что пересекаться они не будут.
В модели следует ввести функцию силы отталкивания такую, что если круги не пересекаются, то эта сила равна нулю.
К сожалению сейчас у меня доступа к этим материалам нет, но вроде бы здесь есть пример подобной модели, или где-то в других документах блога.
2
Avazart
Эксперт С++
7246 / 5418 / 297
Регистрация: 10.12.2010
Сообщений: 24,042
Записей в блоге: 17
07.08.2012, 10:23 #7
Почему нельзя просто привязать круги к сетке.
0
Kojt
73 / 69 / 2
Регистрация: 19.05.2010
Сообщений: 167
07.08.2012, 10:39 #8
Цитата Сообщение от Avazart Посмотреть сообщение
Почему нельзя просто привязать круги к сетке.
Наверно потому, что есть условие минимального изменения длин
0
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
На самом деле вершин больше. Каждая вершина - центр круга. Нужно расположить круги так, чтобы расстояния изменились минимально. Круги не должны пересекаться.
Вот такая задача
0
Avazart
Эксперт С++
7246 / 5418 / 297
Регистрация: 10.12.2010
Сообщений: 24,042
Записей в блоге: 17
07.08.2012, 20:15 #10
Диаметр окружности одинаков у всех вершин?
Соединяющие линии могут пересекаться ?

Наверно потому, что есть условие минимального изменения длин
Ну так привязывать к сетке только проблемные.
0
07.08.2012, 20:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.08.2012, 20:15
Привет! Вот еще темы с ответами:

Построение реберного покрытия графа - C++
Нужно написать программу на построение реберного покрытия графа на языке C++. Как это осуществить? Помогите, пожалуйста, хоть как-то,...

заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь - C++
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

ввести порядковый номер карты из колоды и выводит в консоль масть и достоинство карты - C++
ввести порядковый номер карты из колоды и выводит в консоль масть и достоинство карты. Колода, начинается с двоек до туза, по очереди, для...

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


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru