Oś Świata/Kolokolo Bird

O przecinaniu się wielokątów

29.05
2016

Dziś problem geometryczny. A może informatyczny? Problem, na jaki się natknąłem przy okazji przetwarzania obrazów satelitarnych, ale obecny i w innych dziedzinach, choćby grafice komputerowej.

Odpowiedzieć nań można na wiele sposobów, od dostępnego dla gimnazjalisty, po odlotowe pomysły uczonych zręcznych (doktorów habilitowanych) fizyki teoretycznej.

PROBLEM:
Mamy płaszczyznę. Zwykłą, euklidesową (czy raczej kartezjańską), żadnych cudów, zwykła geometria, kartka papieru. Na tej płaszczyźnie mamy dany wielokąt — zadany nam przez jego wierzchołki (w wersji obliczeniowej: znamy ich współrzędne kartezjańskie). Mamy też drugi wielokąt, zadany w taki sam sposób. Należy podać przepis (napisać programik, określić algorytm) rozstrzygający, czy te dwa wielokąty mają część wspólną, czy też są rozłączne.
O wielokątach nie wiemy nic specjalnego, w szczególności nie muszą być wypukłe, nie wiemy nawet, czy ich wierzchołki zostały nam zadane w kolejności wskazówek zegara, czy przeciwnej, nie wiemy, ile mają boków — każdy może mieć inną ich liczbę.

Bardzo polecam zastanowienie się nad problemem. Zadajcie też problem swoim gimnazjalno-licealnym dzieciom (Moniko!)
Liczę na odpowiedzi.

Mam dwa, wzajemnie sprzeczne, kryteria oceny odpowiedzi:
1. efektywność numeryczna (jak szybko komputer może to rozstrzygnąć);
2. elegancja/piękno/pomysł idei matematycznej za tym stojącej.
No i, oczywiście, wstępne kryterium konieczne:
0. rozwiązanie powinno być prawdziwe-poprawne.

Jak na razie, to najbardziej podoba mi się przepiękny pomysł (choć dość niepraktyczny obliczeniowo) z twierdzenia o residuach. Roger Penrose byłby nim zachwycony. Ale da się z tego zrobić ilustrację sensu twierdzenia o residuach. Właśnie penrose’owską w stylu: czyli co logarytmy mają wspólnego z kątami, i czym różni się kręcenie się na fotelu trochę w lewo i trochę w prawo, od okręcenia się w kółko.

No i poza tym mam kilka poprawnych, szkolnych, lepiej lub gorzej zoptymalizowanych numerycznie, rozwiązań na poziomie geometrii gimnazjalnej (no może, w dzisiejszych spsiałych czasach, licealnej).

5
Dodaj komentarz

5 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
avataravatar Recent comment authors
  Subscribe  
najnowszy najstarszy oceniany
Powiadom o
avatar
Gość
monikasz

Ponownie mi dziecko do tablicy wywołujesz, a on teraz na jakimś innym etapie chyba jest… ech, to gimnazjum, a może ten wiek… To zadanie maturalne mu pokazałam, ale on niestety o konstrukcji ma słabe pojęcie, zabrał się do tego analitycznie, żeby potem na koniec ewentualnie „przeliczyc” to cyrklem i linijką, za dużo mu tam po drodze ciekawych/trudnych bocznych uliczek sie pokazało, w końcu to zostawił. A to o czym teraz mówisz, to hm… ja jestem zdaje się z tych, co to odpadli na residuach, bo pamiętam, że było, ale nie pamiętam co. Jak wiele rzeczy na studiach: niekoniecznie trudne, ale… Czytaj więcej »

avatar
Gość
monikasz

Prawo Gaussa? To chyba na tym tle mnie tego uczono, wieki temu…
A opowiedziane po ludzku to rzeczywiście jest proste, a jednocześnie… inspirujące, rzeczywiście coś dla Pawła. Dziecię wróci przewietrzone, to mu wrzucę, dzięki. 🙂