roboforum.ru

Digit писал(а):В общем, проверил векторный вариант на листике робот поедет достаточно прямо...

Что и требовалось доказать

Digit писал(а):Но все-таки он не в состоянии проехать между двумя препятствиями по центру - он будет прижиматься к одному из препятствий.

А вы когда между двумя домами проходите - тоже обязательно по центру идете или где ближе? Боитесь стукнуться - увеличивайте SafeDistance.

Digit писал(а):А еще решение задачи триангуляции не в статье не описано

Триангуляция то зачем? сказали же что нафиг её не надо, у меня решено в общем виде будет. Триангуляция - лишь частный случай получится.

Digit писал(а):Мы ж не можем сделать полносвязный граф - надо проверять пересечение ребер графа и препятствий... В общем, как-то так

Пересечение отрезка и ломанной - распишу обязательно.

Digit писал(а):

=DeaD= писал(а):Может вообще не париться, да в википедию сослаться общую? http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
Как думаешь? Или оттуда стырить описалово?

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

Наоборот "для продвинутых" описание тут, а для тех кто не вкурил - в вику за подробностями.

Digit писал(а):Рисунков достаточно?

Ща будем смотреть.

Digit писал(а):А зачем обводить препятствия, представленные в виде прямоугольников, прямоугольниками со скругленными углами? Мы ж по-танковски поворачиваем и на время поворота забили...

Банально иначе наша система может ответ дать "фиг проедешь" когда проезд есть, просто двигаться придется коряво

Digit писал(а):

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

Вот к вопросу о триангуляции, о которой я говорил выше... Надо привести алгоритм, позволяющий построить граф, удовлетворяющий условиям из цитаты.

Будет, будет. Правда при чем тут триангуляция? Триангуляция вроде - когда по точным данным свои координаты находим.

Digit писал(а):...в общем для иллюстрации "на пальцах" засунул туда алгоритм А*. Пойдет? Или вообще теперь огромная статья - никто читать не будет?

Про алгоритм А* - посмотрю что сделано

Добавлено спустя 1 минуту 15 секунд:
Вообще есть желание разнести поиск пути на векторной карте и поиск пути на растровой карте.

А* - к растровой с простейшей дейкстрой.

А мой навороченный алгоритм - к векторной.

Добавлено спустя 15 минут 32 секунды:

Digit писал(а):Но все-таки он не в состоянии проехать между двумя препятствиями по центру - он будет прижиматься к одному из препятствий. А еще решение задачи триангуляции не в статье не описано

Digit в википедии писал(а):Переход от векторной карты к взвешенному графу. Показан один из множества вариантов построения графа на данном наборе вершин.

Аааааа! Я понял, что ты не понял что значит "один из множества"? На данном наборе вершин граф определяется единственным образом. Пересечение либо есть, либо нет. Все ребра которые не пересекают границы препятствий обязательно есть, остальные нет.

И у тебя на графе не хватает огромной кучи ребер. И некоторые вершины непонятно откуда (углы карты, где нет препятствий).

В общем, по триангуляции. То, что это определение положения - да. Но еще, если не путаю, так называют построение сети треугольников (mesh) на произвольном множестве точек. При этом как функция выбора "правильного" треугольника - минимальное отношение его сторон. Это как раз то, что нам надо, чтоб граф построить.

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

По поводу того, что это граф "один из"

=DeaD= писал(а):

Digit в википедии писал(а):Переход от векторной карты к взвешенному графу. Показан один из множества вариантов построения графа на данном наборе вершин.

что значит "один из множества"? На данном наборе вершин граф определяется единственным образом. Пересечение либо есть, либо нет. Все ребра которые не пересекают границы препятствий обязательно есть, остальные нет.

У нас граф с самопересечениями или без? Если без, то на множестве из 4-х точек можно построить как минимум два разных набора треугольников. И это будет два графа. Вот о том и пишу.

Добавлено спустя 2 минуты 17 секунд:
Относительно скругленных контуров вокруг препятствий... Не понял, чем это поможет алгоритму пути находить? По-моему, только лишних вершин плодим...

Добавлено спустя 2 минуты 49 секунд:
А смысл разделять векторные и растровые поиски пути? Суть то одна и та же... Ну будет в растре А* (пусть даже с вариантами улучшения, отсечениями всякими и т.п.), а в векторе будет Дейкстра в полноценном варианте. А дальше что? Дейкстра может применяться на растре. А* может при определенных условиях применяться на векторе. На то они и алгоритмы!

