Twoim celem jest ustalenie, czy dany punkt 2D X znajduje się w obszarze trójkąta o danych wierzchołkach A, B, C.
Napisz funkcję, która przyjmuje współrzędne punktu testowego X i trzech wierzchołków trójkąta (czyli w sumie 8 współrzędnych) i zwraca True, jeśli punkt znajduje się w tym trójkącie, i False, jeśli leży na zewnątrz.
Nie martw się o przypadki krawędzi. Jeśli punkt leży na granicy trójkąta (krawędzi lub wierzchołka) lub trójkąt jest w rzeczywistości segmentem linii, kod może zrobić wszystko, w tym awarię. Nie martw się także o stabilność numeryczną lub precyzję zmiennoprzecinkową.
Twój kod musi być nazwaną funkcją. Fragmenty kodu nie będą akceptowane.
Wygrywa niewiele postaci.
Wejście:
Osiem liczb rzeczywistych reprezentujących współrzędne. Liczby będą się mieścić w zakresie (-1,1)
.
Dokładny format wejściowy jest elastyczny. Możesz na przykład wziąć osiem liczb, listę ośmiu liczb, listę czterech punktów podanych przez krotkę, macierz 2 * 4, cztery liczby zespolone, dwie listy współrzędnych xi współrzędnych y, i tak dalej.
Dane wejściowe muszą być tylko liczbami w pewnym kontenerze, bez dodatkowych danych. Nie można użyć danych wejściowych do wykonania żadnego wstępnego przetwarzania, ani nie można wymagać żadnych ograniczeń na danych wejściowych, takich jak wymóg podawania punktów we współrzędnej rosnącej y. Twój wkład musi dopuszczać dowolne osiem współrzędnych (chociaż twój kod może zachowywać się arbitralnie we wspomnianych wcześniej przypadkach krawędzi).
Podaj swój format wejściowy.
Wynik:
Odpowiedni Boolean True
/ False
, odpowiedni numer 1
/ 0
lub analogi w Twoim języku.
Przypadki testowe
Dane wejściowe otrzymują listę [X,A,B,C]
czterech krotek, najpierw punkt testowy, a następnie trzy wierzchołki trójkąta. Pogrupowałem je w tych, których wyniki powinny być, True
i tych, które powinny False
.
True
instancje:
[(-0.31961, -0.12646), (0.38478, 0.37419), (-0.30613, -0.59754), (-0.85548, 0.6633)]
[(-0.87427, -0.00831), (0.78829, 0.60409), (-0.90904, -0.13856), (-0.80685, 0.48468)]
[(0.28997, -0.03668), (-0.28362, 0.42831), (0.39332, -0.07474), (-0.48694, -0.10497)]
[(-0.07783, 0.04415), (-0.34355, -0.07161), (0.59105, -0.93145), (0.29402, 0.90334)]
[(0.36107, 0.05389), (0.27103, 0.47754), (-0.00341, -0.79472), (0.82549, -0.29028)]
[(-0.01655, -0.20437), (-0.36194, -0.90281), (-0.26515, -0.4172), (0.36181, 0.51683)]
[(-0.12198, -0.45897), (-0.35128, -0.85405), (0.84566, 0.99364), (0.13767, 0.78618)]
[(-0.03847, -0.81531), (-0.18704, -0.33282), (-0.95717, -0.6337), (0.10976, -0.88374)]
[(0.07904, -0.06245), (0.95181, -0.84223), (-0.75583, -0.34406), (0.16785, 0.87519)]
[(-0.33485, 0.53875), (-0.25173, 0.51317), (-0.62441, -0.90698), (-0.47925, 0.74832)]
False
instancje:
[(-0.99103, 0.43842), (0.78128, -0.10985), (-0.84714, -0.20558), (-0.08925, -0.78608)]
[(0.15087, -0.56212), (-0.87374, -0.3787), (0.86403, 0.60374), (0.01392, 0.84362)]
[(0.1114, 0.66496), (-0.92633, 0.27408), (0.92439, 0.43692), (0.8298, -0.29647)]
[(0.87786, -0.8594), (-0.42283, -0.97999), (0.58659, -0.327), (-0.22656, 0.80896)]
[(0.43525, -0.8923), (0.86119, 0.78278), (-0.01348, 0.98093), (-0.56244, -0.75129)]
[(-0.73365, 0.28332), (0.63263, 0.17177), (-0.38398, -0.43497), (-0.31123, 0.73168)]
[(-0.57694, -0.87713), (-0.93622, 0.89397), (0.93117, 0.40775), (0.2323, -0.30718)]
[(0.91059, 0.75966), (0.60118, 0.73186), (0.32178, 0.88296), (-0.90087, -0.26367)]
[(0.3463, -0.89397), (0.99108, 0.13557), (0.50122, -0.8724), (0.43385, 0.00167)]
[(0.88121, 0.36469), (-0.29829, 0.21429), (0.31395, 0.2734), (0.43267, -0.78192)]
Odpowiedzi:
JavaScript / ECMAScript 6,
161159158/152JavaScript:
Wersja ECMAScript 6 (dzięki m.buettner, zapisuje 6 znaków)
Nazwij to tak (zwraca
true
lubfalse
):Wykorzystuje fantazyjną matematykę współrzędnych barycentrycznych opartą na kodzie z tej odpowiedzi . Wersja bez golfa dla przyjemności czytania:
źródło
(a*(l-n)+i*(g-e)+n*e-g*l)
zamiast(-g*l+a*(-n+l)+i*(g-e)+n*e)
?Python 2,7
1281271171101091039995949190Moja pierwsza próba golfa kodowego!
Kod
Przyjmuje jako dane wejściowe (x, y, t) gdzie (x, y) jest punktem, który sprawdzamy, a t jest trójkątem t = ((x1, y1), (x2, y2), (x3, y3)).
Wyjaśnienie
Obliczam wyznaczniki macierzy
Te wyznaczniki reprezentują podpisane odległości od boków trójkąta do punktu (x, y). Jeśli wszystkie mają ten sam znak, to punkt znajduje się po tej samej stronie każdej linii, a zatem jest zawarty w trójkącie.
W powyższym kodzie
a*y+c*b+d*x-d*a-c*y-b*x
jest wyznacznikiem jednej z tych macierzy.Korzystam z faktu, że
True+True+True==3
iFalse+False+False==0
aby ustalić, czy wszystkie te determinanty mają ten sam znak.Korzystam z ujemnych wskaźników listy Pythona, używając
t[-1]
zamiastt[(i+1)%3]
.Dzięki Peter za pomysł, aby użyć
s%3<1
zamiasts in(0,3)
sprawdzić, czy s wynosi 0 lub 3!Wersja Sagemath
Niezupełnie inne rozwiązanie, więc dołączam to do tej odpowiedzi, rozwiązanie sagemath zawierające 80 znaków:
gdzie
p=[x,y]
it=[[x1,y1],[x2,y2],[x3,y3]]
źródło
s in (0,3)
to skrócićs%3<1
?-1,0,1 ... t[i]+t[i+1]
odpowiada0,1,2 ... t[i-1]+t[i]
in -1,0,1
przed przeczytaniem tego. W rzeczywistości twój sposób jest bardziej czytelny, więc i tak go wykorzystam.sum
jeśli umieścisz0,1,2
w nawiasach, które opisują znak, zastępując spację. Powodem jest to, że Python pozwala na przekazywanie nieobrobionego zrozumienia funkcjom, ale przecinki w kruchej krotce1,2,3
mylą go, ponieważ próbuje je parsować jako osobne argumenty.Mathematica, 67 bajtów
Funkcja przyjmuje dwa argumenty, punkt
X
i listę punktów{A,B,C}
, które są odpowiednio nazywane#
i#2
. To znaczy, jeśli zadzwoniszwtedy dostaniesz
#
jakX
i#2
jak{A,B,C}
. (Zauważ, że w kodzie są zagnieżdżone dwie inne anonimowe funkcje -#
i#2
mają one inne znaczenie).Oto wyjaśnienie samej funkcji:
Zauważ, że ta funkcja będzie faktycznie działać dla każdego wypukłego n-gona, o ile jego wierzchołki są podane w kolejności zgodnej z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara.
źródło
Det
?CJam,
66635952463432313028 znakówPo przekształceniu ciągu Unicode oceniany jest następujący kod ( 33 bajty ):
Oczekuje
X [A B C]
jako danych wejściowych, gdzie każdy punkt ma formę[double double]
. Wyjście to 1 lub 0.Wypróbuj online.
Ogromne podziękowania dla użytkownika 2302 za zapisanie 6 znaków (13 bajtów nieskompresowanego kodu)!
Przypadki testowe
źródło
{
a}
i traktowane jako pojedyncza jednostka. Podobnie jak bloki kodu w C / java, tyle że bloki są obiektami pierwszej klasy i mogą być przypisywane do zmiennych (definiując w ten sposób funkcje).1m<@m*
przygotowuje 3 pary X i następny (i+1
th) wierzchołek trójkąta.@-@@-
przesuwa bieżący (i
th) wierzchołek do początku (i jest dublowany, jeśli tak nie było@-\@-
, ale to nie ma znaczenia).@@*@@*>
oblicza oś Z iloczynu krzyżowego, czyli wyznacznika, i zwraca,1
jeśli jest ujemna.:+3%!
zwraca, czy wszystkie są takie same, tzn. wszystkie 3 są ujemne lub nieujemne, co oznacza dodatnie, z wyjątkiem przypadków krawędzi. Myślę, że czytanie CJam jest trudniejsze niż gra w golfa.{[_1m<\]z\f{f{+~@-@@-}~@@*@@*>})-!}:T
. Użyj2m>
lubWm<
dla bezpieczeństwa Unicode.{2*2/\f{f{+~@-@@-}~@@*@@*>})-!}:T
C - 156 bajtów
Dane wejściowe to tablica 3 pływaków w X, 3 pływaków w Y i oddziel x i y dla punktu testowego. Bonus: obsługuje wszystkie skrzynki krawędziowe!
Zaadaptowano z PNPOLY.
źródło
i;j;c;f(float*X,float*Y,float x,float y){for(c=i=0,j=2;i<3;)c^=(Y[i]>y)-(Y[j]>y)&(x<(X[j]-X[i])*(y-Y[i])/(Y[j]-Y[i])+X[j=i++]);return c;}
137 - testowany w javascriptPyth 1.0.5 ,
575451Definiuje funkcję g, która przyjmuje dwa dane wejściowe: punkt testowy, a następnie listę wierzchołków trójkąta. Wyjścia
True
iFalse
. Uwaga: Niszczy dane wejściowe, w szczególności b, listę wierzchołków trójkąta.Wypróbuj tutaj . Ostatnie kilka znaków
gvwvw
wywołuje funkcję z przypadkiem testowym w następnych dwóch wierszach.Na podstawie tego algorytmu
Wyjaśnienie:
CJam - Wojna w Pyth trwa!
źródło
w
pobieranie danych STDIN?Z
z pustym zestawem które gromadzą sięZ|=
, a następnie sprawdzić jego długość, aby zobaczyć, czy tylko0
„s lub1
były widoczne? Strategia okazała się dłuższa w Pythonie, ale być może warto jest używać prymitywów Pythona.J
6445 (42 bez przydziału)Przypisanie nie jest konieczne, aby rzecz była funkcją, więc nie wiadomo, czy ją policzyć, czy nie. Korzystając z elastycznych danych wejściowych: Chciałbym mieć tablicę (1 + liczba wierzchołków) x (wymiarowość przestrzeni).
Mam nadzieję, że zdobędziesz tutaj kilka dodatkowych punktów ...: Ta rzecz działa dla każdego wymiaru simpleks, nie tylko trójkątów w płaszczyźnie, ale także trójstronnej piramidy w przestrzeni 3D i tak dalej. Działa również, gdy liczba wierzchołków simpleksu jest mniejsza niż (n + 1), a następnie oblicza, czy rzut punktu na simpleks jest w środku, czy nie.
Przekształca się we współrzędne barycentryczne , a następnie sprawdza wartości ujemne, wskazując, że punkt znajduje się na zewnątrz. Czy umysł J używa _ jako ujemnego
Uruchom na podanych przykładach:
źródło
N+1
wierzchołkami. Na przykład piramida 4 wierzchołków w przestrzeni 3D lub simpleks 5 wierzchołków w przestrzeni 3D. Liczba wierzchołków może być mniejsza niżN+1
, w którym to przypadku algorytm sprawdza, czy rzut ortogonalny na hiperpłaszczyznę, w której znajduje się simpleks, leży wewnątrz tego simpleksu, czy nie (np. 2-punktowy simpleks w 2-D zostanie wyświetlony na linii i sprawdzony czy ta projekcja leży między punktami końcowymi)HTML5 + JS, 13b + 146b / 141b / 114 znaków
HTML:
JS (146b):
lub ES6 (141b):
lub zaciemnione przez Unicode ES6 (114 znaków):
demo: http://jsfiddle.net/xH8mV/
Obfuscation w Unicode wykonane za pomocą: http://xem.github.io/obfuscatweet/
źródło
Python (65)
Wygląda na to, że ludzie są skończeni w przesyłaniu, więc opublikuję własne rozwiązanie mojego pytania.
X
jest liczbą zespoloną reprezentującą punkty testowe iL
jest listą trzech punktów, z których każdy jest liczbą zespoloną.Najpierw wyjaśnię mniej golfową wersję kodu;
Przesuwamy punkty
A,B,C,X
tak, aby byłyX
na początku, wykorzystując wbudowaną złożoną arytmetykę Pythona. Musimy sprawdzić, czy pochodzenie jest zawarte w wypukłym kadłubieA,B,C
. Jest to równoważne z początkiem zawsze leżącym po tej samej stronie (lewej lub prawej) odcinków linii AB, BC i AC.Segment
AB
ma początek po lewej, jeśli jeden podróżuje w kierunku przeciwnym do ruchu wskazówek zegara mniej niż 180 stopni, aby dostać się z A do B, a po prawej w przeciwnym razie. Jeśli weźmiemy pod uwagę kątya
,b
orazc
odpowiadające tym punktom, to znaczyb-a < 180 degrees
(wzięte kątów w zakresie od 0 do 360 stopni). Jako liczb zespolonychangle(B/A)=angle(B)/angle(A)
. Równieżangle(x) < 180 degrees
dokładnie dla punktu w górnej pół-płaszczyźnie, przez który sprawdzamyimag(x)>0
.Tak więc, czy pochodzenie leży po lewej stronie AB jest wyrażone jako
(A/B).imag>0
. Sprawdzenie, czy wszystkie są równe dla każdej pary cyklicznej,A,B,C
informuje nas, czy trójkątABC
zawiera pochodzenie.Wróćmy teraz do w pełni golfowego kodu
Generujemy każdą cykliczną parę
(A-X,B-X,C-X)=(L[0]-X,L[1]-X,L[2]-X)
, wykorzystując owijanie się ujemnych indeksów list Pythona (L[-1]
=L[2]
). Aby sprawdzić, czy Bools to wszystkieTrue
(1
) lub wszystkieFalse
(0
), dodajemy je i sprawdzamy podzielność przez 3, podobnie jak wiele rozwiązań.źródło
Fortran -
232218195174Cholernie okropne. Ta funkcja jest przerażająca z powodu wymogu, że dane są do niej przekazywane i nie możemy jej wstępnie przetwarzać.
Zmniejszenie o 14 znaków jest spowodowane tym, że zapomniałem zagrać w golfa nazwę funkcji z moich testów. Dalszy spadek wynika z niejawnego pisania i zapominania o zmianie nazwy funkcji. Następne 20 znaków odpadło z powodu odczytania punktów jako pojedynczej tablicy. Pełny program to
źródło
logical function T(x);real x(8);p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3);s=x(6)-x(4);u=x(7)-x(3);v=x(8)-x(4);o=r*v-u*s;T=ALL([p*(s-v)+q*(u-r)+o,p*v-q*u,q*r-p*s]>=o);end
Próbowałem skrócić to dalej, używając operacji list, ale niestety nie wyszło to zbyt dobrze.logical function T(x);real x(8);p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3);s=x(6)-x(4);u=x(7)-x(3);v=x(8)-x(4);a=r*v-u*s;b=p*v-q*u;d=q*r-p*s;T=ALL([a-b-d,b,d]>=a);end
mam nadzieję, że nie popełniłem żadnych błędów w transformacjach! Choć wygląda na to, że oryginalny kod nie przechodzi wszystkich przypadków testowych.True
przykładem OP dajeFalse
gdybym zamienićB
iC
„s wartości, dającTrue
do orientacji oryginału.a < 0
, co skutecznie odwraca warunek, który musisz przetestować. Niestety nie da się tego naprawić, pakując wszystko wabs
, ponieważ wówczas domniemany warunekb
id
posiadanie tego samego znaku, gdya
się gubi. Można to naprawić za pomocą czegoś podobnego (ponownie, używając notacji i predefiniowanych zmiennych z mojego ostatniego komentarza)e=a-b-d;T=ALL([a*a-b*b,a*a-d*d,a*a-e*e,a*b,a*d,a*e]>=0)
- które prawdopodobnie można bardziej zagrać w golfa.MATLAB: 9!
Nie za dużo o mnie pisać
Można nazwać tak:
Dane wyjściowe są przypisywane do zmiennej o nazwie
ans
Gdybym musiał napisać funkcję, może być coś takiego, prawdopodobnie można ją zoptymalizować:
źródło
f=@(a,b,c,d)inpolygon(a,b,c,d)
C # 218 (149?)
Prawdopodobnie nie jest tak wydajny pod względem postaci jak metoda matematyczna, ale jest to fajne wykorzystanie bibliotek. Nawiasem mówiąc, również raczej powolny.
Wykorzystując także „Nie martw się także o stabilność numeryczną lub precyzję zmiennoprzecinkową”. - niestety
GraphicsPath
używaint
wewnętrznie s, więc wartość z zakresu -1 <f <1 może mieć tylko trzy możliwe wartości. Ponieważ liczby zmiennoprzecinkowe mają tylko 7 cyfr dokładności, pomnożę je tylko przez 1e7, aby zamienić je na liczby całkowite. Hm, chyba tak naprawdę nie traci precyzji. Można go także wykorzystać w inny sposób: prawdopodobnie mogłem skorzystać z ignorowania precyzji i po prostu podać „złą” odpowiedź.Jeśli pozwolę sobie zignorować koszty związane z importowaniem bibliotek, 149 (przynajmniej,
System.Linq
iSystem.Drawing
są one dość standardowe w większości projektów WinForm, aleSystem.Drawing.Drawing2D
mogą być nieco rozciągnięte):Program testowy (tak, jest brzydki):
źródło
Haskell -
233127Używanie produktów krzyżowych, jak opisano tutaj :
Poprzednie rozwiązanie wdrożone przy użyciu współrzędnych barycentrycznych i wzorów opisanych w tej odpowiedzi Stack Exchange :
Obie funkcje
g
ih
biorą cztery pary, z których pierwsza to punkt, który ma zostać przetestowany pod kątem włączenia, a reszta to współrzędne wierzchołków trójkąta.Aby przetestować z przykładowym wejściem:
Niegolfowane rozwiązania:
źródło
JavaScript (ES6) 120
Bezpośrednio skopiowane z mojej odpowiedzi na to drugie pytanie
Testuj w konsoli FireFox / FireBug
Wyjście wszystkich 1s
Wyjście wszystkich zer
źródło
SmileBASIC,
111100 znakówRysuje trójkąt i sprawdza kolor piksela w punkcie. Trójkąt jest przeskalowany w górę o 99999x i przesunięty tak, że punkt do sprawdzenia będzie wynosił (0,0) przed narysowaniem, aby zminimalizować utratę precyzji.
źródło
Montaż procesora Intel 8087 FPU,
222220 bajtówDo obliczeń używa tylko sprzętu 8087 FPU. Oto wersja niezmontowana (w tym przypadku również nie golfowa) jako MAKRO (oszczędza ci 220 bajtów kodów):
Wyjaśnienie
Używa wyznacznika do obliczenia pola trójkąta ABC, a następnie trójkąta utworzonego z punktem X i dwoma innymi punktami trójkąta ABC. Jeśli obszar trójkąta ABC jest równy sumie obszarów trójkątów XBC + AXC + ABX, wówczas punkt znajduje się w trójkącie. Wynik jest zwracany jako ZF.
Co jest w tym fajnego
Wszystkie operacje matematyczne i zmiennoprzecinkowe są wykonywane sprzętowo z 80-bitową rozszerzoną precyzją. Ostateczne porównanie zmiennoprzecinkowe jest również wykonywane sprzętowo, więc będzie bardzo dokładne.
Wykorzystuje to jednocześnie wszystkie osiem rejestrów stosu 8087.
Co nie jest w tym tak fajnego
Ponieważ punkty trójkąta muszą być ponownie podłączone do formuł kilka razy podczas obliczeń, wymaga to, aby każda zmienna w pamięci była ładowana do rejestrów stosu FPU pojedynczo w odpowiedniej kolejności. Chociaż można to dość łatwo modelować jako funkcję MAKRO, oznacza to, że kod jest rozszerzany za każdym razem podczas składania, tworząc zbędny kod. 41 bajtów zostało zapisanych przez przeniesienie niektórych tych samych powtarzających się segmentów kodu do PROC. Jednak sprawia, że kod jest mniej czytelny, więc powyższa lista jest bez niego (dlatego jest oznaczona jako „nie golfowa”).
Testy
Oto program testowy używający IBM DOS pokazujący dane wyjściowe:
Wydajność
źródło
C 414 (było 465)
Grał w golfa
Dodano oryginalną deklarację funkcji w celu wyjaśnienia
Przepisany jako funkcja o nazwie: wejście przez stdin po jednym wierszu lub wszystkie w jednym wierszu oddzielone spacjami.
źródło
double
na nowo jakoD
ale nadal używaćdouble
w kodzie.Java, 149 znaków
Okropne, biorąc pod uwagę, że muszę napisać „Matematyka”. każdego razu. To jest rzeczywisty program:
gdzie a jest x punktu a, b jest x punktu b, c dla x z c, d jest y z a, e jest y z b, f jest y z c, a x i y są x i o co chodzi. Wartość logiczna k określa, czy jest to prawda, czy nie.
źródło
100*
?JavaScript 125/198
Jeśli punkty są podane w 8 argumentach:
Jeśli punkty są podane w układzie dwuwymiarowym:
Ten kod nie używa żadnej z tych fantazyjnych matematyki wektorowej. Zamiast tego używa tylko prostej sztuczki algebry, aby ustalić, czy punkt znajduje się w trójkącie, czy nie. Formuła:
który mówi, że punkt jest po której stronie linii , pochodzi z przestawienia definicji nachylenia:
Jeśli przetestujemy wszystkie 3 boki, wszystkie 3 powinny dać pewne liczby z tym samym znakiem tylko wtedy, gdy punkt znajduje się wewnątrz trójkąta, ponieważ testujemy go wokół trójkąta. Jeśli punkt znajduje się na boku, jeden z testów powinien zwrócić 0.
Kod testowy jsFiddle: http://jsfiddle.net/DerekL/zEzZU/
97 znaków (nie licząc spacji ani tabulatorów) liczy się, jeśli zostanie przekonwertowany na CoffeeScript:
115 znaków w przypadku konwersji do ES6:
źródło
d=(x,y,...)=>{...}
. W twoim przypadku możesz zaoszczędzić jeszcze więcej, używając CoffeeScript, który nie potrzebujereturn
: pastebin.com/RVFk1D5k ... a w każdym razie możesz zapisać jeden bajt, używając<1
zamiast==0
.R 23
Zainspirowany MATLAB ,
nazywany jak
SDMTools::pnt.in.poly(point,triangle)
gdziepoint
jest wektorem długości-2 itriangle
jest macierzą 3x2 wierzchołków. SDMTools jest dostępny w CRAN.źródło
Mathematica, 38 znaków
Przykład:
(* Prawdziwe *)
źródło
C (gcc) , 108 bajtów
Wypróbuj online!
Pobiera trzy produkty krzyżowe i zwraca,
1
jeśli znakk̂
komponentu się nie zmienia.źródło