Есть ли какой - то готовый способ проложить ломанную прямую от точки до точки?

@~~-NEURON-~~ · 04.09.2014, 22:01. **Показов** 1208. **Ответов** 3

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

Привет математикам!

См. скрин. Есть куча разных прямоугольников (пусть будут одинакового размера), есть ли какой - то готовый способ прокладки ортогональной ломанной прямой от середины ребра одного прямоугольника к середине ребра другого прямоугольника со следующими требованиями:
1. Линия не может пересекать прямоугольники
2. Линия должна проходить не ближе, чем какое - то заданное расстояние от прямоугольников.
3. Линия должна иметь наименьшую длину.
4.Алгоритм расчёта должен быть наиболее быстр и ложится в рамки программ ЭВМ, имеется ввиду не просто какие - то не применимые математические абстракции, а конкретный заданный алгоритм (формулы)

@~~-NEURON-~~ · 04.09.2014, 22:54 **[ТС]**

тфу ты блин, картинку - то я забыл

@Mysterious Light · 04.09.2014, 23:03

Сообщение от -NEURON-

1. Линия не может пересекать прямоугольники
2. Линия должна проходить не ближе, чем какое - то заданное расстояние от прямоугольников.
3. Линия должна иметь наименьшую длину.

Совместим условия 1 и 2, особенно, если учесть, что 2 влечет за собой 1.
Если Вы увеличите все прямоугольники, кроме начального и конечного, со всех сторон на это какое-то заданное расстояние, то задачу можно сформулировать так:
1-2. Линия не должна пересекать увеличенные прямоугольники.
3. Линия должна иметь наименьшую длину.

Посмотрите алгоритм A* и ей подобные, их много, потому что задача распространённая.

@~~-NEURON-~~ · 05.09.2014, 18:55 **[ТС]**

огромное спасибо

Добавлено через 10 часов 17 минут
А если не привязываться к сетке с ячейкой определённого размера и работать с координатами в числах с плавающей запятой ( double - ну там всякие 4.533434, 34.43242 и тд), то алгоритм A* не подойдёт, нет ли какого - то другого алгоритма ? Думаю самому разработать... Построить граф что ли по координатам каждого прямоугольника ...

@~~-NEURON-~~ Заблокирован
		1
	Есть ли какой - то готовый способ проложить ломанную прямую от точки до точки? 04.09.2014, 22:01. Показов 1208. Ответов 3 Метки нет (Все метки) Привет математикам! См. скрин. Есть куча разных прямоугольников (пусть будут одинакового размера), есть ли какой - то готовый способ прокладки ортогональной ломанной прямой от середины ребра одного прямоугольника к середине ребра другого прямоугольника со следующими требованиями: 1. Линия не может пересекать прямоугольники 2. Линия должна проходить не ближе, чем какое - то заданное расстояние от прямоугольников. 3. Линия должна иметь наименьшую длину. 4.Алгоритм расчёта должен быть наиболее быстр и ложится в рамки программ ЭВМ, имеется ввиду не просто какие - то не применимые математические абстракции, а конкретный заданный алгоритм (формулы) 0

@~~-NEURON-~~ Заблокирован
	04.09.2014, 22:54 [ТС]	2
	тфу ты блин, картинку - то я забыл Миниатюры 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,162 Записей в блоге: 24
	04.09.2014, 23:03	3
	Сообщение было отмечено -NEURON- как решение Решение Сообщение от -NEURON- 1. Линия не может пересекать прямоугольники 2. Линия должна проходить не ближе, чем какое - то заданное расстояние от прямоугольников. 3. Линия должна иметь наименьшую длину. Совместим условия 1 и 2, особенно, если учесть, что 2 влечет за собой 1. Если Вы увеличите все прямоугольники, кроме начального и конечного, со всех сторон на это какое-то заданное расстояние, то задачу можно сформулировать так: 1-2. Линия не должна пересекать увеличенные прямоугольники. 3. Линия должна иметь наименьшую длину. Посмотрите алгоритм A* и ей подобные, их много, потому что задача распространённая. 2

@~~-NEURON-~~ Заблокирован
	05.09.2014, 18:55 [ТС]	4
	огромное спасибо Добавлено через 10 часов 17 минут А если не привязываться к сетке с ячейкой определённого размера и работать с координатами в числах с плавающей запятой ( double - ну там всякие 4.533434, 34.43242 и тд), то алгоритм A* не подойдёт, нет ли какого - то другого алгоритма ? Думаю самому разработать... Построить граф что ли по координатам каждого прямоугольника ... 0

Есть ли какой - то готовый способ проложить ломанную прямую от точки до точки?

Решение