Digit писал(а):В общем, по триангуляции. То, что это определение положения - да. Но еще, если не путаю, так называют построение сети треугольников (mesh) на произвольном множестве точек. При этом как функция выбора "правильного" треугольника - минимальное отношение его сторон. Это как раз то, что нам надо, чтоб граф построить.

Не знаю как вы, но я триангуляцию нигде не пользовал и не предполагал пользовать

Digit писал(а):То, что я в углы карты нарисовал, так там тоже могут быть точки... Могу убрать А кучи ребер не хватает - так там же запаришься все рисовать! К тому же, то, что нарисовано - тоже граф, причем пригодный для решения задачи

Так чем он пригодный то? Мы же кратчайший путь ищем, а не абы какой а вы?

Digit писал(а):По поводу того, что это граф "один из"

=DeaD= писал(а):

Digit в википедии писал(а):Переход от векторной карты к взвешенному графу. Показан один из множества вариантов построения графа на данном наборе вершин.

что значит "один из множества"? На данном наборе вершин граф определяется единственным образом. Пересечение либо есть, либо нет. Все ребра которые не пересекают границы препятствий обязательно есть, остальные нет.

У нас граф с самопересечениями или без? Если без, то на множестве из 4-х точек можно построить как минимум два разных набора треугольников. И это будет два графа. Вот о том и пишу.

Дак конечно с самопересечениями! Кто ж запрещает рассматривать пересекающие друг друга отрезки пути? Главное чтобы они границы препятствий не пересекали.

Digit писал(а):Относительно скругленных контуров вокруг препятствий... Не понял, чем это поможет алгоритму пути находить? По-моему, только лишних вершин плодим...

Тем что легко построить пример прикрепленный ниже.

Digit писал(а):А смысл разделять векторные и растровые поиски пути? Суть то одна и та же... Ну будет в растре А* (пусть даже с вариантами улучшения, отсечениями всякими и т.п.), а в векторе будет Дейкстра в полноценном варианте. А дальше что? Дейкстра может применяться на растре. А* может при определенных условиях применяться на векторе. На то они и алгоритмы!

Как это к чему? А* на векторной карте не применяется, а на растровой границы препятствий и построение графа нафиг не надо. Вот и получается, что только по дейкстре они и пересекаются к тому же дейкстра на растровой карте полноценная нафиг не нужна, там все длины ребер одинаковые и можно все сильно упростить. Итого - вообще нет пересечений

Добавлено спустя 54 секунды:
По моему нас надо расстрелять за оффтопик переношу обсуждение конкретной темы в отдельную ветку

Добавлено спустя 3 часа 26 минут 49 секунд:
Re: Энциклопедия по робототехнике - Поиск пути на карте (обсужд.)
Разнес страницу на 2 части, в растровой попробую как силы появятся дописать упрощенную дейкстру (фронт волны так же надо хранить в очереди), и вообще обе страницы попробую причесать. А сейчас я че-то выдохся выходные не отдохнул нормально - работать пришлось...

=DeaD= писал(а):

Digit писал(а):В общем, по триангуляции. То, что это определение положения - да. Но еще, если не путаю, так называют построение сети треугольников (mesh) на произвольном множестве точек. При этом как функция выбора "правильного" треугольника - минимальное отношение его сторон. Это как раз то, что нам надо, чтоб граф построить.

Не знаю как вы, но я триангуляцию нигде не пользовал и не предполагал пользовать

Собственно, я чего-то решил, что граф должен быть без самопересечений С самопересечениями нам реально достаточно соединить все вершины со всеми, а потом последовательно проверить каждое ребро на пересечение с препятствием...

=DeaD= писал(а):Как это к чему? А* на векторной карте не применяется, а на растровой границы препятствий и построение графа нафиг не надо. Вот и получается, что только по дейкстре они и пересекаются к тому же дейкстра на растровой карте полноценная нафиг не нужна, там все длины ребер одинаковые и можно все сильно упростить. Итого - вообще нет пересечений

не хочу прослыть занудой, но А* - это Дейкстра и есть... Ну да ладно.

P.S.
Ох, да простит меня Авр123 за использование его методов:
Давай общаться на "ТЫ"!

Digit писал(а): не хочу прослыть занудой, но А* - это Дейкстра и есть... Ну да ладно.

