Zasada jednej ręki. Jak znaleźć wyjście z labiryntu Wynik procedury

Na skrzyżowaniach preferuj nieoznaczone szlaki. Za każdym razem, gdy dojdziesz do skrzyżowania, poświęć chwilę, aby spojrzeć na oznaczenia na każdym szlaku. Niektóre z nich mogą być nieoznaczone, podczas gdy inne pokażą, że wybrałeś je już raz (lub dwa razy). Warto dawać pierwszeństwo szlakom bez oznaczeń. W ten sposób masz większe szanse na pójście do przodu. Jeśli wszystkie szlaki są oznaczone raz, wybierz losowo jeden.

Unikaj szlaków oznaczonych dwukrotnie. Jeśli jesteś zmuszony podążać ścieżką, którą już raz oznaczyłeś, powinieneś zaznaczyć ją po raz drugi. Zgodnie z algorytmem Luc-Tremaux, podwójnie oznaczony szlak nie zaprowadzi Cię do wyjścia. Jeśli znajdziesz skrzyżowanie, na którym ta sama ścieżka jest oznaczona dwukrotnie, zawsze wybieraj inną ścieżkę, nawet jeśli oznacza to konieczność zawrócenia.

Wróć, jeśli trafisz w ślepy zaułek. Jeśli dotrzesz do ślepego zaułka, musisz wrócić do ostatniego skrzyżowania, które przejechałeś. Nie zapomnij oznaczyć ścieżki, aby wiedzieć, że prowadzi do ślepego zaułka. Po dotarciu do skrzyżowania wybierz jedną z pozostałych ścieżek i kontynuuj labirynt.

Dzień dobry, droga społeczności.

tło

Pewnego pięknego dnia, spacerując po Internecie, znaleziono labirynt. Ciekawe stało się odnalezienie jego przejścia i po przejściu przez sieć nadal nie znalazłem działającej implementacji oprogramowania, rozwiązania labiryntu.

Tutaj jest:

Dzień pracy był nudny, nastrój był znakomity. Cel, środki i wola są tam. Wniosek jest oczywisty, przejdziemy.

Fabuła

Dla wygodnego rozwiązania konieczne jest sprowadzenie istniejącego obrazu labiryntu do typu dwuwymiarowej tablicy. Każdy element może przyjąć jedną z 3 wartości:

Stała ŚCIANA=-1; PUSTE=-2; NIERUCHOMY BLOK=-3;

Najpierw chcę pokazać funkcje skanowania obrazu labiryntu, następnie zapisywania danych do tablicy oraz funkcję generowania nowego obrazu na podstawie danych z tablicy:

Skanowanie obrazu:

zmN:liczba całkowita=600; LABIRINT: tablica liczb całkowitych; ... varbit:TBitmap; i,j:liczba całkowita; początek bitu:=TBitmap.Create; Jeśli OpenDialog1.Execute, rozpocznij bit.LoadFromFile(OpenDialog1.FileName); dla i:=0 do N wykonaj dla j:=0 do N wykonaj jeśli bit.Canvas.Pixels=clWhite to LABIRINT:=BLANK else LABIRINT:=WALL; bit.Bezpłatny; ... koniec; koniec; ...

Generowanie obrazu:

zmN:liczba całkowita=600; LABIRINT: tablica liczb całkowitych; ... procedura genBitmap; varbit:TBitmap; i,j: liczba całkowita; początek bitu:=TBitmap.Create; bit.Szerokość:=N+1; bit.Wysokość:=N+1; dla i:=0 do N wykonaj dla j:=0 do N zacznij, jeśli LABIRINT=BLANK then bit.Canvas.Pixels:=clWhite // inaczej if LABIRINT=WALL then bit.Canvas.Pixels:=clBlack inaczej bit.Canvas .Piksele:=clRed; koniec; bit.SaveToFile("tmp.bmp"); bit.Bezpłatny; koniec; ...

Najpierw musisz ponownie zapisać obraz jako monochromatyczny bmp, aby mieć 2 kolory biały lub czarny. Jeśli przyjrzysz się uważnie labiryntowi, ma on ścianę o grubości 2 pikseli i drogę o grubości 4 pikseli. Idealnie byłoby, aby grubość ściany i drogi wynosiła 1 piksel. Aby to zrobić, musisz przebudować obraz, podzielić obraz przez 3, czyli usunąć co 2 i 3, rząd i kolumnę pikseli ze zdjęcia (nie wpłynie to na poprawność i przejezdność labiryntu).

