Jako, że ten wpis publikuję w Wigilię Bożego Narodzenia dlatego przy okazji chciałbym wszystkim czytającym życzyć Wesołych Świąt i samych udanych kompilacji ;)
A teraz do rzeczy. Ponieważ ciężko jest znaleźć w polskim Internecie jakiś sensowny opis algorytmu SAT, dlatego postanowiłem napisać krótki artykuł na temat jego działania. Ponieważ całość mam zapisaną jako plik pdf, dlatego uznałem, że nie ma sensu dublować tekstu i dlatego po prostu umieszczam link do pliku: Algorytm SAT
Opisany sposób na sprawdzanie czy okrąg przecina wielokąt jest błędny, gdyż sprawdza jedynie czy jakiś punkt wielokąta znajduje się wewnątrz okręgu, przecinać jednak może się również jedynie krawędź