Sprawdź, czy punkt leży w trójkącie

40

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/ 0lub 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ć, Truei 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)]
xnor
źródło
Jaka jest twoja definicja postaci? Ascii? Kodowalny w 7 bitach? W bajcie? Jakieś Unicode?
isaacg
Co sugerujesz? Istnieją już rozwiązania wykorzystujące skompresowany kod.
xnor
Zazwyczaj uważam, że bajty są używane dla znaków innych niż ascii, ponieważ w przeciwnym razie przewaga Utf-32 jest nie do pokonania.
isaacg
Nie mogę teraz wrócić; dowolny znak Unicode jest znakiem. Kompresuj, jeśli chcesz.
xnor

Odpowiedzi:

19

JavaScript / ECMAScript 6, 161 159 158/152

JavaScript:

function $(t,r,i,a,n,g,l,e){b=(-g*l+a*(-n+l)+i*(g-e)+n*e)/2;c=b<0?-1:1;d=(a*l-i*e+(e-a)*t+(i-l)*r)*c;f=(i*g-a*n+(a-g)*t+(n-i)*r)*c;return d>0&&f>0&&d+f<2*b*c}

Wersja ECMAScript 6 (dzięki m.buettner, zapisuje 6 znaków)

$=(t,r,i,a,n,g,l,e)=>{b=(-g*l+a*(-n+l)+i*(g-e)+n*e)/2;c=b<0?-1:1;d=(a*l-i*e+(e-a)*t+(i-l)*r)*c;f=(i*g-a*n+(a-g)*t+(n-i)*r)*c;return d>0&&f>0&&d+f<2*b*c}

Nazwij to tak (zwraca truelub false):

$(pointX, pointY, v1X, v1Y, v2X, v2Y, v3X, v3Y);

Wykorzystuje fantazyjną matematykę współrzędnych barycentrycznych opartą na kodzie z tej odpowiedzi . Wersja bez golfa dla przyjemności czytania:

function $ (pointX, pointY, v1X, v1Y, v2X, v2Y, v3X, v3Y) {
  var A =  (-v2Y * v3X + v1Y * (-v2X + v3X) + v1X * (v2Y - v3Y) + v2X * v3Y) / 2;
  var sign = A < 0 ? -1 : 1;
  var s = (v1Y * v3X - v1X * v3Y + (v3Y - v1Y) * pointX + (v1X - v3X) * pointY) * sign;
  var t = (v1X * v2Y - v1Y * v2X + (v1Y - v2Y) * pointX + (v2X - v1X) * pointY) * sign;
  return s > 0 && t > 0 && s + t < 2 * A * sign;
}
Abraham
źródło
12
+1, jeśli tylko dla nazw parametrów!
Matt
Dlaczego musisz złamać mój liczący znaki UserScript?
kitcar2000
@ kitcar2000 co masz na myśli?
Abraham
Reguły mówią, że znaki są liczone, a nie bajty. Możesz więc użyć tego: xem.github.io/obfuscatweet, aby zmieścić w 122
znakach
1
Czy się mylę, czy mógłbyś użyć (a*(l-n)+i*(g-e)+n*e-g*l)zamiast (-g*l+a*(-n+l)+i*(g-e)+n*e)?
Zacharý
19

Python 2,7 128 127 117 110 109 103 99 95 94 91 90

Moja pierwsza próba golfa kodowego!

Kod

f=lambda x,y,t:sum(a*y+c*b+d*x<d*a+c*y+b*x for i in(0,1,2)for a,b,c,d in[t[i-1]+t[i]])%3<1

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

| 1 x1 y1 |      | 1 x2 y2 |      | 1 x3 y3 |
| 1 x2 y2 | ,    | 1 x3 y3 | ,    | 1 x1 y1 | .
| 1 x  y  |      | 1 x  y  |      | 1 x  y  |

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*xjest wyznacznikiem jednej z tych macierzy.

Korzystam z faktu, że True+True+True==3i False+False+False==0aby ustalić, czy wszystkie te determinanty mają ten sam znak.

Korzystam z ujemnych wskaźników listy Pythona, używając t[-1]zamiast t[(i+1)%3].

Dzięki Peter za pomysł, aby użyć s%3<1zamiast s 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:

f=lambda p,t,o=[1]:sum([det(Matrix([o+t[i-1],o+t[i],o+p]))<0for i in 0,1,2])%3<1

gdzie p=[x,y]it=[[x1,y1],[x2,y2],[x3,y3]]

Alex L.
źródło
1
Można s in (0,3)to skrócić s%3<1?
Peter Taylor
1
Wykorzystanie ujemnych indeksów można zmodyfikować, aby zaoszczędzić jeszcze jedno: -1,0,1 ... t[i]+t[i+1]odpowiada0,1,2 ... t[i-1]+t[i]
Peter Taylor
@PeterTaylor Absolutnie racja! Szkoda, że ​​usunąłem to miejsce in -1,0,1przed przeczytaniem tego. W rzeczywistości twój sposób jest bardziej czytelny, więc i tak go wykorzystam.
Alex L
1
Witamy w Code Golf! Możesz pozbyć się nawiasów kwadratowych do zrozumienia listy w środku, sumjeśli umieścisz 0,1,2w nawiasach, które opisują znak, zastępując spację. Powodem jest to, że Python pozwala na przekazywanie nieobrobionego zrozumienia funkcjom, ale przecinki w kruchej krotce 1,2,3mylą go, ponieważ próbuje je parsować jako osobne argumenty.
xnor
16

Mathematica, 67 bajtów

