Weźmy pod uwagę potencjalnie przecinający się wielokąt, zdefiniowany przez listę wierzchołków w przestrzeni 2D. Na przykład
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
Istnieje kilka sposobów definiowania obszaru takiego wielokąta, ale najciekawszym jest zasada parzysto-nieparzysta. Biorąc dowolny punkt na płaszczyźnie, narysuj linię od punktu do nieskończoności (w dowolnym kierunku). Jeśli linia ta przecina wielokąt nieparzystą liczbę razy, punkt jest częścią obszaru wielokąta, jeśli przecina wielokąt parzystą liczbę razy, punkt nie jest częścią wielokąta. W powyższym przykładzie wielokąta przedstawiono zarówno jego kontur, jak i jego parzysty nieparzysty obszar:
Wielobok na ogół nie będzie ortogonalny. Wybrałem tylko taki prosty przykład, aby ułatwić policzenie obszaru.
Obszar tego przykładu to 17
(nie 24
lub 33
jak mogą dać inne definicje lub obszar).
Zauważ, że zgodnie z tą definicją obszar wielokąta jest niezależny od jego kolejności nawijania.
Wyzwanie
Biorąc pod uwagę listę wierzchołków o współrzędnych całkowitych definiujących wielokąt, określ jego obszar według reguły parzystej i nieparzystej.
Możesz napisać funkcję lub program, przyjmując dane wejściowe przez STDIN lub najbliższą alternatywę, argument wiersza poleceń lub argument funkcji i albo zwróć wynik, albo wydrukuj go do STDOUT lub najbliższej alternatywy.
Możesz pobierać dane wejściowe w dowolnym dogodnym formacie listy lub ciągu, o ile nie są one wstępnie przetwarzane.
Wynik powinien być albo liczbą zmiennoprzecinkową, z dokładnością do 6 cyfr znaczących (dziesiętnych), albo wynikiem racjonalnym, którego reprezentacja zmiennoprzecinkowa jest dokładna do 6 cyfr znaczących. (Jeśli uzyskasz racjonalne wyniki, prawdopodobnie będą one dokładne, ale nie mogę tego wymagać, ponieważ nie mam dokładnych wyników w celach informacyjnych).
Musisz być w stanie rozwiązać każdy z poniższych przypadków testowych w ciągu 10 sekund na rozsądnej maszynie stacjonarnej. (W tej regule jest pewna swoboda, więc dokonaj najlepszego osądu. Jeśli na moim laptopie zajmie to 20 sekund, dam ci wątpliwości, jeśli zajmie to chwilę, nie zrobię tego). Myślę, że ten limit powinno być bardzo hojne, ale powinno wykluczać podejścia, w których po prostu dyskrecjonujesz wielokąt na odpowiednio drobnej siatce i liczysz, lub używasz podejść probabilistycznych, takich jak Monte Carlo. Bądź dobrym sportowcem i nie próbuj optymalizować tych podejść, aby i tak dotrzymać terminu. ;)
Nie wolno używać żadnych istniejących funkcji związanych bezpośrednio z wielokątami.
To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach).
Założenia
- Wszystkie współrzędne są liczbami całkowitymi w zakresie
0 ≤ x ≤ 100
,0 ≤ y ≤ 100
. - Będą przynajmniej
3
i co najwyżej50
wierzchołki. - Nie będzie powtarzanych wierzchołków. Żaden wierzchołek nie będzie leżał na innej krawędzi. ( Jednak na liście mogą znajdować się punkty współliniowe.)
Przypadki testowe
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
17.0000
{{22, 87}, {6, 3}, {98, 77}, {20, 56}, {96, 52}, {79, 34}, {46, 78}, {52, 73}, {81, 85}, {90, 43}}
2788.39
{{90, 43}, {81, 85}, {52, 73}, {46, 78}, {79, 34}, {96, 52}, {20, 56}, {98, 77}, {6, 3}, {22, 87}}
2788.39
{{70, 33}, {53, 89}, {76, 35}, {14, 56}, {14, 47}, {59, 49}, {12, 32}, {22, 66}, {85, 2}, {2, 81},
{61, 39}, {1, 49}, {91, 62}, {67, 7}, {19, 55}, {47, 44}, {8, 24}, {46, 18}, {63, 64}, {23, 30}}
2037.98
{{42, 65}, {14, 59}, {97, 10}, {13, 1}, {2, 8}, {88, 80}, {24, 36}, {95, 94}, {18, 9}, {66, 64},
{91, 5}, {99, 25}, {6, 66}, {48, 55}, {83, 54}, {15, 65}, {10, 60}, {35, 86}, {44, 19}, {48, 43},
{47, 86}, {29, 5}, {15, 45}, {75, 41}, {9, 9}, {23, 100}, {22, 82}, {34, 21}, {7, 34}, {54, 83}}
3382.46
{{68, 35}, {43, 63}, {66, 98}, {60, 56}, {57, 44}, {90, 52}, {36, 26}, {23, 55}, {66, 1}, {25, 6},
{84, 65}, {38, 16}, {47, 31}, {44, 90}, {2, 30}, {87, 40}, {19, 51}, {75, 5}, {31, 94}, {85, 56},
{95, 81}, {79, 80}, {82, 45}, {95, 10}, {27, 15}, {18, 70}, {24, 6}, {12, 73}, {10, 31}, {4, 29},
{79, 93}, {45, 85}, {12, 10}, {89, 70}, {46, 5}, {56, 67}, {58, 59}, {92, 19}, {83, 49}, {22,77}}
3337.62
{{15, 22}, {71, 65}, {12, 35}, {30, 92}, {12, 92}, {97, 31}, {4, 32}, {39, 43}, {11, 40},
{20, 15}, {71, 100}, {84, 76}, {51, 98}, {35, 94}, {46, 54}, {89, 49}, {28, 35}, {65, 42},
{31, 41}, {48, 34}, {57, 46}, {14, 20}, {45, 28}, {82, 65}, {88, 78}, {55, 30}, {30, 27},
{26, 47}, {51, 93}, {9, 95}, {56, 82}, {86, 56}, {46, 28}, {62, 70}, {98, 10}, {3, 39},
{11, 34}, {17, 64}, {36, 42}, {52, 100}, {38, 11}, {83, 14}, {5, 17}, {72, 70}, {3, 97},
{8, 94}, {64, 60}, {47, 25}, {99, 26}, {99, 69}}
3514.46
źródło
upath
operatora. (W rzeczywistości jest to bardzo prosta konwersja 1: 1 między separatorami. Po}, {
prostu staje sięlineto
, przecinek między xiy jest usuwany, a nawiasy otwierające i zamykające są zastępowane statycznym nagłówkiem i stopką ...)upath
ilineto
brzmi, jakbyś faktycznie przetwarzał dane wejściowe. Tj. Nie bierzesz listy współrzędnych, ale rzeczywisty wielokąt.CrossingPolygon
.Odpowiedzi:
Mathematica,
247225222Najpierw dodaj punkty przecięcia do wielokąta, następnie odwróć niektóre krawędzie, a następnie jego pole można obliczyć jak zwykły wielokąt.
Przykład:
źródło
{1,2},{4,4},{4,2},{2,4},{2,1},{5,3}
? Powinieneś wyjść z 3.433333333333309. Patrzyłem na użycie podobnej logiki.103/30
, a wartość liczbowa to3.43333
.Python 2,
323319 bajtówPobiera listę wierzchołków przez STDIN jako liczby zespolone, w następującej formie
i zapisuje wynik w STDOUT.
Ten sam kod po zamianie łańcucha i niektórych odstępach:
Wyjaśnienie
Dla każdego punktu przecięcia dwóch boków wielokąta wejściowego (w tym wierzchołków), przeprowadź linię pionową przez ten punkt.
(W rzeczywistości, z powodu gry w golfa, program przechodzi kilka kolejnych linii; to nie ma znaczenia, o ile mijamy przynajmniej te linie.) Ciało wielokąta między dowolnymi dwiema kolejnymi liniami składa się z pionowych trapezoidów ( oraz trójkąty i segmenty linii, jako ich szczególne przypadki). Tak musi być, ponieważ jeśli którykolwiek z tych kształtów miałby dodatkowy wierzchołek między dwiema podstawami, między tymi dwoma liniami byłaby kolejna pionowa linia. Suma powierzchni wszystkich takich trapezoidów to powierzchnia wielokąta.
Oto jak odnajdujemy te trapezoidy: Dla każdej pary kolejnych pionowych linii znajdujemy segmenty każdej strony wielokąta, które (prawidłowo) leżą między tymi dwiema liniami (które mogą nie istnieć dla niektórych boków). Na powyższej ilustracji są to sześć czerwonych segmentów, biorąc pod uwagę dwie czerwone pionowe linie. Zauważ, że te segmenty nie przecinają się prawidłowo (tzn. Mogą się spotkać tylko w punktach końcowych, całkowicie się pokrywają lub wcale nie przecinają się, ponieważ, ponownie, jeśli prawidłowo się przecinają, pomiędzy nimi będzie inna linia pionowa;) dlatego warto rozmawiać o zamawianiu ich od góry do dołu, co robimy. Zgodnie z zasadą parzysto-nieparzystą, gdy przekroczymy pierwszy segment, jesteśmy wewnątrz wielokąta; kiedy przekroczymy drugi, jesteśmy poza; trzeci znowu; czwarte wyjście; i tak dalej...
Ogólnie jest to algorytm O ( n 3 log n ).
źródło
Haskell, 549
Nie wygląda na to, bym mógł zagrać w tę grę wystarczająco daleko, ale koncepcja była inna niż dwie pozostałe odpowiedzi, więc pomyślałem, że i tak podzielę się tym. Wykonuje operacje wymierne O (N ^ 2) w celu obliczenia obszaru.
Przykład:
Pomysł polega na ponownym okablowaniu wielokąta przy każdym skrzyżowaniu, w wyniku czego powstanie połączenie wielokątów bez przecinających się krawędzi. Następnie możemy obliczyć (podpisany) obszar każdego z wielokątów za pomocą wzoru sznurowadła Gaussa ( http://en.wikipedia.org/wiki/Shoelace_formula ). Zasada parzystej nieparzystości wymaga, aby po przekształceniu skrzyżowania pole nowego wielokąta było liczone ujemnie w stosunku do starego wielokąta.
Rozważmy na przykład wielokąt w pierwotnym pytaniu. Skrzyżowanie w lewym górnym rogu jest konwertowane na dwie ścieżki, które spotykają się tylko w jednym punkcie; obie ścieżki są zorientowane zgodnie z ruchem wskazówek zegara, więc obszary każdej z nich byłyby dodatnie, chyba że zadeklarujemy, że ścieżka wewnętrzna jest ważona o -1 w stosunku do ścieżki zewnętrznej. Jest to równoważne odwróceniu ścieżki alphaalpha.
Jako kolejny przykład rozważ wielokąt z komentarza MickyT:
Tutaj niektóre wielokąty są zorientowane zgodnie z ruchem wskazówek zegara, a niektóre przeciwnie do ruchu wskazówek zegara. Reguła „przerzucanie na krzyż” gwarantuje, że regiony zorientowane zgodnie z ruchem wskazówek zegara podniosą dodatkowy współczynnik -1, powodując, że wniosą one pozytywną wartość do tego obszaru.
Oto jak działa program:
źródło