Przygotowany rysunek:

Szerokość i wysokość obrazu: 1802 piksele.

1. Użyj funkcji skanowania obrazu.
2. Przebuduj obraz:

zmN:liczba całkowita=1801; LABIRINT: tablica liczb całkowitych; ... procedura rebuildArr2; zmienna i,j:liczba całkowita; zacznij od i:=0 do ((N dziel 3)) wykonaj dla j:=0 do ((N dz 3)) wykonaj LABIRINT:=LABIRINT; N:=N dział 3; koniec; ...

3. Generujemy przebudowany obraz.

Wynik zabiegu:

Szerokość i wysokość obrazu: 601 pikseli.

I tak mamy obraz labiryntu pożądanego typu, teraz najciekawsze jest wyszukiwanie wszystkich opcji przejścia labiryntu. Co my mamy? Tablica z zapisanymi wartościami ŚCIANA – ściana i BLANK – droga.

Była jedna nieudana próba znalezienia przejścia labiryntu za pomocą algorytmu falowego. Dlaczego nieudany, we wszystkich próbach ten algorytm prowadził do błędu „Stack Overflow”. Jestem na 100% pewien, że korzystając z niego można znaleźć opis przejścia, ale był bezpiecznik, aby wymyślić coś ciekawszego.

Pomysł nie pojawił się od razu, było kilka realizacji przejścia, które z czasem działały przez około 3 minuty, po czym przyszedł wgląd: „a co jeśli nie szukamy ścieżek przejścia, ale ścieżek, które nie prowadzą do przejście labiryntu i oznacz je jako ślepe zaułki.”

Algorytm jest następujący:
Uruchom funkcję rekurencyjną we wszystkich punktach dróg labiryntu:
1. Jeśli stoimy na drodze i wokół nas są 3 ściany, miejsce w którym stoimy oznaczamy jako ślepy zaułek, w przeciwnym razie wychodzimy z funkcji;
2. Przechodzimy do miejsca, które nie jest ścianą z punktu nr 1 i powtarzamy punkt nr 1;

Implementacja oprogramowania:

zmN:liczba całkowita=600; LABIRINT: tablica liczb całkowitych; ... procedura setBlankAsDeadblockRec(x,y:integer); vark:liczba całkowita; początek:=0; jeśli LABIRINT=blank to zacznij, jeśli LABIRINT<><><><>PUSTE następnie k:=k+1; jeśli k=4 to LABIRINT:=DEADBLOCK; jeśli k=3 to zacznij LABIRINT:=DEADBLOCK; jeśli LABIRINT=BLANK to ustaw BlankAsDeadblockRec(x-1,y); jeśli LABIRINT=BLANK to ustaw BlankAsDeadblockRec(x,y-1); jeśli LABIRINT=BLANK to ustaw BlankAsDeadblockRec(x+1,y); jeśli LABIRINT=BLANK to ustaw BlankAsDeadblockRec(x,y+1); koniec; koniec; koniec; procedura setDeadblock; zmienna i,j:liczba całkowita; rozpocznij dla i:=1 do N-1 wykonaj dla j:=1 do N-1 wykonaj setBlankAsDeadblockRec(i,j); koniec; ...

Wniosek

Mam "kompletny" działający algorytm, którego można użyć do znalezienia całej drogi przez labirynt. Ten ostatni przekroczył wszelkie oczekiwania pod względem szybkości. Mam nadzieję, że moja mała praca przyniesie komuś korzyść lub popchnie do nowych myśli.

Kod programu i zaliczony labirynt:

