Policz liczbę boków wielokąta

Robot liczący po stronie wielokąta postanowił podróżować po świecie bez uprzedzenia, ale ważne jest, aby proces liczenia wielokątów nie był zatrzymywany zbyt długo. Masz więc następujące zadanie: Biorąc pod uwagę czarno-biały obraz wielokąta, twój program / funkcja powinna zwrócić liczbę stron.

Program zostanie dostarczony do starego komputera z kartami dziurkacza, a ponieważ karty dziurkacze są obecnie bardzo drogie, lepiej postaraj się, aby twój program był jak najkrótszy.

Krawędzie mają co najmniej 10 pikseli długości, a kąty utworzone przez dwie sąsiednie krawędzie wynoszą co najmniej 10 °, ale nie więcej niż 170 ° (lub ponownie więcej niż 190 °). Wielokąt jest całkowicie zawarty w obrazie, a wielokąt i jego dopełnienie są połączone (nie ma izolowanych wysp), więc to wejście nie byłoby poprawne:

Punktacja

To jest kodegolf, co oznacza, że ​​wygrywa najkrótsza przesyłana bajtowa przesyłka, która musi znaleźć prawidłową liczbę krawędzi dla każdego przypadku testowego. (Przesyłanie powinno działać również w innych przypadkach, optymalizacja tylko tych przypadków testowych jest niedozwolona).

Jeśli chcesz przesłać rozwiązanie, które za każdym razem nie znajduje poprawnego numeru, możesz je również przesłać, ale będzie ono umieszczane w rankingu za wszystkimi przesłanymi, które działają lepiej.

Podaj całkowitą liczbę w tytule zgłoszenia. (Błąd całkowity suma różnic bezwzględnych między rzeczywistą liczbą stron a każdym wyjściem).

Przypadki testowe

n = 10

n = 36

n = 7

n = 5

To nie jest przypadek testowy, tylko z ciekawości: ile masz krawędzi dla tego wejścia?

Python 2 + PIL, bez błędów, 313 307 bajtów

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

Pobiera nazwę pliku obrazu w wierszu polecenia i drukuje wynik do STDOUT.

Podaje poprawny wynik dla wszystkich testów, a n = 28 dla koła.

Wyjaśnienie

Algorytm działa, idąc wzdłuż obwodu wielokąta i licząc liczbę napotkanych wierzchołków (wykrytych jako zmiany kierunku). Zaczynamy od piksela najbardziej oddalonego od początku, októry z pewnością jest wierzchołkiem, a zatem przylega do krawędzi (tj. Granicy między pikselem pierwszego planu i pikselem tła). Śledzimy naszą pozycję, pnajnowszy wierzchołek vi najnowszy „punkt kontrolny”, qz których wszystkie są początkowo równe o. Śledzimy również kierunek krawędzi dwzględem bieżącego piksela; dpoczątkowo wskazuje wschód, co jest bezpiecznym kierunkiem, ponieważ wiemy, że jest krawędź na wschód odo, inaczej nie byłoby to najdalsze od pochodzenia. Poruszamy się wzdłuż krawędzi, w kierunku prostopadłym do punktów po naszej lewej stronie, tj. W kierunku zgodnym z ruchem wskazówek zegara. Ilekroć „spadamy z krawędzi”, tj. W każdej sytuacji, w której znajduje się poza wielokątem lub gdy piksel po naszej lewej stronie (tj. W kierunku ) znajduje się wewnątrz wielokąta, dostosowujemy i odpowiednio przed wznowieniem.d takiego, którydpdpd

Za każdym razem, gdy odległość między postatnim punktem kontrolnym, a qstaje się większa niż 5, staramy się ustalić, czy minęliśmy wierzchołek między qi p: Porównujemy kąt między vq(tj. Wektorem od vdo q), który jest ogólnym kierunkiem bok wieloboku, którym szliśmy, gdy dotarliśmy do ostatniego punktu kontrolnego, oraz qpprzesunięcie między ostatnim punktem kontrolnym a bieżącą pozycją. Jeśli kąt jest większy niż około 10 °, dochodzimy do wniosku, że idziemy wzdłuż innej strony wielokąta, zwiększamy liczbę wierzchołków i ustawiamy vbieżący wierzchołek na p. W każdym punkcie kontrolnym, niezależnie od tego, czy wykryliśmy wierzchołek, czy nie, aktualizujemyq ostatni punkt kontrolny dop. Kontynuujemy w ten sposób, aż wrócimy odo punktu początkowego i zwrócimy liczbę znalezionych wierzchołków (zauważ, że liczba wierzchołków wynosi początkowo 1, ponieważ punktem początkowym ojest sam wierzchołek).

Poniższe obrazy pokazują wykryte wierzchołki. Zauważ, że biorąc p, bieżąca pozycja w każdym punkcie kontrolnym, ponieważ pozycja nowego wierzchołka nie jest optymalna, ponieważ prawdziwy wierzchołek jest prawdopodobnie gdzieś pomiędzy ostatnim punktem kontrolnym qi pwzdłuż obwodu. Jak widać, wszystkie wierzchołki inne niż pierwszy (ogólnie prawy dolny wierzchołek) są nieco oddalone. Naprawienie tego kosztowałoby więcej bajtów, ale wydaje się, że działa wystarczająco dobrze, jak jest. Biorąc to pod uwagę, trudno jest nie nadużywać tylko czterech przypadków testowych.