И компьютер тоже…

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

В этой статье я расскажу об алгоритме, который я использовал для обнаружения фигур. Я знаю, что в реальном мире параметров гораздо больше, и иногда может быть намного сложнее обнаружить определенные формы, особенно абстрактные, которые состоят из дуг, но этот алгоритм по-прежнему хорошо работает и полезен для большинство случаев использования. Алгоритм предполагает, что мы работаем в 2D-пространстве и создадим набор нормализованных векторов, крик, прямоугольник или любую заранее заданную форму в заданном атласе фигур. Если вы хотите сразу перейти к делу, тогда реализация алгоритма JS может быть использована в следующем репозитории Git: github.com/Appfairy/shapeit.

Без дальнейших действий давайте пройдемся по алгоритму!

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

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

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

  • Если круг не был найден, уменьшите уровень детализации многоугольника, склеивая вершины, которые вызывают незначительное изменение угла.

  • Иногда мы можем ограничиться одним вектором или набором векторов, если в данном эскизе не было замкнутой области.

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

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

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

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

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

  • Для шкалы мы просто вычислим среднюю длину всех векторов и разделим 2 значения, чтобы найти правильное умножение.
  • Для угла мы повторим тот же процесс, но, кроме того, мы попробуем разные варианты радианов (пусть r - средний радиан многоугольника): r, -r, π + r, π - r, r + .5π, -r - .5π, .5π - r, 1.5π + r.
  • Мы повторим согласование углов для зеркальной версии формы, иначе говоря, в другом «направлении».
  • Мы разместим масштабированную, повернутую и (потенциально) зеркально отраженную фигуру и поместим ее центр поверх центра нарисованного многоугольника.
  • Из всех преобразованных фигур с разными вариациями угла мы выберем ту, у которой среднее отклонение вершин будет наименьшим по сравнению с вершинами нарисованного многоугольника.

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

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

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