//Proszę nie kopać mnie za język programowania, którego używałem. jednostka Jednostka1; interfejs wykorzystuje Windows, Graphics, Forms, Dialogs, ExtCtrls, StdCtrls, Controls, Classes; const ŚCIANA=-1; PUSTE=-2; NIERUCHOMY BLOK=-3; wpisz TForm1 = class(TForm) Button1: TButton; OpenDialog1: TOpenDialog; procedura Button1Click(Sender: TObject); private ( Deklaracje prywatne ) public ( Deklaracje publiczne ) koniec; var Form1: TForm1; N:liczba całkowita=600; LABIRINT: tablica liczb całkowitych; implementacja ($R *.dfm) procedura genBitmap; varbit:TBitmap; i,j: liczba całkowita; początek bitu:=TBitmap.Create; bit.Szerokość:=N+1; bit.Wysokość:=N+1; dla i:=0 do N wykonaj dla j:=0 do N zacznij, jeśli LABIRINT=BLANK then bit.Canvas.Pixels:=clWhite // inaczej if LABIRINT=WALL then bit.Canvas.Pixels:=clBlack inaczej bit.Canvas .Piksele:=clRed; koniec; bit.SaveToFile("tmp.bmp"); bit.Bezpłatny; koniec; procedura rebuildArr2; zmienna i,j:liczba całkowita; zacznij od i:=0 do ((N dziel 3)) wykonaj dla j:=0 do ((N dz 3)) wykonaj LABIRINT:=LABIRINT; N:=N dział 3; koniec; procedura setBlankAsDeadblockRec(x,y:integer); vark:liczba całkowita; początek:=0; jeśli LABIRINT=blank to zacznij, jeśli LABIRINT<>PUSTE następnie k:=k+1; jeśli LABIRINT<>PUSTE następnie k:=k+1; jeśli LABIRINT<>PUSTE następnie k:=k+1; jeśli LABIRINT<>PUSTE następnie k:=k+1; jeśli k=4 to LABIRINT:=DEADBLOCK; jeśli k=3 to zacznij LABIRINT:=DEADBLOCK; jeśli LABIRINT=BLANK to ustaw BlankAsDeadblockRec(x-1,y); jeśli LABIRINT=BLANK to ustaw BlankAsDeadblockRec(x,y-1); jeśli LABIRINT=BLANK to ustaw BlankAsDeadblockRec(x+1,y); jeśli LABIRINT=BLANK to ustaw BlankAsDeadblockRec(x,y+1); koniec; koniec; koniec; procedura setDeadblock; zmienna i,j:liczba całkowita; rozpocznij dla i:=1 do N-1 wykonaj dla j:=1 do N-1 wykonaj setBlankAsDeadblockRec(i,j); koniec; procedura TForm1.Button1Click(Sender: TObject); varbit:TBitmap; i,j:liczba całkowita; początek bitu:=TBitmap.Create; Jeśli OpenDialog1.Execute, rozpocznij bit.LoadFromFile(OpenDialog1.FileName); dla i:=0 do N wykonaj dla j:=0 do N wykonaj jeśli bit.Canvas.Pixels=clWhite to LABIRINT:=BLANK else LABIRINT:=WALL; bit.Bezpłatny; setDeadblock; genBitmapa; koniec; koniec; koniec.

Aby znaleźć najkrótszą ścieżkę, planowane jest zastosowanie algorytmu falowego do znalezionych fragmentów labiryntu. Ciekawe byłoby usłyszeć, do czego można zastosować inne algorytmy szybki znaleźć drogę w wielkim labiryncie?

Jedną z najprostszych zasad pokonywania labiryntu jest zasada „jednej ręki”: poruszając się po labiryncie należy zawsze dotykać jego ściany prawą lub lewą ręką. Algorytm ten był prawdopodobnie znany starożytnym Grekom. Będziesz musiał przejść długą drogę, wchodząc we wszystkie ślepe uliczki, ale w końcu cel zostanie osiągnięty. Chociaż ta zasada ma jedną wadę, porozmawiamy o niej później.

Spróbujmy opisać robota działającego zgodnie z zasadą „prawej ręki”.

Na początku swojej pracy robot musi znaleźć ścianę, za którą będzie podążał. Aby to zrobić, może po prostu iść do przodu, aż natrafi na przeszkodę.

Po uderzeniu w przeszkodę robot zaczyna się poruszać zgodnie z zasadą „prawej ręki”.

Poruszając się po ścianie robot sprawdza, czy po prawej stronie jest przejście. Jeśli jest przejście, robot musi nim podążać, aby nie oderwać się od ściany po prawej stronie.

Jeśli nie ma przejścia - przed nami jest ściana - robot skręca w lewo. Jeśli znowu nie ma przejścia, ponownie skręca w lewo, skręcając w ten sposób o 180 stopni i idzie w przeciwnym kierunku.

Schemat blokowy algorytmu dla robota działającego zgodnie z zasadą „prawej ręki” pokazano na rysunku.

