Задача геометрического свойства. Есть численные координаты Начала (U4:V4) и координаты Конца (AE43:AF43). Между ними - находятся препятствия, в данном случае - это фигура ограниченная четырьмя координатами, вписанными в диапазон AL4:AS4, и фигурой из двух координат (то есть отрезком) - чьи координаты вписаны в диапазон AL5:AS5.
То есть - имеется координаты начала и конца, и координаты препятствий - которые лежат между ними.
Как формулой - рассчитать промежуточные координаты ломаной линии, соединяющей начало и конец, длина которой - самая минимальная ? В файле - эти промежуточные узлы - помечены красной заливкой, для наглядности.
Здравствуйте. Появился непростой вопрос.
Задача геометрического свойства. Есть численные координаты Начала (U4:V4) и координаты Конца (AE43:AF43). Между ними - находятся препятствия, в данном случае - это фигура ограниченная четырьмя координатами, вписанными в диапазон AL4:AS4, и фигурой из двух координат (то есть отрезком) - чьи координаты вписаны в диапазон AL5:AS5.
То есть - имеется координаты начала и конца, и координаты препятствий - которые лежат между ними.
Как формулой - рассчитать промежуточные координаты ломаной линии, соединяющей начало и конец, длина которой - самая минимальная ? В файле - эти промежуточные узлы - помечены красной заливкой, для наглядности.ПутинВВ
Кстати - вы знаете как здесь можно формулой рассчитать количество промежуточных узлов и их координаты ? Или решение формулой здесь не подойдет ?
bmv98rus, нет не реинкарнация.
Кстати - вы знаете как здесь можно формулой рассчитать количество промежуточных узлов и их координаты ? Или решение формулой здесь не подойдет ?ПутинВВ
ПутинВВ, Одной формулой тут не обойтись, так как в расчет нужно и размеры и геометрию фигур, с какой стороны от движения препятствие оставляем …. . например ломаная в 5 шагов будет короче, так как движение на втором шаге вдоль торца левого прямоугольника сократит дистанцию. А если мы говорим о неограниченном количестве шагов, то обход угла по кротчайшей дистанции - это дуга. А дуга это просто ломаная линия с мелким шагом.
ПутинВВ, Одной формулой тут не обойтись, так как в расчет нужно и размеры и геометрию фигур, с какой стороны от движения препятствие оставляем …. . например ломаная в 5 шагов будет короче, так как движение на втором шаге вдоль торца левого прямоугольника сократит дистанцию. А если мы говорим о неограниченном количестве шагов, то обход угла по кротчайшей дистанции - это дуга. А дуга это просто ломаная линия с мелким шагом.bmv98rus
Замечательный Временно просто медведь , процентов на 20.
Не совсем понял задачу. 1. Она дискретная (т.е. привязана к клеточкам) или векторная (т.е. задана координатами геометрических фигур и их характеристиками и нужно найти решения не привязанные к клеткам)? 2. Нужно найти решение за наименьшее кол-во изгибов пути или их может быть множество.
Если задача дискретная и не обязательно идти по прямым, то можно применить волновой алгоритм по матрице если векторная, то можно привязаться к сетке с каким нибудь шагом, и по ней построить граф (та еще задача будет), а затем найти решение алгоритмом Дейкстры
Не совсем понял задачу. 1. Она дискретная (т.е. привязана к клеточкам) или векторная (т.е. задана координатами геометрических фигур и их характеристиками и нужно найти решения не привязанные к клеткам)? 2. Нужно найти решение за наименьшее кол-во изгибов пути или их может быть множество.
Если задача дискретная и не обязательно идти по прямым, то можно применить волновой алгоритм по матрице если векторная, то можно привязаться к сетке с каким нибудь шагом, и по ней построить граф (та еще задача будет), а затем найти решение алгоритмом ДейкстрыMCH
MCH, Задача - мне кажется дискретная. Потому что координаты вершин прямоугольника - это всегда какая-то конкретная ячейка. И можно перефразировать исходные данные, записав вместо x y x y x y x y 10 100 200 130 190 140 5 110
адреса ячеек: I16, AF20, AF23, I19
А для линии это будет вместо x y x y 175 160 300 155
адреса ячеек AA32, AR25
(Мне кажется, что расстояния здесь нужно измерять не в координатах (я их просто для наглядности привел), а в количестве ячеек до цели, в том числе и по диагонали)
2. Насчет количества изгибов. Просто желательно, чтобы путь к цели - был кратчайшим. И с точке зрения кратчайшего пути - получается, что в данном случае в моем примере - это будет ровно примерно изгиба (адреса AH22 и Z32), поскольку именно с таким количеством изгибов путь будет минимальным.
Но если все равно путь будет примерно таким же коротким, то наверное можно и немного побольше изгибов пути допустить. Например если добавить еще дополнительные промежуточные адреса AH20 и Z34 - то путь не станет особо длиннее.
MCH, Задача - мне кажется дискретная. Потому что координаты вершин прямоугольника - это всегда какая-то конкретная ячейка. И можно перефразировать исходные данные, записав вместо x y x y x y x y 10 100 200 130 190 140 5 110
адреса ячеек: I16, AF20, AF23, I19
А для линии это будет вместо x y x y 175 160 300 155
адреса ячеек AA32, AR25
(Мне кажется, что расстояния здесь нужно измерять не в координатах (я их просто для наглядности привел), а в количестве ячеек до цели, в том числе и по диагонали)
2. Насчет количества изгибов. Просто желательно, чтобы путь к цели - был кратчайшим. И с точке зрения кратчайшего пути - получается, что в данном случае в моем примере - это будет ровно примерно изгиба (адреса AH22 и Z32), поскольку именно с таким количеством изгибов путь будет минимальным.
Но если все равно путь будет примерно таким же коротким, то наверное можно и немного побольше изгибов пути допустить. Например если добавить еще дополнительные промежуточные адреса AH20 и Z34 - то путь не станет особо длиннее.ПутинВВ
Такие задачи (волновые) решаются программированием. Формулами достаточно сложно. У меня где-то были формульные итерационные решения для прохождения по лабиринту. Как раз используя волновой алгоритм. Но там во ВСЕХ ячейках поля записаны сложные формулы. Для данной задачи вряд ли подойдёт.
Такие задачи (волновые) решаются программированием. Формулами достаточно сложно. У меня где-то были формульные итерационные решения для прохождения по лабиринту. Как раз используя волновой алгоритм. Но там во ВСЕХ ячейках поля записаны сложные формулы. Для данной задачи вряд ли подойдёт.Светлый