Нет, Дейкстра это на графах и классика, а что такое А* я вообще затрудняюсь сказать, по моему обычная заливка. Особенность в том, что А* изначально не предназначен для работы с различными длинами ребер. Как минимум потому, что в нем не предусмотрена замена уже заполненных значений на меньшие (по научному - процедура "релаксации"). Я уж не говорю про то, что нигде не сказано про хранение в очереди фронта волны.

Digit писал(а):Ох, да простит меня Авр123 за использование его методов:
Давай общаться на "ТЫ"!

Вот блин короче, наверное, проще не обращать внимание на эти мои глюки

Ладно, на ты\вы забьем. Я просто себя неловко чувствую, "тыкая", когда со мной вот так культурно

Про А*. Я ж его в самом простом виде привел... Ты заглядывал по ссылке, которую я в вики в примечании дал? Вот эта: http://program.rin.ru/razdel/html/688-1.html
Там есть варианты...
Разная длина ребер... Ну, вот смотри: берем две матрицы. в одну будем заносить наши числа, в другой записаны числа от 0 до 255, характеризующие проходимость территории. Скажем, 255 - это непроходимо, стена или еще что-то. А значения от 1 до 100 - это степень пересеченности местности, т.е. время, затрачиваемое на преодоление клеточки с таким типом местности, т.е. длина ребра графа. Думаю, понятно, что это синонимы в данном случае.
Переносим в нашу результирующую матрицу в точку финиша число, хранящееся по координатам точки финиша во второй матрице.
Теперь заполняя нашу результирующую матрицу, прибавляем к числу, хранящемуся по текущим координатам в результирующей матрице, число из исходной матрицы из клетки, куда двигается "фронт волны".
Все. Мы учли длину ребер. Останется из точки старта перемещаться каждый раз в клетку с наименьшим числом (по сравнению с соседями) и все.
Написано, наверное, коряво... Могу рисунок сделать, схемку. Для наглядности. Надо?

Добавлено спустя 4 минуты 42 секунды:
Загляни туда еще - требуется твой "одобрямс" - viewtopic.php?f=5&t=1947&start=60

Digit писал(а):Ладно, на ты\вы забьем. Я просто себя неловко чувствую, "тыкая", когда со мной вот так культурно

Про А*. Я ж его в самом простом виде привел... Ты заглядывал по ссылке, которую я в вики в примечании дал? Вот эта: http://program.rin.ru/razdel/html/688-1.html
Там есть варианты...
Разная длина ребер... Ну, вот смотри: берем две матрицы. в одну будем заносить наши числа, в другой записаны числа от 0 до 255, характеризующие проходимость территории. Скажем, 255 - это непроходимо, стена или еще что-то. А значения от 1 до 100 - это степень пересеченности местности, т.е. время, затрачиваемое на преодоление клеточки с таким типом местности, т.е. длина ребра графа. Думаю, понятно, что это синонимы в данном случае.
Переносим в нашу результирующую матрицу в точку финиша число, хранящееся по координатам точки финиша во второй матрице.
Теперь заполняя нашу результирующую матрицу, прибавляем к числу, хранящемуся по текущим координатам в результирующей матрице, число из исходной матрицы из клетки, куда двигается "фронт волны".
Все. Мы учли длину ребер. Останется из точки старта перемещаться каждый раз в клетку с наименьшим числом (по сравнению с соседями) и все.
Написано, наверное, коряво... Могу рисунок сделать, схемку. Для наглядности. Надо?

Тогда не ясно с какого перепугу было называть это А* алгоритмом, когда есть название общепринятое - Дейкстра. Видимо люди в разных видах деятельности привыкли по второму разу изобретать велосипед.

История была про физика, который электрические поля исследовал, уехав на 2 года на остров. Он по приезду с докладом выступал и рассказывал как с полями что рассчитывать и сказал что по ходу придумал специальные таблицы с числами и действия с ними. После доклада к нему подошел математик и рассказал, что таблицы с числами давно придуманы и называются матрицами, и действия с ними тоже давно придуманы...

Digit писал(а):Загляни туда еще - требуется твой "одобрямс" - viewtopic.php?f=5&t=1947&start=60

Done!

=DeaD= писал(а):Тогда не ясно с какого перепугу было называть это А* алгоритмом, когда есть название общепринятое - Дейкстра. Видимо люди в разных видах деятельности привыкли по второму разу изобретать велосипед.

Я не в курсе, почему его не назвали сразу Дейкстрой... Возможно, чтоб отличать классического Дейкстру от сильно упрощенной версии.

Завел раздел [[Прикладная геометрия]], попробую сегодня наполнить. В нем будут различные прикладные штуки типа пересечения отрезков, многоугольников и т.п. полезности.