Spróbujmy sprawdzić działanie tego algorytmu i napisać dla niego program. W tym celu przejdźmy do środowiska programistycznego. Środowisko to jest wygodnym narzędziem do modelowania różnych algorytmów związanych ze sterowaniem robotami. Ma wykonawcę żółwia, który w swoim rdzeniu jest niczym innym jak prawdziwym robotem. Żółw posiada bardzo wygodny zestaw poleceń - do przodu, w prawo, w lewo, w tył. Dodatkowo w centrum żółwia znajduje się czujnik, który przyjmuje wartość od 0 do 100, w zależności od odcienia powierzchni, na której się znajduje.

Dialekt języka Logo, którego będziemy używać, jest bardzo prosty i podobny do podstawowego. Możesz zapoznać się z poleceniami języka. Darmowe pobieranie środowiska programistycznego GameLogo - . Rozmiar dystrybucji jest niewielki - tylko 1 Mb.

Archiwum GameLogo zawiera tła z labiryntami, z których jeden wykorzystamy.

Na samym początku programu wydamy żółwiowi polecenie podniesienia pióra (domyślnie żółw zostawia za sobą ślad).

Rozmiar pola to 800 x 600 punktów. Pozycja początkowa żółwia znajduje się na współrzędnych 115 545 (biały kwadrat).

Kolor torów labiryntu jest jasny, na nich czujnik przyjmie wartości większe niż 50. Kolor ścian labiryntu jest ciemny, wartość czujnika będzie mniejsza niż 50. Wyjście z labiryntu jest reprezentowane przez czarny kwadrat, powyżej którego wartość czujnika będzie równa 0.

Zadeklarujmy zmienną flagową, za pomocą której będziemy kontrolować, czy osiągnięto wyjście z labiryntu.

Napiszmy program i uruchommy go za pomocą dużego czerwonego przycisku oznaczonego "Uruchom".

Zmienna flaga tła = maze1.gif podnieś punkt pisaka 115, 545 "szukaj pierwszej ściany powtarzaj, aż wskaźnik > 50 (do przodu 12) „zasada prawej ręki powtarzaj aż flaga = 0 (w prawo 90 do przodu 12 jeśli czujnik = 0 to flaga = 1 w przeciwnym razie jeśli czujnik

Jeśli wiadomo, że labirynt nie ma osobnych ścian, czyli nie ma zamkniętych tras, którymi można wrócić do punktu wyjścia, to taki labirynt nazywa się po prostu połączony i zawsze można go całkowicie ominąć, stosując „ jedna ręka”.

Jeśli w labiryncie znajdują się ściany wolnostojące, to stosując zasadę „jednej ręki” nie zawsze da się przejść przez wszystkie korytarze i ślepe zaułki. Labirynty z oddzielnymi ścianami i zamkniętymi ścieżkami nazywane są wielokrotnie połączonymi. Jednocześnie wielokrotnie połączone labirynty można podzielić na dwie grupy: bez „pętli” wokół bramki (zamknięta trasa nie omija bramki) oraz z zamkniętą „pętlą” wokół bramki (cel można ominąć na zamkniętej trasie).

W wielopołączonych labiryntach z drugiej grupy nie działa zasada „jednej ręki”, a przy jej użyciu niemożliwe jest osiągnięcie celu. Ale nawet te labirynty można przejść, opierając się na dokładnym algorytmie.

Rozwiązanie problemu takich labiryntów należy do stosunkowo późnych czasów i zostało zainicjowane przez Leonharda Eulera. Euler nie bez powodu wierzył, że wyjście z labiryntu można znaleźć, a co więcej, w stosunkowo prosty sposób.

Uniwersalny algorytm przechodzenia przez dowolne labirynty został opisany dopiero sto lat później w książce francuskiego matematyka E. Luca „Recreations matematiques”, opublikowanej w 1882 roku. Co ciekawe, opisując algorytm, Luca wskazał na prymat innego francuskiego matematyka, M. Tremaux. W ten sposób algorytm stał się znany jako Algorytm Lucasa-Tremo.

