Решаем беспорядок картины!

Question

Какой алгоритм вы бы использовали на компьютере, если вы хотите решить беспорядочную картинку?

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

Спасибо

Answer 1

Что вам нужно сделать, это определить словарь индексации для каждой грани мозаики, так чтобы индекс правого края мог сказать вам, каков индекс соответствующего левого края (например, простой словарь: «выпуклый» и «вогнутый», с «выпуклым» на лице, подразумевающим «вогнутый» на соответствующем противоположном лице), а затем классифицирует каждый фрагмент в соответствии с индексным словарем. Чем тоньше словарный запас, тем более различим подбор лиц и тем быстрее будет работать ваш алгоритм, как бы вы его не реализовали. (Например, у вас может быть «плоский край, прямой край-наклон слева, прямой-наклон наклон вправо, вогнутый, выпуклый, ручка, отверстие-ручка, ...). Мы предполагаем, что схема индексации абстрагирует фактическая форма края и наличие предиката «точно совпадает (piece1, edge1, piece2, edge2)», который имеет значение true, только если края точно совпадают. Далее мы предполагаем, что существует не более одного точного соответствия элемента с определенным краем.

Цель состоит в том, чтобы вырастить набор регионов, например, набор связанных частей, до тех пор, пока больше не будет возможности вырастить регионы. Сначала мы помечаем все фрагменты с уникальными именами регионов, по 1 на фрагмент, и по всем ребрам как несопоставленные. Затем мы перечисляем ребра куска в любом порядке. Для каждого перечисляемого элемента P с ребром E используйте схему индексации, чтобы выбрать потенциально совпадающие пары элемент / ребро. Проверьте предикат точно подходит; не более одного куска Q с ребром F точно совпадает. Объедините области для P и Q вместе, чтобы сделать большую область. Повторение. Я думаю, что это решает загадку.

Answer 2

.1 Найдите 2x2-грамма , чтобы все четыре ребра уместились. Затем оцените, насколько хорошо содержимое изображения соответствует друг другу.

  P1 <--> P2
  ^       ^
  |       |
  v       v
  P3 <--> P4

.2 тег ориентации (вручную или эвристически), но использовать их только как эвристические оценки (для ранжирования), а не как окончательные критерии поиска.

.3 Контекст формы

Answer 3

Чтобы прояснить ответ Ира Бакстера, еще один способ осмысления проблемы состоит в том, чтобы представить головоломку в виде графика, где каждая часть - это узел, а каждая поверхность с другой частью - ребро.

Например, если вы разрабатывали игру-головоломку, сохранение «ответа» таким образом сделало бы «проверку, подходит ли он» коду намного быстрее, поскольку его можно было бы уменьшить до некоторого вида поиска по хешу.

Answer 4

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

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