Наверняка знаешь, но все же. Вот сайтик: AlgoList. Сайт уже давно в сети, постоянно обновляется и вообще хороший. (Не сочтите за рекламу )

Добавлено спустя 20 минут 24 секунды:
В алгоритме построения растровой карты:

Во всех клетках с локальными координатами относительно нашего робота от 0,0 до D*cos(A),D*sin(A) препятствий нет. Простейший способ выявить все эти клетки - запустить цикл по переменной V с шагом в полдлины стороны клетки от 0 до D-K и ставить в клетку с локальными координатами относительно робота V*cos(A),V*sin(A) пометку "есть проход".

ИМХО, правильнее рассматривать не отрезок, а треугольник, в котором распространялись ИК-лучи (или чем там робот засек препятствие). А клетки помечать свободными только те, которые в данный треугольник поместились полностью (это ограничение растровой карты - иначе у нас клетка, в которой объект только малую долю занимает, будет считаться свободной).

Digit писал(а):Наверняка знаешь, но все же. Вот сайтик: AlgoList. Сайт уже давно в сети, постоянно обновляется и вообще хороший. (Не сочтите за рекламу )

В курсе там части нужных нам алгоритмов нету Например объединение многоугольников, разность и пересечение, когда они невыпуклые

Digit писал(а):Добавлено спустя 20 минут 24 секунды:
В алгоритме построения растровой карты:

Во всех клетках с локальными координатами относительно нашего робота от 0,0 до D*cos(A),D*sin(A) препятствий нет. Простейший способ выявить все эти клетки - запустить цикл по переменной V с шагом в полдлины стороны клетки от 0 до D-K и ставить в клетку с локальными координатами относительно робота V*cos(A),V*sin(A) пометку "есть проход".

ИМХО, правильнее рассматривать не отрезок, а треугольник, в котором распространялись ИК-лучи (или чем там робот засек препятствие). А клетки помечать свободными только те, которые в данный треугольник поместились полностью (это ограничение растровой карты - иначе у нас клетка, в которой объект только малую долю занимает, будет считаться свободной).

Ну про то, что не должно быть объектов занимающих малую доли клетки - я уже сказал. А ИК-лучи вроде широкий угол не захватывают? Хотя пофиг, можно и треугольник рассмотреть

Добавлено спустя 2 часа 9 минут 10 секунд:
Re: Энциклопедия по робототехнике - Поиск пути на карте (обсужд.)
Расписал в [[Прикладная геометрия]] Переход от одной системы координат к другой. Прошу рецензировать понятно или нет?

=DeaD= писал(а):
Расписал в [[Прикладная геометрия]] Переход от одной системы координат к другой. Прошу рецензировать понятно или нет?

вполне доступно даже для меня пиши дальше =)

Расписал там же ([[Прикладная геометрия]]) пересечение двух отрезков. Мозголомательная получилась штука надо как-то упрощать, у кого-нибудь есть идеи как?

Добавлено спустя 40 минут 48 секунд:
Re: Энциклопедия по робототехнике - Поиск пути на карте (обсужд.)
Добавил пересечение точки с отрезком и думаю надо будет вынести общие вещи выше (типа определения общего уравнения прямой на плоскости, вычисление коэффициентов общего уравнения прямой по координатам отрезка, вычисление точки пересечения двух прямых и т.п.)

По поводу возможного упрощения: алгоритм на АлгоЛисте. По-моему понятно.

И еще. В этом разделе у нас чисто геометрия?
я к тому, что величины определяются сенсорами с погрешностью... Учет погрешности у нас будет в алгоритмах?

Digit писал(а):По поводу возможного упрощения: алгоритм на АлгоЛисте. По-моему понятно.

Ну да, не считая того, что куча случаев рассмотрена мимоходом, а у меня подробно расписана. Типа этого "Если знаменатель равен нулю, то прямые параллельны." и что? Неужели в этом случае пересечение проверять не надо? В общем попробую на их вариант переписать, так-то да, согласен, мне тоже их подход более простым для понимания кажется. Только надо четко прописывать что будет в случае параллельности

Digit писал(а):И еще. В этом разделе у нас чисто геометрия?
я к тому, что величины определяются сенсорами с погрешностью... Учет погрешности у нас будет в алгоритмах?

А что с погрешностями? Что про них можно написать интересного в целом?

PS: И еще - думаю надо выкинуть случаи, когда один из отрезков - точка, типа проверить на входе, тогда проще всё будет.