f=Equal@@({#2,-#}&@@(#-#2).(x-#)>0&@@@Partition[x=#;#2,2,1,{1,1}])&

Funkcja przyjmuje dwa argumenty, punkt Xi listę punktów {A,B,C}, które są odpowiednio nazywane #i #2. To znaczy, jeśli zadzwonisz

f[X,{A,B,C}]

wtedy dostaniesz #jak Xi #2jak {A,B,C}. (Zauważ, że w kodzie są zagnieżdżone dwie inne anonimowe funkcje - #i #2mają one inne znaczenie).

Oto wyjaśnienie samej funkcji:

                                              x=#;#2            & (* Save X into a variable x, but evaluate to {A,B,C}. *)
                                    Partition[x=#;#2,2,1,{1,1}] & (* Get a cyclic list of pairs {{A,B},{B,C},{C,B}}. *)
       (                        &@@@Partition[x=#;#2,2,1,{1,1}])& (* Define an anonymous function and apply it to each 
                                                                     of the above pairs. The two elements are referred 
                                                                     to as # and #2. *)
       (          (#-#2)        &@@@Partition[x=#;#2,2,1,{1,1}])& (* Subtract the two points. For a pair of vertices 
                                                                     this yields a vector corresponding to the edge 
                                                                     between them. *)
        {#2,-#}&                                                  (* An anonymous function that takes two values, 
                                                                     reverses them, inverts the sign of one of them 
                                                                     and puts them into a list. *)
       ({#2,-#}&@@(#-#2)        &@@@Partition[x=#;#2,2,1,{1,1}])& (* Applied to the edge, this yields its normal. *)
       ({#2,-#}&@@(#-#2).(x-#)  &@@@Partition[x=#;#2,2,1,{1,1}])& (* Take the scalar product of that normal with a
                                                                     vector from a vertex to x. This is projection of 
                                                                     this vector onto that normal and hence the SIGNED
                                                                     distance of x from the edge. *)
       ({#2,-#}&@@(#-#2).(x-#)>0&@@@Partition[x=#;#2,2,1,{1,1}])& (* Check the sign of that distance, the exact mapping 
                                                                     between (left, right) and (True, False) is 
                                                                     irrelevant, as long as it's consistent. *)
Equal@@({#2,-#}&@@(#-#2).(x-#)>0&@@@Partition[x=#;#2,2,1,{1,1}])& (* Check if all signs are equal - that is, if point X 
                                                                     lies on the same side of all edges. This is 
                                                                     equivalent to check that the point is inside the 
                                                                     triangle. *)

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.

Martin Ender
źródło
Czy nie byłoby skuteczniej sprawdzić, czy iloczyn odległości jest dodatni, niż gdyby wszystkie znaki były równe? Nie mam matematyki, ale wydaje się, że powinno być łatwiej.
isaacg
@isaacg Istnieją trzy warunki, więc jeśli wszystkie są negatywne, ich produkt jest negatywny, a jeśli wszystkie są pozytywne, ich produkt jest pozytywny. Twoje podejście działa tylko wtedy, gdy znaki dwóch liczb mają być równe.
Martin Ender
Dlaczego nie użyć Det?
alephalpha
@alephalpha Cóż, głównie dlatego, że o tym nie myślałem. : P ... Zajmę się tym
Martin Ender
@alephalpha Hm nie, nie mogę teraz znaleźć sposobu na zbudowanie trzech wymaganych macierzy w mniejszej liczbie znaków.
Martin Ender
7

CJam, 66 63 59 52 46 34 32 31 30 28 znaków

"Ă䒟损崙㩴ァ椟饃꿾藭鑭蘁"2G#b131b:c~

Po przekształceniu ciągu Unicode oceniany jest następujący kod ( 33 bajty ):

{2*2/\f{f{+~@-@@-}~@@*@@*>})-!}:T

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

$ cat triangle.cjam
"Ă䒟损崙㩴ァ椟饃꿾藭鑭蘁"2G#b131b:c~

[
  [-0.31961 -0.12646] [ [0.38478 0.37419]   [-0.30613 -0.59754] [-0.85548 0.6633]   ] T
  [-0.87427 -0.00831] [ [0.78829 0.60409]   [-0.90904 -0.13856] [-0.80685 0.48468]  ] T
  [0.28997 -0.03668]  [ [-0.28362 0.42831]  [0.39332 -0.07474]  [-0.48694 -0.10497] ] T
  [-0.07783 0.04415]  [ [-0.34355 -0.07161] [0.59105 -0.93145]  [0.29402 0.90334]   ] T
  [0.36107 0.05389]   [ [0.27103 0.47754]   [-0.00341 -0.79472] [0.82549 -0.29028]  ] T
  [-0.01655 -0.20437] [ [-0.36194 -0.90281] [-0.26515 -0.4172]  [0.36181 0.51683]   ] T
  [-0.12198 -0.45897] [ [-0.35128 -0.85405] [0.84566 0.99364]   [0.13767 0.78618]   ] T
  [-0.03847 -0.81531] [ [-0.18704 -0.33282] [-0.95717 -0.6337]  [0.10976 -0.88374]  ] T
  [0.07904 -0.06245]  [ [0.95181 -0.84223]  [-0.75583 -0.34406] [0.16785 0.87519]   ] T
  [-0.33485 0.53875]  [ [-0.25173 0.51317]  [-0.62441 -0.90698] [-0.47925 0.74832]  ] T
  [-0.99103 0.43842]  [ [0.78128 -0.10985]  [-0.84714 -0.20558] [-0.08925 -0.78608] ] T
  [0.15087 -0.56212]  [ [-0.87374 -0.3787]  [0.86403 0.60374]   [0.01392 0.84362]   ] T
  [0.1114 0.66496]    [ [-0.92633 0.27408]  [0.92439 0.43692]   [0.8298 -0.29647]   ] T
  [0.87786 -0.8594]   [ [-0.42283 -0.97999] [0.58659 -0.327]    [-0.22656 0.80896]  ] T
  [0.43525 -0.8923]   [ [0.86119 0.78278]   [-0.01348 0.98093]  [-0.56244 -0.75129] ] T
  [-0.73365 0.28332]  [ [0.63263 0.17177]   [-0.38398 -0.43497] [-0.31123 0.73168]  ] T
  [-0.57694 -0.87713] [ [-0.93622 0.89397]  [0.93117 0.40775]   [0.2323 -0.30718]   ] T
  [0.91059 0.75966]   [ [0.60118 0.73186]   [0.32178 0.88296]   [-0.90087 -0.26367] ] T
  [0.3463 -0.89397]   [ [0.99108 0.13557]   [0.50122 -0.8724]   [0.43385 0.00167]   ] T
  [0.88121 0.36469]   [ [-0.29829 0.21429]  [0.31395 0.2734]    [0.43267 -0.78192]  ] T
]p;

$ cjam triangle.cjam
[1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
Dennis
źródło
Czy to nazwana funkcja?
Martin Ender
@ m.buettner: Sortuj. Oficjalnym wiki mówi następujące: Block - odcinek programu ograniczoną przez {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).
Dennis
1
@xnor 1m<@m*przygotowuje 3 pary X i następny ( i+1th) wierzchołek trójkąta. @-@@-przesuwa bieżący ( ith) 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, 1jeś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.
jimmy23013
1
37 bajtów: {[_1m<\]z\f{f{+~@-@@-}~@@*@@*>})-!}:T. Użyj 2m>lub Wm<dla bezpieczeństwa Unicode.
jimmy23013
1
33 bajty:{2*2/\f{f{+~@-@@-}~@@*@@*>})-!}:T
jimmy23013
5

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!

int f(float*X,float*Y,float x,float y){int i,j,c=0;for(i=0,j=2;i<3;j=i++)if(((Y[i]>y)!=(Y[j]>y))&&(x<(X[j]-X[i])*(y-Y[i])/(Y[j]-Y[i])+X[i]))c=!c;return c;}

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 javascript
bebe
@bebe - To powoduje błąd składniowy.
Derek 朕 會 功夫
To nie powoduje błędu składniowego.
bebe,
4

Pyth 1.0.5 , 57 54 51

DgYb=Z0J'bWbK;bDiHNR*-'H'K-@N1@K1~Z>iYJiJY=JK)R!%Z3

Definiuje funkcję g, która przyjmuje dwa dane wejściowe: punkt testowy, a następnie listę wierzchołków trójkąta. Wyjścia Truei False. Uwaga: Niszczy dane wejściowe, w szczególności b, listę wierzchołków trójkąta.

Wypróbuj tutaj . Ostatnie kilka znaków gvwvwwywołuje funkcję z przypadkiem testowym w następnych dwóch wierszach.

Na podstawie tego algorytmu

Wyjaśnienie:

DgYb                  Define g(Y,b):
=Z0                     Z=0
J'b                     J=b[0]              (No = is needed because j is special).
Wb                      While len(b)>0:     (While b:)
K;b                       K=b.pop()
DiHN                      Define i(H,N):    
R*-'H'K-@N1@K1              Return half of the linked equation.
~ZiYJiJY                  Z+=i(Y,J)>i(J,Y)
=JK                       J=K
)                       Wend
R!%Z3                   return not Z%3==0   (True iff Z == 0 or 3)

CJam - Wojna w Pyth trwa!

isaacg
źródło
Powinna to być funkcja nazwana. Czy wpobieranie danych STDIN?
xnor
@xnor Ups, brakowało mi tego fragmentu opisu. Będzie edytować.
isaacg
@xnor Czy funkcje, które drukują odpowiedź są dozwolone, czy muszą zwracać odpowiedź? Obecnie drukuje odpowiedź, ale mógłbym poprosić o zwrot jeszcze jednej postaci.
isaacg
Zwróć odpowiedź.
xnor
Czy może zapisać znaki zastępując licznik Zz pustym zestawem które gromadzą się Z|=, a następnie sprawdzić jego długość, aby zobaczyć, czy tylko 0„s lub 1były widoczne? Strategia okazała się dłuższa w Pythonie, ale być może warto jest używać prymitywów Pythona.
xnor
4

J 64 45 (42 bez przydziału)

c=:*./@(>:&0)@({.(,(1-+/))@%.|:@}.)@(}:-"1{:)

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

NB. example in triangle
D =: 4 2 $ 1 1 0 0 3 0 0 2 NB. 4 rows , x first, then the vertices of the triangle

NB. subtract last vertex coordinates from the rest and drop reference node
n=: (}:-"1{:)

NB. preprocessed to barycentric coordinates
bar=: {. (, 1 - +/)@%. |:@}.

NB. all positive
ap =: *./@(>:&0)

insided =: ap@bar@n

inside D
1

Uruchom na podanych przykładach:

   true =: 0 : 0
[(-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 =: 0 : 0
[(-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)]
)
   NB. replace - by _ to avoid problems
   NB. cut up per row, drop the [ ] and convert to numbers
   $dat_t =: ((4 2 $ ".)@}:@}.;._2) (true='-')} true ,: '_'
10 4 2
   $dat_f =: ((4 2 $ ".)@}:@}.;._2) (false='-')}false,: '_'
10 4 2
   NB. this results in arrays with shape 10 4 2

   NB. for each 4 x 2 array (rank 2), do c for all true instances
   c=:*./@(>:&0)@({.(,(1-+/))@%.|:@}.)@(}:-"1{:)
   c"2 dat_t
1 1 1 1 1 1 1 1 1 1
   NB. the same for the false ones, demonstrating anonymous usage
   NB. still a function though (or verb in J parlance)
   *./@(>:&0)@({.(,(1-+/))@%.|:@}.)@(}:-"1{:)"2 dat_f
0 0 0 0 0 0 0 0 0 0
jpjacobs
źródło
Poprosiłem o nazwaną funkcję, więc liczą się znaki przypisania. Oto kilka punktów do uogólnienia na wielokąty! ······
xnor
Cóż, właściwie nie do końca uogólniam na wielokąty, ale na N-wymiarowe simpleksy z maksymalnymi N+1wierzchoł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)
jpjacobs
4

HTML5 + JS, 13b + 146b / 141b / 114 znaków

HTML:

<canvas id=C>

JS (146b):

// @params: t1x, t1y, t2x, t2y, t3x, t3y, pointx, pointy
function T(a,b,c,d,e,f,g,h){with(C.getContext("2d"))return beginPath(),moveTo(a,b),lineTo(c,d),lineTo(e,f),fill(),!!getImageData(g,h,1,1).data[3]}

lub ES6 (141b):

T=(a,b,c,d,e,f,g,h)=>{with(C.getContext("2d"))return beginPath(),moveTo(a,b),lineTo(c,d),lineTo(e,f),fill(),!!getImageData(g,h,1,1).data[3]}

lub zaciemnione przez Unicode ES6 (114 znaków):

eval(unescape(escape('𥀽𚁡𛁢𛁣𛁤𛁥𛁦𛁧𛁨𚐽🡻𭱩𭁨𚁃𛡧𩑴𠱯𫡴𩑸𭀨𘠲𩀢𚐩𬡥𭁵𬡮𘁢𩑧𪑮𤁡𭁨𚀩𛁭𫱶𩑔𫰨𨐬𨠩𛁬𪑮𩑔𫰨𨰬𩀩𛁬𪑮𩑔𫰨𩐬𩠩𛁦𪑬𫀨𚐬𘐡𩱥𭁉𫑡𩱥𡁡𭁡𚁧𛁨𛀱𛀱𚐮𩁡𭁡𦰳𧑽').replace(/uD./g,'')))

demo: http://jsfiddle.net/xH8mV/

Obfuscation w Unicode wykonane za pomocą: http://xem.github.io/obfuscatweet/

Xem
źródło
Wydaje się, że nie daje poprawnego wyniku, gdy punkt jest blisko boku: jsfiddle.net/L2B2A Wierzę, że dzieje się tak, ponieważ wszystkie dane wejściowe znajdują się między (-1,1), a twój kod testuje tylko 4 piksele wokół pochodzenie.
Derek 朕 會 功夫
to prawda, aby pasować do przykładów, powinienem zmienić pochodzenie i skalę mojego płótna, aby obsługiwać wewnątrz trójkąty [-1,1]. Ale dlaczego te trójkąty są tak małe?
xem.
problem mówi, że wszystkie xy są między -1 a 1. Naprawdę nie wiem dlaczego, ale wierzę, że możesz po prostu pomnożyć każde wejście przez 1e7 (aby zachować precyzję), aby uzyskać poprawny wynik: D
Derek 朕 會 功夫
Rozwiązanie graficzne, bardzo sprytne!
xnor
3

Python (65)

Wygląda na to, że ludzie są skończeni w przesyłaniu, więc opublikuję własne rozwiązanie mojego pytania.

f=lambda X,L:sum(((L[i-1]-X)/(L[i]-X)).imag>0for i in(0,1,2))%3<1

Xjest liczbą zespoloną reprezentującą punkty testowe i Ljest listą trzech punktów, z których każdy jest liczbą zespoloną.

Najpierw wyjaśnię mniej golfową wersję kodu;

def f(X,A,B,C):A-=X;B-=X;C-=X;return((A/B).imag>0)==((B/C).imag>0)==((C/A).imag>0)

Przesuwamy punkty A,B,C,Xtak, aby były Xna początku, wykorzystując wbudowaną złożoną arytmetykę Pythona. Musimy sprawdzić, czy pochodzenie jest zawarte w wypukłym kadłubie A,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 ABma 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ąty a, boraz codpowiadające tym punktom, to znaczy b-a < 180 degrees(wzięte kątów w zakresie od 0 do 360 stopni). Jako liczb zespolonych angle(B/A)=angle(B)/angle(A). Również angle(x) < 180 degreesdokładnie dla punktu w górnej pół-płaszczyźnie, przez który sprawdzamy imag(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,Cinformuje nas, czy trójkąt ABCzawiera pochodzenie.

Wróćmy teraz do w pełni golfowego kodu

f=lambda X,L:sum(((L[i-1]-X)/(L[i]-X)).imag>0for i in(0,1,2))%3<1

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 wszystkie True( 1) lub wszystkie False( 0), dodajemy je i sprawdzamy podzielność przez 3, podobnie jak wiele rozwiązań.

xnor
źródło
2

Fortran - 232 218 195 174

Cholernie okropne. Ta funkcja jest przerażająca z powodu wymogu, że dane są do niej przekazywane i nie możemy jej wstępnie przetwarzać.

logical function L(x);real::x(8);p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3);s=x(6)-x(4);t=x(7)-x(3);u=x(8)-x(4);L=ALL([p*(s-u)+q*(t-r)+r*u-t*s,p*u-q*t,q*r-p*s]>=r*u-t*s);endfunction

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

program inTriagle
   real, dimension(2) :: a,b,c,x
   do 
      print*,"Enter coordinates as x,a,b,c"
      read*,x,a,b,c
      if(all(x==0.0).and.all(a==0.0).and.all(b==0.0).and.all(c==0.0)) exit
      print*,"Is point in triangle: ",T(x,a,b,c)
   enddo
 contains!                       
   logical function L(x)
     real::x(8)
     p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3)
     s=x(6)-x(4);t=x(7)-x(3);u=x(8)-x(4)
     L=ALL([p*(s-u)+q*(t-r)+r*u-t*s,p*u-q*t,q*r-p*s]>=r*u-t*s)
   endfunction
end program inTriagle
Kyle Kanos
źródło
1
Możesz to nieco skrócić, opierając się na niejawnym pisaniu Fortrana i używając pojedynczej tablicy wejściowej zawierającej wszystkie 8 liczb: 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);endPróbowałem skrócić to dalej, używając operacji list, ale niestety nie wyszło to zbyt dobrze.
Ventero,
1
Jeszcze krótszy, eliminując częstsze podwyrażenia: 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);endmam 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.
Ventero,
@Ventero: Nie mogę uwierzyć, że zapomniałem nadużywać niejawnego pisania :(. Dzięki za pomoc!
Kyle Kanos
@Ventero: Wygląda na to, że moja odpowiedź zależy od orientacji trójkąta. Pierwszym Trueprzykładem OP daje Falsegdybym zamienić Bi C„s wartości, dając Truedo orientacji oryginału.
Kyle Kanos
Ach, w rzeczywistości problem powstaje, gdy (ponowne użycie notacji z mojego poprzedniego komentarza) a < 0, co skutecznie odwraca warunek, który musisz przetestować. Niestety nie da się tego naprawić, pakując wszystko w abs, ponieważ wówczas domniemany warunek bi dposiadanie tego samego znaku, gdy asię 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.
Ventero
2

MATLAB: 9!

Nie za dużo o mnie pisać

inpolygon

Można nazwać tak:

inpolygon(2/3, 2/3, [0 1 1], [0 0 1])

Dane wyjściowe są przypisywane do zmiennej o nazwie ans


Gdybym musiał napisać funkcję, może być coś takiego, prawdopodobnie można ją zoptymalizować:

function y=f(a,b,c,d)
inpolygon(a,b,c,d)
Dennis Jaheruddin
źródło
2
może być krótszy za pomocą uchwytu funkcji:f=@(a,b,c,d)inpolygon(a,b,c,d)
jpjacobs
2

C # 218 (149?)

using P=System.Drawing.PointF;
bool F(P[]p){for(int i=0;i<4;i++){p[i].X*=1e7f;p[i].Y*=1e7f;}P[]a=new P[3];Array.Copy(p,1,a,0,3);var g=new System.Drawing.Drawing2D.GraphicsPath();g.AddLines(a);return g.IsVisible(p[0]);}

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 GraphicsPathużywa intwewnę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.Linqi System.Drawingsą one dość standardowe w większości projektów WinForm, ale System.Drawing.Drawing2Dmogą być nieco rozciągnięte):

bool G(PointF[]p){for(int i=0;i<4;i++){p[i].X*=1e7f;p[i].Y*=1e7f;}var g=new GraphicsPath();g.AddLines(p.Skip(1).ToArray());return g.IsVisible(p[0]);}

Program testowy (tak, jest brzydki):

using System;
using System.Drawing;
using System.Drawing.Drawing2D;
using P=System.Drawing.PointF;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        Program prog = new Program();
        foreach (string test in
@"[(-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)]
[(-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)]".Split('\n'))
        {
            string t = test.Replace("[(", "").Replace(")]", "");
            string[] points = t.Split(new string[] { "), (" }, StringSplitOptions.None);

            string[] p = points[0].Split(',');
            P[] xabc = new P[4];

            for (int i = 0; i < 4; i++)
            {
                p = points[i].Split(',');
                xabc[i] = new F(float.Parse(p[0]), float.Parse(p[1]));
            }

            Console.WriteLine(test + "=>" + prog.F(xabc));
        }

        Console.ReadKey();
    }

    bool G(PointF[]p)
    {
        for(int i=0;i<4;i++){p[i].X*=1e7f;p[i].Y*=1e7f;}
        var g=new GraphicsPath();
        g.AddLines(p.Skip(1).ToArray());
        return g.IsVisible(p[0]);
    }

    bool F(P[]p)
    {
        for(int i=0;i<4;i++){p[i].X*=1e7f;p[i].Y*=1e7f;}
        var g=new System.Drawing.Drawing2D.GraphicsPath();
        g.AddLines(p.Skip(1).ToArray());
        return g.IsVisible(p[0]);
    }
}
Kok
źródło
Urocze, silnik do rysowania wykonuje pracę.
xnor
2

Haskell - 233 127

Używanie produktów krzyżowych, jak opisano tutaj :

h(a,b)(p,q)(r,s)(t,u)=z a b p q r s==z a b r s t u&&z a b r s t u==z a b t u p q where z j k l m n o =(o-m)*(j-l)+(l-n)*(k-m)>0

Poprzednie rozwiązanie wdrożone przy użyciu współrzędnych barycentrycznych i wzorów opisanych w tej odpowiedzi Stack Exchange :

g(p,q)(r,s)(t,u)(v,w)=
 let (j,k)=(p+(-r),q+(-s))
     (l,m)=(t+(-r),u+(-s))
     (n,o)=(v+(-r),w+(-s))
     d=l*o-n*m
     a=(j*(m-o)+k*(n-l)+l*o-n*m)/d
     b=(j*o-k*n)/d
     c=(k*l-j*m)/d
 in (0<=a&&a<1)&&(0<=b&&b<1)&&(0<=c&&c<1)

Obie funkcje gi hbiorą 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:

let trueTestCases =
  [((-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))]

let falseTestCases =
  [((-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))]

type Point = (Double, Double)

test :: [(Point, Point, Point, Point)] -> [Bool]
test testCases =
  map (\((px,py),(ax,ay),(bx,by),(cx,cy)) -> h (px,py) (ax,ay) (bx,by) (cx,cy)) testCases

test trueTestCases --> [True,True,True,True,True,True,True,True,True,True]
test falseTestCases --> [False,False,False,False,False,False,False,False,False,False]

Niegolfowane rozwiązania:

type Point = (Double, Double)

-- using cross products

triangulate' (a, b) (p, q) (r, s) (t, u) =
  (side a b p q r s == side a b r s t u) && (side a b r s t u == side a b t u p q)
  where side j k l m n o = (o - m) * (j - l) + (-n + l) * (k - m) >= 0

-- using barycentric coordinates

triangulate :: (Point, Point, Point, Point) -> Bool
triangulate ((px, py), (ax, ay), (bx, by), (cx, cy)) = 
  let (p'x, p'y) = (px + (-ax), py + (-ay))
      (b'x, b'y) = (bx + (-ax), by + (-ay))
      (c'x, c'y) = (cx + (-ax), cy + (-ay))
      d = b'x * c'y - c'x * b'y
      a = (p'x * (b'y - c'y) + p'y * (c'x - b'x) + b'x * c'y - c'x * b'y) / d
      b = (p'x * c'y - p'y * c'x) / d
      c = (p'y * b'x - p'x * b'y) / d
  in
      (0 <= a && a < 1) && (0 <= b && b < 1) && (0 <= c && c < 1)
OI
źródło
2

JavaScript (ES6) 120

C=(p,q,i,j,k,l,m,n,
 z=j*(m-k)+i*(l-n)+k*n-l*m,
 s=(j*m-i*n+(n-j)*p+(i-m)*q)/z,
 t=(i*l-j*k+(j-l)*p+(k-i)*q)/z
)=>s>0&t>0&s+t<1

Bezpośrednio skopiowane z mojej odpowiedzi na to drugie pytanie

Testuj w konsoli FireFox / FireBug

Wyjście wszystkich 1s

;[
C(-0.31961, -0.12646, 0.38478, 0.37419, -0.30613, -0.59754, -0.85548, 0.6633),
C(-0.87427, -0.00831, 0.78829, 0.60409, -0.90904, -0.13856, -0.80685, 0.48468),
C(0.28997, -0.03668, -0.28362, 0.42831, 0.39332, -0.07474, -0.48694, -0.10497),
C(-0.07783, 0.04415, -0.34355, -0.07161, 0.59105, -0.93145, 0.29402, 0.90334),
C(0.36107, 0.05389, 0.27103, 0.47754, -0.00341, -0.79472, 0.82549, -0.29028),
C(-0.01655, -0.20437, -0.36194, -0.90281, -0.26515, -0.4172, 0.36181, 0.51683),
C(-0.12198, -0.45897, -0.35128, -0.85405, 0.84566, 0.99364, 0.13767, 0.78618),
C(-0.03847, -0.81531, -0.18704, -0.33282, -0.95717, -0.6337, 0.10976, -0.88374),
C(0.07904, -0.06245, 0.95181, -0.84223, -0.75583, -0.34406, 0.16785, 0.87519),
C(-0.33485, 0.53875, -0.25173, 0.51317, -0.62441, -0.90698, -0.47925, 0.74832)
]

Wyjście wszystkich zer

;[
C(-0.99103, 0.43842,0.78128, -0.10985,-0.84714, -0.20558,-0.08925, -0.78608),
C(0.15087, -0.56212,-0.87374, -0.3787,0.86403, 0.60374,0.01392, 0.84362),
C(0.1114, 0.66496,-0.92633, 0.27408,0.92439, 0.43692,0.8298, -0.29647),
C(0.87786, -0.8594,-0.42283, -0.97999,0.58659, -0.327,-0.22656, 0.80896),
C(0.43525, -0.8923,0.86119, 0.78278,-0.01348, 0.98093,-0.56244, -0.75129),
C(-0.73365, 0.28332,0.63263, 0.17177,-0.38398, -0.43497,-0.31123, 0.73168),
C(-0.57694, -0.87713,-0.93622, 0.89397,0.93117, 0.40775,0.2323, -0.30718),
C(0.91059, 0.75966,0.60118, 0.73186,0.32178, 0.88296,-0.90087, -0.26367),
C(0.3463, -0.89397,0.99108, 0.13557,0.50122, -0.8724,0.43385, 0.00167),
C(0.88121, 0.36469,-0.29829, 0.21429,0.31395, 0.2734,0.43267, -0.78192)
]
edc65
źródło
2

SmileBASIC, 111 100 znaków

DEF T X,Y,A,B,C,D,E,F
Q=9e5GCLS
GTRI(A-X)*Q,Q*(B-Y),Q*(C-X),Q*(D-Y),Q*(E-X),Q*(F-Y)?!!GSPOIT(0,0)END

Rysuje 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.

12Me21
źródło
2

Montaż procesora Intel 8087 FPU, 222 220 bajtów

Do 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):

; calculate the area of of a triangle ABC using determinate
; input: coordinates (float), Ax,Ay,Bx,By,Cx,Cy
; output: area in ST
TAREA   MACRO   A1,A2,B1,B2,C1,C2
    FLD  A1
    FLD  B2
    FLD  C2
    FSUB        ; ST = By - Cy
    FMUL        ; ST = Ax * ( By - Cy )
    FLD  B1 
    FLD  C2
    FLD  A2
    FSUB        ; ST = Cy - Ay
    FMUL        ; ST = Bx * ( Cy - Ay )
    FLD  C1
    FLD  A2
    FLD  B2
    FSUB        ; Ay - By
    FMUL        ; Cx * ( Ay - By )
    FADD        ; Cx * ( Ay - By ) + Bx * ( Cy - Ay )
    FADD        ; Cx * ( Ay - By ) + Bx * ( Cy - Ay ) + Ax * ( By - Cy )
    FLD1        ; make a value of 2
    FADD ST,ST  ; ST = 2
    FDIV        ; divide by 2
    FABS        ; take abs value
        ENDM

; determine if point X is in triangle ABC
; input: points X, A, B, C
; output: ZF=1 if X in triangle, ZF=0 if X not in triangle
TXINABC     MACRO X1,X2,A1,A2,B1,B2,C1,C2

    TAREA  A1,A2,B1,B2,C1,C2    ; ST(3) = area of triangle ABC
    TAREA  X1,X2,B1,B2,C1,C2    ; ST(2) = area of triangle XBC
    TAREA  A1,A2,X1,X2,C1,C2    ; ST(1) = area of triangle AXC
    TAREA  A1,A2,B1,B2,X1,X2    ; ST(0) = area of triangle ABX

    FADD        ; add areas of triangles with point
    FADD        ; ST = ST + ST(1) + ST(2)
    FCOMPP      ; compare ST to ST(1) and pop results
    FWAIT       ; sync CPU/FPU
    FSTSW R     ; store result flags to R
    MOV  AX, R  ; move result to AX
    SAHF        ; store result into CPU flags for conditional check
        ENDM

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:

TTEST   MACRO T
        LOCAL IS_IN_TRI

    TXINABC T,T+4*1,T+4*2,T+4*3,T+4*4,T+4*5,T+4*6,T+4*7
    MOV  DX, OFFSET TEQ     ; load true string by default 
    JZ   IS_IN_TRI          ; if ZF=1, it is in triangle, skip to display
    MOV  DX, OFFSET FEQ     ; otherwise ZF=0 means not in triangle, so load false string
IS_IN_TRI:
    MOV  AH, 9              ; DOS write string function
    INT  21H 
        ENDM

START:
    FINIT                   ; reset 8087

    TTEST   T0              ; true tests
    TTEST   T1
    TTEST   T2
    TTEST   T3
    TTEST   T4
    TTEST   T5
    TTEST   T6
    TTEST   T7
    TTEST   T8
    TTEST   T9

    TTEST   F0              ; false tests
    TTEST   F1
    TTEST   F2
    TTEST   F3
    TTEST   F4
    TTEST   F5
    TTEST   F6  
    TTEST   F7
    TTEST   F8  
    TTEST   F9

    RET         ; return to DOS

T0  DD  -0.31961, -0.12646, 0.38478, 0.37419, -0.30613, -0.59754, -0.85548, 0.6633
T1  DD  -0.87427, -0.00831, 0.78829, 0.60409, -0.90904, -0.13856, -0.80685, 0.48468
T2  DD  0.28997, -0.03668, -0.28362, 0.42831, 0.39332, -0.07474, -0.48694, -0.10497
T3  DD  -0.07783, 0.04415, -0.34355, -0.07161, 0.59105, -0.93145, 0.29402, 0.90334
T4  DD  0.36107, 0.05389, 0.27103, 0.47754, -0.00341, -0.79472, 0.82549, -0.29028
T5  DD  -0.01655, -0.20437, -0.36194, -0.90281, -0.26515, -0.4172, 0.36181, 0.51683
T6  DD  -0.12198, -0.45897, -0.35128, -0.85405, 0.84566, 0.99364, 0.13767, 0.78618
T7  DD  -0.03847, -0.81531, -0.18704, -0.33282, -0.95717, -0.6337, 0.10976, -0.88374
T8  DD  0.07904, -0.06245, 0.95181, -0.84223, -0.75583, -0.34406, 0.16785, 0.87519
T9  DD  -0.33485, 0.53875, -0.25173, 0.51317, -0.62441, -0.90698, -0.47925, 0.74832

F0  DD  -0.99103, 0.43842, 0.78128, -0.10985, -0.84714, -0.20558, -0.08925, -0.78608
F1  DD  0.15087, -0.56212, -0.87374, -0.3787, 0.86403, 0.60374, 0.01392, 0.84362
F2  DD  0.1114, 0.66496, -0.92633, 0.27408, 0.92439, 0.43692, 0.8298, -0.29647
F3  DD  0.87786, -0.8594, -0.42283, -0.97999, 0.58659, -0.327, -0.22656, 0.80896
F4  DD  0.43525, -0.8923, 0.86119, 0.78278, -0.01348, 0.98093, -0.56244, -0.75129
F5  DD  -0.73365, 0.28332, 0.63263, 0.17177, -0.38398, -0.43497, -0.31123, 0.73168
F6  DD  -0.57694, -0.87713, -0.93622, 0.89397, 0.93117, 0.40775, 0.2323, -0.30718
F7  DD  0.91059, 0.75966, 0.60118, 0.73186, 0.32178, 0.88296, -0.90087, -0.26367
F8  DD  0.3463, -0.89397, 0.99108, 0.13557, 0.50122, -0.8724, 0.43385, 0.00167
F9  DD  0.88121, 0.36469, -0.29829, 0.21429, 0.31395, 0.2734, 0.43267, -0.78192

TEQ DB 'In Triangle',0DH,0AH,'$'
FEQ DB 'Not In Triangle',0DH,0AH,'$'

Wydajność

In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
640 KB
źródło
1

C 414 (było 465)

Grał w golfa

#define D double 
int F(D ax,D ay,D bx,D by,D cx,D cy,D px,D py){int y=0;double J,K;D m=(ax-bx<0.001)?(by-ay)/(ax-bx):1000;D b=m*ax+ay;J=m*cx-cy+b;K=m*px-py+b;if(J*K>=0)y=1;return y;}D T[8],k;int i,n;void G(){while(i<8){scanf("%lf",&k);T[i++]=k;}n+=F(T[2],T[3],T[4],T[5],T[6],T[7],T[0],T[1]);n+=F(T[4],T[5],T[6],T[7],T[2],T[3],T[0],T[1]);n+=F(T[2],T[3],T[6],T[7],T[4],T[5],T[0],T[1]);printf(n==3?"True":"False");}

Dodano oryginalną deklarację funkcji w celu wyjaśnienia

/**
* determine if points C & P are on same side of line AB
* return 1 if true, 0 otherwise
*/
int PointsSameSide(D ax,D ay,D bx,D by,D cx, D cy, D px, D py);

Przepisany jako funkcja o nazwie: wejście przez stdin po jednym wierszu lub wszystkie w jednym wierszu oddzielone spacjami.

#define D double
int F(D ax,D ay,D bx,D by,D cx, D cy, D px, D py)
{
int y=0;
double J,K;
D m = (ax-bx<0.001)?(by-ay)/(ax-bx):1000;
D b = m*ax+ay;
J=m*cx-cy+b;
K=m*px-py+b;
if(J*K>=0)y=1;
return y;
}
double T[8],k;
int i,n;
void G()
{
while(i<8){scanf("%lf",&k);T[i++]=k;}
n+=F(T[2],T[3],T[4],T[5],T[6],T[7],T[0],T[1]);
n+=F(T[4],T[5],T[6],T[7],T[2],T[3],T[0],T[1]);
n+=F(T[2],T[3],T[6],T[7],T[4],T[5],T[0],T[1]);
printf(n==3?"True":"False");
}
Bacchusbeale
źródło
3
Możesz zaoszczędzić trochę bajtów, pozbywając się nowych linii i niepotrzebnych spacji. Ponadto, zostały doublena nowo jako Dale nadal używać doublew kodzie.
gronostaj
1

Java, 149 znaków

g=Math.atan2(100*(d-y),(a-x));h=Math.atan2(100*(e-y),(b-x));i=Math.atan2(100*(f-y),(c-x));k=Math.round(Math.abs(g-h)+Math.abs(h-i)+Math.abs(i-g))==6;

Okropne, biorąc pod uwagę, że muszę napisać „Matematyka”. każdego razu. To jest rzeczywisty program:

package mathPackage;
public class InTriangle {
public static void main(String[] args) {
    boolean k;
    double a=-1,b=0,c=1,d=0,e=1,f=0,x=0,y=0.4;
    double g,h,i;
    g=Math.atan2(100*(d-y),(a-x));
    h=Math.atan2(100*(e-y),(b-x));
    i=Math.atan2(100*(f-y),(c-x));
    k=Math.round(Math.abs(g-h)+Math.abs(h-i)+Math.abs(i-g))==6;
    System.out.println(k);
    System.out.println(g);
    System.out.println(h);
    System.out.println(i);
    System.out.print(Math.abs(g-h)+Math.abs(h-i)+Math.abs(i-g));
}
}

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.

colorado777
źródło
1
Do czego służą 100*?
xnor
1

JavaScript 125/198

Jeśli punkty są podane w 8 argumentach:

function d(x,y,a,b,c,d,e,f){function z(a,b,c,d){return(y-b)*(c-a)-(x-a)*(d-b)>0}return(z(a,b,c,d)+z(c,d,e,f)+z(e,f,a,b))%3<1}

Jeśli punkty są podane w układzie dwuwymiarowym:

function c(s){return (z(s[1][0],s[1][1],s[2][0],s[2][1])+z(s[2][0],s[2][1],s[3][0],s[3][1])+z(s[3][0],s[3][1],s[1][0],s[1][1]))%3<1;function z(a,b,c,d){return (s[0][1]-b)*(c-a)-(s[0][0]-a)*(d-b)>0}}

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:

(y-b)(c-a) - (x-a)(d-b)

który mówi, że punkt jest po której stronie linii , pochodzi z przestawienia definicji nachylenia:

            m = (y2-y1)/(x2-x1)
      (y2-y1) = m(x2-x1)
       (y-y1) = m(x-x1)     ,substituting point we are testing (x,y) to be the 2nd point
       (y-y1) = (x-x1)(y2-y1)/(x2-x1)  ,substitute back the original definition of m
(y-y1)(x2-x1) = (x-x1)(y2-y1)    <-- left side will be greater than the right side, if
                                     the point is on the left; otherwise, it's on the right
            0 = (y-b)(c-a)-(x-a)(d-b) ,where (a,b)=(x1,y1), (c,d)=(x2,y2)

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/

var l = [[-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],
         [-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]];

function d(x,y,a,b,c,d,e,f){function z(a,b,c,d){return(y-b)*(c-a)-(x-a)*(d-b)>0}return(z(a,b,c,d)+z(c,d,e,f)+z(e,f,a,b))%3<1}

for(var i = 0; i < l.length; i++){
    console.log(d.apply(undefined,l[i]));    //10 true, 10 false
}

97 znaków (nie licząc spacji ani tabulatorów) liczy się, jeśli zostanie przekonwertowany na CoffeeScript:

d=(x,y,a,b,c,d,e,f)->
    z=(a,b,c,d)->
        (y-b)*(c-a)-(x-a)*(d-b)>0
    (z(a,b,c,d)+z(c,d,e,f)+z(e,f,a,b))%3<1

115 znaków w przypadku konwersji do ES6:

d=(x,y,a,b,c,d,e,f)=>{z=(a,b,c,d)=>{return (y-b)*(c-a)-(x-a)*(d-b)>0};return(z(a,b,c,d)+z(c,d,e,f)+z(e,f,a,b))%3<1}
Derek 朕 會 功夫
źródło
To jest „fantazyjna matematyka wektorowa”, której używam: D (ale nie fantazyjne podejście do współrzędnych barycentrycznych, które przyjęli niektórzy inni). Podobnie jak w przypadku najczęściej głosowanej odpowiedzi, możesz zapisać kilka bajtów, używając ES6 i definiując funkcje takie jak d=(x,y,...)=>{...}. W twoim przypadku możesz zaoszczędzić jeszcze więcej, używając CoffeeScript, który nie potrzebuje return: pastebin.com/RVFk1D5k ... a w każdym razie możesz zapisać jeden bajt, używając <1zamiast ==0.
Martin Ender
@ m.buettner: o Myślałem, że użyte równanie nie ma nic wspólnego z wektorami (pochodzącymi z prostej algebry), ale najwyraźniej oba dają to samo równanie. Matematyka jest cudowna.
Derek 朕 會 功夫
1

R 23

Zainspirowany MATLAB ,

SDMTools::pnt.in.poly()

nazywany jak SDMTools::pnt.in.poly(point,triangle)gdzie pointjest wektorem długości-2 i trianglejest macierzą 3x2 wierzchołków. SDMTools jest dostępny w CRAN.

Shadowtalker
źródło
1

Mathematica, 38 znaków

RegionMember[Polygon[#[[1]]],#[[2]]] &

Przykład:

d = {{{0, 0}, {1, 0}, {.5, .7}}, {.5, .6}};

RegionMember[Polygon[#[[1]]], #[[2]]] & @ d

(* Prawdziwe *)

David G. Stork
źródło
Standardowo liczy się spacje jako postacie, ale prawdopodobnie tutaj można je usuwać bez łamania.
xnor
1
Ponadto należy pobierać dane wejściowe i generować dane wyjściowe zamiast używać predefiniowanych zmiennych. Możesz wyszukać niektóre odpowiedzi Mathematica, aby zobaczyć, jak to robią.
xnor
0

C (gcc) , 108 bajtów

i;f(a,b,c,d,e,f,g,h)float a,b,c,d,e,f,g,h;{i=(e-=a)*(h-=b)>(f-=b)*(g-=a);i=(c-=a)*f>(d-=b)*e==i&i==g*d>h*c;}

Wypróbuj online!

Pobiera trzy produkty krzyżowe i zwraca, 1jeśli znak komponentu się nie zmienia.

sufitowy
źródło