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

@Union · Регистрация: 16.08.2010

Студворк — интернет-сервис помощи студентам

Задача такая, есть 10 вершин, представляющих из себя круги диаметром 10 мм каждый. Есть таблица, в которой определено расстояние от каждой до каждой вершины (всего соответственно 100 значенией). Важное условие - круги не должны пересекаться. При этом при построении графа для выполнения данного условия разрешается несоответствие расстояний, но нарушение заданного расстояния между вершинами должно быть минимальным, для сохранения объективности графа.
Как рассчитать позиции этих кругов не учитывая пересечения, я понимаю. Но вот как рассчтать так, чтобы пересечений не происходило - не понятно.
Кто занимался подобными задачами - расскажите вкратце, как решается подобная задача, или посоветуйте статью/литературу.

@Avazart · 06.08.2012, 23:35

Важное условие - круги не должны пересекаться

Круги или соединяющие линии?

@Union · 06.08.2012, 23:47 **[ТС]**

В каждой вершине круг заданного диаметра. Круги не должны пересекаться.
Может выйти так, имеется 4 вершины: a, b, c и d.
a от d отстоит на расстояние n
b от a и от b отстоит на расстояние n/2
с от a и от b отстоит тоже на расстояние n/2
Выходит такая картина:

a-----------bc-----------d

То есть точки b и c пересеклись (совпали)...

@Avazart · 06.08.2012, 23:58

Повторяю

Круги или соединяющие их линии?

Если круги, то при чем тут граф ?

@Union · 07.08.2012, 02:13 **[ТС]**

Важное условие - круги не должны пересекаться.

, т.ч. круги. Вот приведу пример. На первом рисунке строго соблюдены длины. Круги пересеклись. Нужно составить такой алгоритм, который будет при минимальном изменении заданных длин дуг строить граф с непересекающимися кругами (рисунок 2).

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

Нашел немного здесь: http://habrahabr.ru/post/148351/ но в математике не силен, а описания принципа как такового нет

@Kojt · 07.08.2012, 08:42

Можно попробовать реализовать физическую модель с пружинами
Т.е. представить соединительные линии как пружины, тогда за несколько итераций круги расставятся по местам так, что пересекаться они не будут.
В модели следует ввести функцию силы отталкивания такую, что если круги не пересекаются, то эта сила равна нулю.
К сожалению сейчас у меня доступа к этим материалам нет, но вроде бы здесь есть пример подобной модели, или где-то в других документах блога.

@Avazart · 07.08.2012, 10:23

Почему нельзя просто привязать круги к сетке.

@Kojt · 07.08.2012, 10:39

Сообщение от Avazart

Почему нельзя просто привязать круги к сетке.

Наверно потому, что есть условие минимального изменения длин

@Union · 07.08.2012, 20:05 **[ТС]**

Да. У меня даны вершины a, b, c, d и такая табличка расстояний:
a - b = 100
a - c = 88
a - d = 3
b - c = 10
b - d = 55
c - d = 77
На самом деле вершин больше. Каждая вершина - центр круга. Нужно расположить круги так, чтобы расстояния изменились минимально. Круги не должны пересекаться.
Вот такая задача

@Avazart · 07.08.2012, 20:15

Диаметр окружности одинаков у всех вершин?
Соединяющие линии могут пересекаться ?

Наверно потому, что есть условие минимального изменения длин

Ну так привязывать к сетке только проблемные.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Union 17 / 17 / 0 Регистрация: 16.08.2010 Сообщений: 252

	Построение графа (карты узлов) 06.08.2012, 23:03. Показов 3878. Ответов 9 Метки нет (Все метки) Задача такая, есть 10 вершин, представляющих из себя круги диаметром 10 мм каждый. Есть таблица, в которой определено расстояние от каждой до каждой вершины (всего соответственно 100 значенией). Важное условие - круги не должны пересекаться. При этом при построении графа для выполнения данного условия разрешается несоответствие расстояний, но нарушение заданного расстояния между вершинами должно быть минимальным, для сохранения объективности графа. Как рассчитать позиции этих кругов не учитывая пересечения, я понимаю. Но вот как рассчтать так, чтобы пересечений не происходило - не понятно. Кто занимался подобными задачами - расскажите вкратце, как решается подобная задача, или посоветуйте статью/литературу. 0

@Kojt 73 / 69 / 1 Регистрация: 19.05.2010 Сообщений: 167
	07.08.2012, 08:42
	Можно попробовать реализовать физическую модель с пружинами Т.е. представить соединительные линии как пружины, тогда за несколько итераций круги расставятся по местам так, что пересекаться они не будут. В модели следует ввести функцию силы отталкивания такую, что если круги не пересекаются, то эта сила равна нулю. К сожалению сейчас у меня доступа к этим материалам нет, но вроде бы здесь есть пример подобной модели, или где-то в других документах блога. 2

@Avazart 8488 / 6155 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	07.08.2012, 10:23
	Почему нельзя просто привязать круги к сетке. 0

@Union 17 / 17 / 0 Регистрация: 16.08.2010 Сообщений: 252
	07.08.2012, 20:05 [ТС]
	Да. У меня даны вершины a, b, c, d и такая табличка расстояний: a - b = 100 a - c = 88 a - d = 3 b - c = 10 b - d = 55 c - d = 77 На самом деле вершин больше. Каждая вершина - центр круга. Нужно расположить круги так, чтобы расстояния изменились минимально. Круги не должны пересекаться. Вот такая задача 0