Подсчитайте количество сторон на многоугольнике

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

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

Края имеют длину не менее 10 пикселей, а углы, образованные двумя примыкающими краями, составляют не менее 10 °, но не более 170 ° (или снова больше 190 °). Многоугольник полностью содержится в изображении, и многоугольник, а также это дополнение связано (там нет изолированных островов) , так что этот вход будет не действителен:

счет

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

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

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

Контрольные примеры

п = 10

п = 36

n = 7

п = 5

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

Python 2 + PIL, без ошибок, 313 307 байт

from Image import*
I=open(sys.argv[1])
w,h=I.size;D=I.getdata()
B={i%w+i/w*1j for i in range(w*h)if D[i]!=D[0]}
n=d=1;o=v=q=p=max(B,key=abs)
while p-w:
 p+=d*1j;e=2*({p}<B)+({p+d}<B)
 if e!=2:e%=2;d*=1j-e*2j;p-=d/1j**e
 if abs(p-q)>5:
    t=(q-v)*(p-q).conjugate();q=p;w=o
    if.98*abs(t)>t.real:n+=1;v=p
print n

Принимает имя файла изображения в командной строке и печатает результат в STDOUT.

Дает правильный результат для всех тестов, и n = 28 для круга.

объяснение

Алгоритм работает путем обхода периметра многоугольника и подсчета количества встреченных вершин (определяется как изменение направления). Мы начинаем с пикселя, самого дальнего от начала координат, oкоторый гарантированно будет вершиной и, следовательно, будет смежным с ребром (то есть границей между пикселем переднего плана и фоновым пикселем). Мы отслеживаем нашу позицию, pсамую последнюю вершину vи самую последнюю «контрольную точку» q, все из которых изначально равны o. Мы также отслеживаем направление края dотносительно текущего пикселя; dизначально указывает на восток, что является безопасным направлением, поскольку мы знаем, что к востоку отoиначе он не был бы самым дальним от источника. Мы движемся вдоль края в направлении, перпендикулярном dтакому, которое dуказывает на нашу левую сторону, то есть в направлении по часовой стрелке. Всякий раз, когда мы «падаем с края», т. Е. В любой ситуации, где pнаходится за пределами многоугольника или когда пиксель слева от нас (то есть в направлении d) находится внутри многоугольника, мы корректируемся pи dсоответственно перед возобновлением.

Каждый раз, когда расстояние между pи до последней контрольной точки, qстановится больше 5, мы пытаемся определить, прошли ли мы через вершину между qи p: Мы сравниваем угол между vq(т. Е. Вектором от vдо q), который является общим направлением сторона многоугольника, по которой мы шли, когда мы достигли последней контрольной точки, и qpсмещение между последней контрольной точкой и текущей позицией. Если угол больше примерно 10 °, мы заключаем, что идем по другой стороне многоугольника, увеличиваем количество вершин и устанавливаем vтекущую вершину равной p. На каждой контрольной точке, независимо от того, обнаружили ли мы вершину или нет, мы обновляем qпоследнюю контрольную точку доp, Мы продолжим в том же духе, пока не вернемся в oначальную точку и не вернем количество найденных вершин (обратите внимание, что число вершин изначально равно 1, поскольку начальная точка oсама является вершиной.)

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