Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 12.08.2015, 09:48
Аватар для Paguo-86PK
Профессор
Отправить личное сообщение для Paguo-86PK Посмотреть профиль Найти все сообщения от Paguo-86PK
 
Регистрация: 16.09.2009
Сообщений: 253

Бинаризация рукописного лабиринта
Имеется алгоритм декодирования маршрута проезда специфического лабиринта в набор токенов.
Правила обхода пути очень просты:
  • Если ветка маршрута имеет один и более поворотов, она помечается синим цветом
  • Если ветка маршрута имеет один и более тупиков, она помечается красным цветом
  • Если ветка маршрута имеет хотя бы один поворот, она не может иметь более одного тупика
На матрице MxN жук благополучно проходит весь маршрут до конца, попутно составляя строку токенов (фигурки тетрамино и пентамино), что отображено в gif-анимации. Проблема только в одном: Жук может двигать по пути шириной в 1 пиксел. Следовательно, имеется редактор лабиринтов.

Вопрос: Какие фильтры следует применять, если лабиринт нарисован от руки маркером или мелом на доске под любым углом?
Уточнения: В самом начале виден корявый лабиринт, нарисованый от руки в Paint. Потом он оквадрачивается в матрицу (всё прорисовал вручную, каждый кадр).
Варианты: Пробовал классический FloodFill с составлением массива координат линий заливки - слишком много данных и не знаю, как систематизировать. Хотел применять алгоритм чтения QR-кода, но мне не нужны три ключевых квадрата на углах. Так же пытался пустить жука с "радаром", который двигается в направлении дальнего горизонта и составляет список поворотов, но не смог сформулировать в скрипте (js+canvas). А выгугленный алгоритм использует уже бинаризованый лабиринт с шагом в 1 пиксел.

Спасибо!
Изображения:
Тип файла: gif anima.gif (49.7 Кб, 5 просмотров)

Последний раз редактировалось Paguo-86PK, 12.08.2015 в 14:18.
Ответить с цитированием
  #2 (permalink)  
Старый 12.08.2015, 12:01
Аватар для nerv_
junior
Отправить личное сообщение для nerv_ Посмотреть профиль Найти все сообщения от nerv_
 
Регистрация: 29.11.2011
Сообщений: 3,924

Сообщение от Paguo-86PK
Вопрос: Какие фильтры следует применять, если лабиринт нарисован от руки маркером или мелом на доске под любым углом?
вероятно, Line fitting, или методы аппроксимации набора точек прямой

Что касается обхода лабиринта - отдельная тема. Я бегло посмотрел статью. На первый взгляд ни о чем
См. в сторону
1. Неинформированные методы поиска (в пространстве состояний)
2. Информированные методы поиска (в пространстве состояний)
3. Визуализация работы информированных методов поиска

---

Если интересно, почти все неинформированные методы я реализовал в рамках своего проекта
https://github.com/nervgh/recursive-iterator
RecursiveIterator / Рекурсивный итератор

Информированные(й) в рамках форка (на скорую руку)
Игра "Пятнашки"
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук

Последний раз редактировалось nerv_, 12.08.2015 в 12:10.
Ответить с цитированием
  #3 (permalink)  
Старый 12.08.2015, 15:00
Аватар для Paguo-86PK
Профессор
Отправить личное сообщение для Paguo-86PK Посмотреть профиль Найти все сообщения от Paguo-86PK
 
Регистрация: 16.09.2009
Сообщений: 253

Сообщение от nerv_ Посмотреть сообщение
вероятно, Line fitting, или методы аппроксимации набора точек прямой
См. в сторону
1. Неинформированные методы поиска (в пространстве состояний)
2. Информированные методы поиска (в пространстве состояний)
3. Визуализация работы информированных методов поиска

Если интересно, почти все неинформированные методы я реализовал в рамках своего проекта
Информированные(й) в рамках форка (на скорую руку)
Думаю, меня не совсем так поняли.
Нужно кривой лабиринт, нарисованый на бумаге и захваченый WebCamer'ой в режиме реального времени обойти. Мой "жук" его обходит только в случае, когда путь имеет ширину в 1 пиксел.
Тем самым, мне нужен фильтр, который не просто векторизирует растровую размазню 1:1, а просто составляет список координат горизонтальных и вертикальных коридоров.