Tremo proponuje następujące zasady: opuszczając dowolny punkt labiryntu, należy postawić znak na jego ścianie (krzyż) i ruszyć w dowolnym kierunku w ślepy zaułek lub rozdroże; w pierwszym przypadku cofnij się, postaw drugi krzyżyk, wskazując, że ścieżka została przebyta dwukrotnie - w tę iz powrotem, i idź w kierunku, który nigdy nie był przebyty lub przebyty raz; w drugim - idź w dowolnym kierunku, zaznaczając każde skrzyżowanie przy wejściu i przy wyjściu jednym krzyżem; jeśli na skrzyżowaniu jest już jeden krzyż, to należy iść nową drogą, jeśli nie, to przebytą ścieżkę, zaznaczając ją drugim krzyżem.

Znając algorytm Tremo, możesz poprawić zachowanie legendarnego Tezeusza. Zainspirowany darem ukochanej Ariadny, pewnie przemierza labirynt. Nagle przed nim pojawia się przejście, wzdłuż którego nić została już rozciągnięta... Co robić? W żadnym wypadku nie przekraczaj jej, ale wracaj znaną już ścieżką, podwajając wątek, aż pojawi się kolejny nieprzebyty ruch.

Korzystając z wariantu algorytmu Tremo, ojciec teorii informacji, Claude Elwood Shannon, zbudował jeden z pierwszych samouczących się robotów. Shannon nadał mu dźwięczne imię „Tezeusz”, ale w historii „Tezeusz” stał się lepiej znany jako „mysz” Shannona. „Mysz” najpierw zbadała cały labirynt, a następnie (po raz drugi) przeszła całą drogę znacznie szybciej, omijając odcinki, które minęły dwa razy.

Na pierwszej Rosyjskiej Olimpiadzie Robotów odbyły się zawody, których celem było przejście swego rodzaju labiryntu: w możliwie najkrótszym czasie, przechodząc przez „otwarte drzwi” w ścianach, robot musiał przedostać się od startu do koniec. Robot mógł kontrolować swój ruch wzdłuż czarnych linii narysowanych na podłodze labiryntu.

Ten obraz krąży teraz w całym Internecie. Często towarzyszy temu następujący tekst: Izraelski wywiad wojskowy ma specjalną jednostkę, w której służą chłopcy i dziewczęta cierpiący na różne zaburzenia ze spektrum autyzmu. Osoby z autyzmem analizują najczęściej mapy i zdjęcia lotnicze, które pojawiają się na ekranach komputerów. Ze względu na specyfikę swojego myślenia zwracają uwagę na najdrobniejsze szczegóły, których uwzględnienie w przygotowaniu operacji wojskowych na ziemi pozwala zapobiec ewentualnym stratom personelu. W ten sposób autystyczni harcerze ratują życie żołnierzy”.

Czy próbowałeś tego labiryntu?

Dowiedzmy się więcej o tym problemie.

nawet na wzmiankę o tym labiryncie jest określone, że „ Osoba z autyzmem jest w stanie kilkakrotnie szybciej przetwarzać informacje wizualne i tekstowe niż osoba, która nie cierpi na zaburzenia ze spektrum autyzmu. Ta ich cecha okazała się nieodzowna w high-tech. W Specialisterne, duńskiej firmie konsultingowej ds. technologii, 75 procent jej pracowników to osoby z autyzmem i zespołem Aspergera, również ze spektrum autyzmu. Różnią się od zwykłych pracowników niesamowitą dbałością o szczegóły, nadludzką koncentracją i umiejętnością szybkiego przetwarzania ogromnych ilości informacji. Te umiejętności są szczególnie przydatne dla testerów oprogramowania. Jakość pracy osób z autyzmem zaangażowanych w tę pracę jest kilkakrotnie wyższa niż jakość pracy zwykłych ludzi. Osoby z autyzmem mogą sprawdzać 4000 stron dokumentacji technicznej 10 razy szybciej niż zwykli ludzie i nigdy nie przegapić ani jednego błędu."

Ale zostawmy autystyków na boku i dowiedzmy się w końcu, jak możesz przejść przez ten labirynt! Właśnie tak...

Zadanie jest nie do rozwiązania! Mamy 3 pokoje z nieparzystą liczbą drzwi (analogia do rysunków „bez podnoszenia ołówka”). Aby problem miał rozwiązanie konieczne jest, aby nie było więcej niż 2 punkty (w naszym przypadku pokoje) z nieparzystą liczbą wierszy (w naszym przypadku pasaże)

Jeśli zbudujemy wykres tego labiryntu, zobaczymy, że jest to ścieżka Eulera, ponieważ ma ona 3 wierzchołki o nieparzystej liczbie krawędzi (drzwi), a warunki testu mogą spełniać tylko dwa.

