Определите, образует ли набор плиток на сетке замкнутую форму

Учитывая набор плиток на сетке, я хочу определить:

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

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

Поэтому моя первоначальная мысль заключалась в том, что, поскольку я проверял правильность цепочки каждый раз, когда игрок шел, когда игрок поднял палец, я мог проверить, были ли первые и последние плитки соседними. (Я уже знаю, что они одного цвета.) Если бы они были рядом, у меня была догадка, что я сделал закрытую фигуру, и я собирался прийти сюда, чтобы попытаться выяснить, упустил ли я что-то большое, и получить какое-то логическое / математическое доказательство того, что моя догадка была верной (или пример, доказывающий, что это неверно).

Но вот когда я подумал о пункте 2: я также должен учитывать цепочки, которые используют край доски в качестве стороны прилагаемой фигуры. В этом случае первый и последний элементы в цепочке не будут смежными, но у меня все равно будет приложенная фигура. Так что теперь я немного вернулась на круги своя.

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

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

1. Цепочка не образует вложенную фигуру.

2. Цепочка делает замкнутую фигуру.

3. Если вы посчитаете стороны доски как ребро (или более чем одно ребро) фигуры, цепочка образует замкнутую фигуру.

4. Цепочка создает замкнутую фигуру, но есть дополнительные точки данных (правильно выбранные пользователем как часть цепочки), которые не являются частью создаваемой фигуры.

Случай 4 самый хитрый, потому что вам нужно извлечь «лишние» звенья цепи, чтобы найти прилагаемую фигуру и кусочки, которые попадают внутрь нее (но не вокруг «незакрытой» области).

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

1. Обнаружение петли плиток

Проблема кажется похожей на обнаружение цикла (цикла) в графе, см. Здесь или здесь .

• Множество узлов Vэтого графа G=(V, E)- это плитки,
• грань e = (v1, v2)существует между двумя различными узлами, если плитки являются прямыми или диагональными соседями

2. Обработка границы экрана

Граница экрана состоит из тех воображаемых плиток, которые образуют один край плитки шириной вокруг экрана видимых плиток.

Согласно вашей спецификации часть границы экрана будет формировать неявную часть замкнутого цикла. Просто для обнаружения замкнутого цикла было бы достаточно расширить граф Gдо графа G', соблюдая соединение с помощью этого правила:

• между любыми двумя разными узлами существует другая грань, если каждая из двух плиток расположена непосредственно возле границы экрана

Таким образом, плитки в точках (0,0) и (1,0) будут частью замкнутого цикла вместе с «граничными плитками» (-1,0), (-1, -1), (0, -1) , (1, -1).

3. Внутренняя часть зацикленной области

Я бы пошел в том же направлении, что и пользователь Артур Вульф Уайт :

Ограничивая набор плиток, мы должны рассмотреть ограничивающую рамку плиток цикла.

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

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

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

ffbb == extbb

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

ffbb < extbb

Начальная начальная плитка для заливки может быть любой плиткой, extbbкоторая является свободной плиткой. Может быть, случайный выбор - лучший подход.

Если бы я до этого знал, что внутренняя часть меньше внешней, я бы начал с центра масс точек петли, который находится во внутренней части для многих областей (контрпример: область в форме буквы С), в противном случае - на границе extbb. Но я понятия не имею, как это оценить.

Заключительные замечания

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

Ниже приведен пример, где внутренняя часть не подключена, с другой стороны, при обнаружении цикла должны быть обнаружены две петли, в этом случае одну следует отбросить.

Вы можете решить эту проблему следующим образом:

1. Нахождение ограничительной рамки этой формы.
2. Увеличение его размера на 1 в каждом направлении.
3. Итерирование по рамке нового слегка увеличенного ограничивающего прямоугольника и применение заливки.
4. Если есть какие-либо тайлы, которые вы не пометили заливкой, которых нет в этой цепочке, то они будут заключены. Я предполагаю, что по вашему определению, если есть вложенные плитки, то фигура является закрытой фигурой.

Для того, чтобы сделать один, перебрать все плитки на цепи и найти их minX, minY, maxXи maxYи что ваш ограничивающий прямоугольник или AABB.

Два тривиально.

Итерация по фрейму проста, просто убедитесь, что не залиты за пределы сетки. Вы можете узнать, как заполнить Википедию .

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

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

Во-первых, нам нужно определить проблему. Я собираюсь предположить, что ситуация выглядит как (2), то есть любой хвост был удален, и конец соединяется обратно с началом, так что у каждой плитки есть ровно один «предшественник» и ровно один «преемник» в цепочке. (где предшественником наследника плитки X всегда является плитка X). Кроме того, если вы достаточно долго следуете за «преемниками», вы в конечном итоге вернетесь к тому, с чего начали. Вы можете использовать предложение Гургадургена, чтобы определить, действительно ли петля пересекает себя в любой точке. Предполагая, что вы заканчиваете ввод пользователя, когда он это делает, он будет выглядеть как ряд последовательностей узлов в строке, за которым следует цикл. Вы можете лишить линии, чтобы получить петлю.

Теперь мы для каждой строки делаем следующее:

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

Теперь возьмите все плитки, которые есть, добавьте плитки на границе (включая хвост, если вы сняли его раньше или нет, на ваш выбор), и назовите этот регион.

Если вы хотите разрешить пользователю использовать границы, помните, что это не определяет и IN / OUT на плате, а просто делит его на две части. Вы можете выбрать меньшую область, например, или потребовать, чтобы пользователь использовал две смежные стороны (т.е. левую и нижнюю, но не верхнюю / нижнюю или левую / правую).

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