Вот как на анимашке ниже:
Сначала - два варианта одного лабиринта от руки (кривой и ещё кривее), а потом ровные фиолетовые линии. В конце - многократный зум микроскопического лабиринта 14x10 пикселей.
Т.е. мне надо изображение 128x110 аккуратно уменьшить до 14x10, сохранив структуру маршрута для жука.
(построчная заливка и прочие методы не дают нужного результата)

Спасибо!
Изображения:
Тип файла: gif animanu.gif (53.0 Кб, 3 просмотров)
Ответить с цитированием
  #4 (permalink)  
Старый 12.08.2015, 16:29
Аватар для nerv_
junior
Отправить личное сообщение для nerv_ Посмотреть профиль Найти все сообщения от nerv_
 
Регистрация: 29.11.2011
Сообщений: 3,924

Сообщение от Paguo-86PK
Думаю, меня не совсем так поняли.
ответ на этот вопрос в первом предложении моего предыдущего поста
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук
Ответить с цитированием
  #5 (permalink)  
Старый 12.08.2015, 16:52
Аватар для Paguo-86PK
Профессор
Отправить личное сообщение для Paguo-86PK Посмотреть профиль Найти все сообщения от Paguo-86PK
 
Регистрация: 16.09.2009
Сообщений: 253

Сообщение от nerv_ Посмотреть сообщение
ответ на этот вопрос в первом предложении моего предыдущего поста
Хм. Извиняюсь.
Я привык работать с растровыми изображениями (типа используя mmx/sse на ассемблере фильтровать кадры), а вот векторные алгоритмы - тёмное дело. Вот что выдаёт мой скрипт в окне FireFox. Некоторые линии прорисовываются дважды.

Алгоритм: Нахожу первую чёрную точку.
  1. Используя Math sin/cos по всему радиусу определяю максимально длинную линию, запоминая её координаты
  2. Разбиваю всю линию на массив отдельных точек и, как в пункте 1, по всему радиусу ищу максимум
Как видите, алгоритм до тупого прост. И, как правило, это его проблема, так как он один путь проходит несколько раз. Из массива линии потом удалять нельзя, надо удалять в самом процессе. Что сложно для меня и я не понимаю эту часть.

Жёлтые и красные - соответственно вертикальные (север/юг) и горизонтальные (запад/восток) направляющие.
(есть, правда, идея учитывать ширину линии, чтобы ошибочно не проходить сквозь перекрёстки. но это пока довольно сложно мне)

В идеале (в бинарном массиве) формируется таблица декодирования (в матрице жук её формирует):
  • ESWN (EAST + SOUTH + WEST + NORTH) (UpperCase - путь имеет повороты) - старт-кольцо
  • wsn или wns (west + south + north или west + south + north) (LowerCase - путь имеет тупики) - фигурка ├ тетриса
  • WN (WEST + NORTH) - фигурка └ тетриса
  • N (NORTH) - фигурка │ тетриса
  • WS - фигурка ┌
  • NWS
  • sw
  • SE
  • en
  • SEN
В итоге получается "├└│┌⊓┤└┴⊔" в массиве 14x10.
Изображения:
Тип файла: jpg tracer.jpg (22.7 Кб, 5 просмотров)

Последний раз редактировалось Paguo-86PK, 12.08.2015 в 18:56.
Ответить с цитированием
  #6 (permalink)  
Старый 12.08.2015, 20:10
Аватар для nerv_
junior
Отправить личное сообщение для nerv_ Посмотреть профиль Найти все сообщения от nerv_
 
Регистрация: 29.11.2011
Сообщений: 3,924

Paguo-86PK, ok, я тебя понял. Моя ссылка
Сообщение от nerv_
вероятно, Line fitting, или методы аппроксимации набора точек прямой
была немного про другое.

Не знаю зачем тебе это надо, но задача любопытная

Немного позднее попытаюсь порассуждать на этот счет в картинках в том числе.
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук

Последний раз редактировалось nerv_, 12.08.2015 в 20:12.
Ответить с цитированием
  #7 (permalink)  
Старый 12.08.2015, 21:14
Аватар для nerv_
junior
Отправить личное сообщение для nerv_ Посмотреть профиль Найти все сообщения от nerv_
 
Регистрация: 29.11.2011
Сообщений: 3,924

Описываю ниже свое понимание
Сообщение от Paguo-86PK
Бинаризации рукописного лабиринта

