Комментарии 15
Тут важно как-то детектировать хотел ли пользователь изобразить примитивную фигуру или нет. А даже если фигура и сложная, типа звезды, например, то её всё равно было бы не плохо "распознавать".
Я думаю тут стоит идти в направлении сглаживания: детектировать точки повторота, а точки между ними апроксимировать кривыми безье. Тогда, например, можно будет нарисовать "пулю" и она будет представлена как равнобедренный треугольник с округлыми бёдрами.
А совсем идеально было бы ещё и учитывать симметрию, чтобы нарисованная "на глазок" звезда не только отображалась как многогранник, но и выглядела красиво. Для этого надо немного смещать углы, выбрав подходящий тип симметрии.
Изначально у меня не было задачи распознавать сложные фигуры вроде звезд. Поэтому я выбрал алгоритм хорошо работающий на выпуклых многоугольниках. Однако, если это будет интересно сообществу, я могу попробовать реализовать алгоритм с определением точек поворота.
Конечно интересно. Я думаю к своему вайтборду что-то такое прикрутить, но всё руки не доходят. Пока что есть лишь сглаживание кривых.
.
Ну и поскольку алгоритм ориентирован на выпуклые многоугольники — вполне логично, что он не может распознать эллипсы. Для эллипсов нужен отдельный алгоритм, и отдельный этап определения, какой из них лучше аппроксимирует данные пользователя (например, через среднеквадратичное отклонение).
Спасибо. В репозитории я уже добавил простое распознавание эллипсов. Позже добавлю отдельное ядро, чтобы алгоритм точнее выбирал их размер и угол поворота.
Действительно, выбор эллипс/многоугольник лучше делать на основании того, что больше похоже на закорючку пользователя. После реализации эллипсов, постараюсь добавить выбор по лучшей аппроксимации.
Данное ядро было выбраноА вы пробовали другие варианты? Я бы ещё попробовал более острые и с уходом в отрицательную область,
На момент написания статьи, ядро с квадратом — третий вариант, первые два работали хуже. Сейчас я изменил его такой вариант: 
, рассчитанный на 3-5 угольники.
выглядит так (немного более острый пик)
К сожалению, ядро с ярко выраженным пиком плохо различает тупые углы, из-за чего трапеции часто распознаются как треугольники.
Пример неправильного распознавания трапеции
К сожалению, ядро с ярко выраженным пиком плохо различает тупые углы, из-за чего трапеции часто распознаются как треугольникиИз чего к сожалению следует, что такой алгоритм является неустойчивым и требует доработки. Потому что небольшие различия в ядре фильтра не должны приводить к настолько фатальным последствиям.
Мне кажется, что такой эффект будет наблюдаться в любом алгоритме, использующем пороговые значения. Например, если пользователь достаточно криво нарисовал ребро, то, в зависимости от фильтра, ребро может разделяться дополнительной вершиной или оставаться прямым (как в примере с трапецией). Тем не менее насчет доработки я с вами согласен — здесь еще есть над чем работать.
1) считает среднее арифметическое,
2) вычитает его из исходных данных,
3) для каждой точки считает модуль и аргумент (те самые расстояние и угол),
4) определяет дискретную (уже действительную) функцию как модуль от аргумента,
5) фильтрует её фильтром высоких частот,
6) по локальным максимумам выбирает узловые точки.
Возможно, такое описание и может показаться переусложнённым — но зато оно более математически прозрачно. В частности, можно фильтровать и исходные данные тоже (например, чтобы получить веса перед вычислением центра или в качестве множителя аргумента), оптимальный фильтр высоких частот выбирать исходя из его спектральных характеристик, а шаги 1, 3 и 4 могут и вообще не понадобится.
Мне не удалось найти понятное описание этого алгоритма. Поэтому мне сложно представить как реализовать описанный вами аглоритм в коде, чтобы проверить его на реальных данных. Буду благодарен, если вы сможете дать ссылку на соответствующую статью или литературу. Боюсь, что без понимания этого алгоритма я не готов к дальнейшей дискусии.
Здесь в качестве ядра свёртки используется квадрат треугольного окна, и для детектирования углов можно использовать не только расстояние, но и угол по отношению к касательной фильтрованного набора точек.
Думаю, вам будет полезна книга Введение в контурный анализ; приложение к обработке изображений и сигналов.
Распознаем простые фигуры по массиву точек