Problem siedmiu mostów Królewca lub Problem mostu królewieckiego(Niemiecki Królewiec Bruckenproblem) to stary problem matematyczny, w którym pytano, jak można przejść przez wszystkie siedem mostów Królewca bez dwukrotnego przechodzenia przez żaden z nich. Po raz pierwszy został rozwiązany w 1736 r. przez niemieckiego i rosyjskiego matematyka Leonharda Eulera.

Od dawna wśród mieszkańców Królewca krążyła taka zagadka: jak przejść przez wszystkie mosty (przez rzekę Pregoła) bez dwukrotnego przechodzenia przez żaden z nich. Wielu królewiecków próbowało rozwiązać ten problem zarówno teoretycznie, jak i praktycznie podczas spacerów. Nikt jednak nie mógł udowodnić ani obalić możliwości istnienia takiej trasy.

W 1736 r. problem siedmiu mostów zainteresował wybitnego matematyka, członka Petersburskiej Akademii Nauk Leonharda Eulera, o którym pisał w liście z 13 marca 1736 r. do włoskiego matematyka i inżyniera Marioniego. W liście tym Euler pisze, że udało mu się znaleźć regułę, dzięki której łatwo określić, czy możliwe jest przejście przez wszystkie mosty bez dwukrotnego przechodzenia przez którykolwiek z nich. Odpowiedź brzmiała „nie”.

Na uproszczonym schemacie części miasta (wykres) odpowiadają mostom z liniami (łukami wykresu), a części miasta odpowiadają punktom połączenia linii (wierzchołkom wykresu). W toku rozumowania Euler doszedł do następujących wniosków:

• Liczba nieparzystych wierzchołków (wierzchołków, do których prowadzi nieparzysta liczba krawędzi) musi być parzysta. Nie może istnieć wykres, który ma nieparzystą liczbę nieparzystych wierzchołków.


• Jeśli wszystkie wierzchołki wykresu są parzyste, możesz narysować wykres bez podnoszenia ołówka z kartki i możesz zacząć od dowolnego wierzchołka wykresu i zakończyć go na tym samym wierzchołku.


• Wykresu z więcej niż dwoma nieparzystymi wierzchołkami nie można narysować jednym pociągnięciem.

Teoria grafów stworzona przez Eulera znalazła bardzo szerokie zastosowanie w systemach transportowych i komunikacyjnych (np. do badania samych systemów, opracowywania optymalnych tras dostaw towarów czy danych o trasach w Internecie).

W 1905 r. wybudowano Most Cesarski, który został następnie zniszczony podczas bombardowań podczas II wojny światowej. Istnieje legenda, że ​​most ten został zbudowany na polecenie samego cesarza, który nie potrafił rozwiązać problemu mostów królewieckich i stał się ofiarą żartu, który z nim grały uczone umysły obecne na świeckich przyjęciach (jeśli dodamy ósmy most, wtedy problem staje się rozwiązywalny). Most Jubileuszowy został zbudowany na podporach Mostu Cesarskiego w 2005 roku. W tej chwili w Kaliningradzie jest siedem mostów, a graf zbudowany na bazie wysp i mostów Kaliningradu nadal nie ma ścieżki Eulera

Oto kolejne rozwiązanie oferowane przez xlazex

Spójrzmy na zdjęcie 1: otoczymy każdą oddzielną część kwadratami, wykluczymy „dodatkowe” punkty, tj. te punkty, których użycie zwiększyłoby możliwą liczbę ścieżek, a których wyłączenie nie wpłynie na liczbę drzwi mijanych przez linię i zamknięcie konturu. Na początek ścieżki weź na przykład punkt 2 .
Spójrzmy na obrazek 2: na nim nakreśliłem ten sam kontur, ale w taki sposób, aby połączenia punktu startowego z kolejnymi były bardziej widoczne. Obraz wyraźnie pokazuje, że części konturu zaznaczonej na niebiesko nie da się zamknąć raz, tj. nawet gdyby ta część konturu była jedyną, nie byłoby ścieżek, po których można by było skonstruować linię zamkniętą.
Konkluzja: problem nie ma rozwiązania w dwuwymiarowym układzie współrzędnych.

Ale jest rozwiązanie w 3D :-)

Dobra, żart, żart...