Упрощенный вариант
1. определить размер кисти
2. выпрямить линии
3. сжать до "однопиксельных" размеров


Попытаюсь описать как
Цитата:
2. выпрямить линии
на примере конкретно взятой линии
- имеем точки, описывающие линию (A - начало, B - конец)
- строим вектор AB по этим точкам (выделено зеленым)
- помещаем его в двумерную координатную плоскость (x-y) так, как показано на рисунке
- т.о. теперь имеем три вектора OX, OY, AB
- ищем угол между векторами OX & AB
- ищем угол между векторами OY & AB
- сравниваем углы, какой меньше, в ту сторону и выпрямляем
- выпрямление происходит на длину вектора согласно шагу кисти

https://yadi.sk/d/K63ZmF-1iR4up
Изображения:
Тип файла: jpg approximation_of_line.jpg (46.6 Кб, 0 просмотров)
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук
Ответить с цитированием
  #8 (permalink)  
Старый 13.08.2015, 00:53
Аватар для nerv_
junior
Отправить личное сообщение для nerv_ Посмотреть профиль Найти все сообщения от nerv_
 
Регистрация: 29.11.2011
Сообщений: 3,924

Ну, что, товарищи, кто
1. расставит на этом (original) безобразии опорные точки (pivot_points)
2. и представит его в виде векторов (линий)
?
Изображения:
Тип файла: jpg original.jpg (42.0 Кб, 0 просмотров)
Тип файла: jpg pivot_points.jpg (53.8 Кб, 4 просмотров)
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук
Ответить с цитированием
  #9 (permalink)  
Старый 13.08.2015, 01:09
без статуса
Отправить личное сообщение для Deff Посмотреть профиль Найти все сообщения от Deff
 
Регистрация: 25.05.2012
Сообщений: 8,219

Мне лениво, как то пытался решить задачу векторизации пути проложенного карандашом по клеточной бумаге(Хотел заскриптить студенческую игрушку векторных гонок(на проложенном карандашом маршруте) на уч. парах) - не добил...
Кстать привязка к координатной сетке и расчет минимально-необходимого вектора(в пикселах) упрощают задачу
Ксать лабиринт тож лучше перепарсивать с привязкой к сетке, ибо криворукий - несимпатичен
По идее там либо вертикальные линии, либо горизонтальные - иных нет(в отличие от маршрута векторных гонок)

Последний раз редактировалось Deff, 13.08.2015 в 01:17.
Ответить с цитированием
  #10 (permalink)  
Старый 13.08.2015, 09:39
Аватар для Paguo-86PK
Профессор
Отправить личное сообщение для Paguo-86PK Посмотреть профиль Найти все сообщения от Paguo-86PK
 
Регистрация: 16.09.2009
Сообщений: 253

Алгоритм - бета-вариант
Сообщение от nerv_ Посмотреть сообщение
Описываю ниже свое понимание

Упрощенный вариант
1. определить размер кисти
2. выпрямить линии
3. сжать до "однопиксельных" размеров

Попытаюсь описать как

на примере конкретно взятой линии
- имеем точки, описывающие линию (A - начало, B - конец)
- строим вектор AB по этим точкам (выделено зеленым)
- помещаем его в двумерную координатную плоскость (x-y) так, как показано на рисунке
- т.о. теперь имеем три вектора OX, OY, AB
- ищем угол между векторами OX & AB
- ищем угол между векторами OY & AB
- сравниваем углы, какой меньше, в ту сторону и выпрямляем
- выпрямление происходит на длину вектора согласно шагу кисти
Я это примерно и делаю.

Чтобы не быть голословным, в архиве - мой сырейщий алгоритм (работает лишь в Opera 12 и FireFox почему-то А chrome только с --disable-web-security) и gif-лабиринт, который выдаёт пачку дублирующих линий. Нужно, как в п.1, определить размер кисти и учитывать его.

(в gif'ке первый кадр я подправил так, чтобы чтение начиналось с нужной позиции: В идеале, чтение начинается с кольца (восток+юг+запад+север) и если в кадре лабиринт перевёрнут, алгоритм должен это учитывать. Но до этого пока очень далеко)
Вложения:
Тип файла: zip reader.zip (11.7 Кб, 4 просмотров)

Последний раз редактировалось Paguo-86PK, 13.08.2015 в 11:15.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
JavaScript проход лабиринта sinkalexęą Общие вопросы Javascript 1 07.12.2013 11:29