Überprüfen Sie, ob der Punkt im Dreieck liegt

40

Ihr Ziel ist es zu bestimmen, ob ein gegebener 2D-Punkt X im Bereich des Dreiecks mit gegebenen Eckpunkten A, B, C liegt.

Schreiben Sie eine Funktion, die die Koordinaten des Testpunkts X und der drei Eckpunkte des Dreiecks (also insgesamt 8 Koordinaten) aufnimmt und True zurückgibt, wenn der Punkt in diesem Dreieck liegt, und False, wenn er außerhalb liegt.

Mach dir keine Sorgen über Edge Cases. Wenn der Punkt auf der Grenze des Dreiecks (Kante oder Scheitelpunkt) liegt oder das Dreieck tatsächlich ein Liniensegment ist, kann Ihr Code alles tun, einschließlich Abstürzen. Sorgen Sie sich auch nicht um numerische Stabilität oder Gleitkommapräzision.

Ihr Code muss eine benannte Funktion sein. Code-Schnipsel werden nicht akzeptiert.

Die wenigsten Charaktere gewinnen.

Eingang:

Acht reelle Zahlen, die Koordinaten darstellen. Die Zahlen liegen im Bereich (-1,1).

Das genaue Eingabeformat ist flexibel. Sie können beispielsweise acht Zahlen, eine Liste mit acht Zahlen, eine Liste mit vier Punkten, die jeweils durch ein Tupel gegeben sind, eine 2 * 4-Matrix, vier komplexe Zahlen, zwei Listen mit den x- und y-Koordinaten, und so weiter.

Die Eingabe muss lediglich aus den Zahlen in einem Container ohne zusätzliche Daten bestehen. Sie können die Eingabe weder für die Vorverarbeitung verwenden, noch benötigen Sie Einschränkungen für die Eingabe, z. B. die Angabe der Punkte in aufsteigender y-Koordinate. Ihre Eingabe muss acht beliebige Koordinaten zulassen (obwohl sich Ihr Code in den oben genannten Randfällen beliebig verhalten kann).

Bitte geben Sie Ihr Eingabeformat an.

Ausgabe:

Entweder das entsprechende Boolesche True/ False, die entsprechende Zahl 1/ 0oder die Analoga in Ihrer Sprache.

Testfälle

Die Eingaben erhalten eine Liste [X,A,B,C]von vier Tupeln, zuerst den Testpunkt, dann die drei Dreieckscheitelpunkte. Ich habe sie in diejenigen gruppiert, deren Ausgaben sein sollten Trueund diejenigen, die sein sollten False.

True Instanzen:

[(-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 Instanzen:

[(-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
quelle
Wie definieren Sie einen Charakter? ASCII? In 7 Bit codierbar? In einem Byte? Irgendein Unicode?
Isaacg
Was schlagen Sie vor? Es gibt bereits Lösungen, die komprimierten Code verwenden.
Xnor
Normalerweise glaube ich, dass Bytes für Nicht-ASCII-Zeichen verwendet werden, da sonst der Utf-32-Vorteil unüberwindbar ist.
Isaacg
Nun, ich kann jetzt nicht zurückgehen. Jedes Unicode-Zeichen ist ein Zeichen. Komprimieren Sie, wenn Sie möchten.
XNOR

Antworten:

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}

ECMAScript 6 Version (danke m.buettner, speichert 6 Zeichen)

$=(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}

Nennen Sie es als solches (Rückgabe trueoder false):

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

Verwendet einige ausgefallene baryzentrische Koordinatenmathematik basierend auf dem Code aus dieser Antwort . Eine ungolfed Version für Ihr Lesevergnügen folgt:

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
quelle
12
+1, wenn auch nur für die Parameternamen!
Matt
Warum musst du mein UserScript zum Zählen von Zeichen unterbrechen ???
kitcar2000
@ kitcar2000 was meinst du?
Abraham
Die Regeln besagen, dass Zeichen gezählt werden, keine Bytes. Sie können also Folgendes verwenden: xem.github.io/obfuscatweet , um in 122 Zeichen zu passen
xem
1
Irre ich mich, oder hättest du (a*(l-n)+i*(g-e)+n*e-g*l)stattdessen verwenden können (-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

Mein erster Code-Golf-Versuch!

Code

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

Nimmt als Eingabe (x, y, t), wobei (x, y) der Punkt ist, den wir überprüfen, und t ein Dreieck ist, t = ((x1, y1), (x2, y2), (x3, y3)).

Erläuterung

Ich berechne die Determinanten der Matrizen

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

Diese Determinanten repräsentieren die vorzeichenbehafteten Abstände von den Seiten des Dreiecks zum Punkt (x, y). Wenn alle dasselbe Vorzeichen haben, befindet sich der Punkt auf der gleichen Seite jeder Linie und ist somit im Dreieck enthalten.

Im obigen Code a*y+c*b+d*x-d*a-c*y-b*xist eine Determinante einer dieser Matrizen.

Ich nutze die Tatsache, dass True+True+True==3und False+False+False==0um festzustellen, ob diese Determinanten alle das gleiche Vorzeichen haben.

Ich benutze Pythons Negativlisten-Indizes, indem ich t[-1]anstelle von benutze t[(i+1)%3].

Vielen Dank an Peter für die Idee, s%3<1anstelle von s in(0,3)zu prüfen, ob s entweder 0 oder 3 ist!

Sagemath Version

Keine wirklich andere Lösung, daher beziehe ich sie in diese Antwort ein, eine Sagemath-Lösung mit 80 Zeichen:

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

wo p=[x,y]undt=[[x1,y1],[x2,y2],[x3,y3]]

Alex L
quelle
1
Könnte s in (0,3)auf gekürzt werden s%3<1?
Peter Taylor
1
Die Verwendung negativer Indizes kann optimiert werden, um einen weiteren Index zu sparen: -1,0,1 ... t[i]+t[i+1]entspricht0,1,2 ... t[i-1]+t[i]
Peter Taylor
@ PeterTaylor Absolut richtig! Schade, dass ich das Leerzeichen entfernt habe, in -1,0,1bevor ich das gelesen habe. Eigentlich ist dein Weg besser lesbar, also werde ich ihn trotzdem benutzen.
Alex L
1
Willkommen beim Code Golf! Sie können die eckigen Klammern für das Listenverständnis in der sumentfernen, wenn Sie die 0,1,2in Klammern stehenden Zeichen einschließen. In diesem Fall ersetzen Sie ein Leerzeichen. Der Grund dafür ist, dass Python die Übergabe von uneingeschränktem Verständnis an Funktionen zulässt, aber die Kommas im nackten Tupel 1,2,3verwirren es, weil es versucht, sie als separate Argumente zu analysieren.
xnor
16

Mathematica, 67 Bytes

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

Die Funktion akzeptiert zwei Argumente, den Punkt Xund eine Liste von Punkten {A,B,C}, die als #und #2bezeichnet werden. Das ist, wenn Sie anrufen

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

dann bekommst du #wie Xund #2wie {A,B,C}. (Beachten Sie, dass zwei andere anonyme Funktionen im Code verschachtelt sind - #und #2innerhalb dieser Funktionen eine andere Bedeutung haben.)

Hier ist eine Erklärung der Funktion selbst:

                                              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. *)

Beachten Sie, dass diese Funktion tatsächlich für jedes konvexe n-Gon funktioniert, solange seine Scheitelpunkte entweder im Uhrzeigersinn oder gegen den Uhrzeigersinn angegeben werden.

Martin Ender
quelle
Wäre es nicht effizienter zu überprüfen, ob das Produkt der Entfernungen positiv ist, als wenn alle Vorzeichen gleich sind? Ich weiß nicht Mathematica, aber es scheint, dass das einfacher sein sollte.
isaacg
@isaacg Es gibt drei Begriffe. Wenn sie alle negativ sind, ist ihr Produkt negativ, und wenn sie alle positiv sind, ist ihr Produkt positiv. Ihr Ansatz funktioniert nur, wenn die Vorzeichen zweier Zahlen gleich sein sollen.
Martin Ender
Warum nicht benutzen Det?
Alephalpha
@alephalpha Na ja, wahrscheinlich, weil ich nicht daran gedacht habe. : P ... Ich werde das untersuchen
Martin Ender
@alephalpha Hm nein, ich kann im Moment keinen Weg finden, die drei erforderlichen Matrizen in weniger Zeichen zu erstellen.
Martin Ender
7

CJam, 66 63 59 52 46 34 32 31 30 28 Zeichen

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

Nach der Transformation der Unicode-Zeichenfolge wird der folgende Code ( 33 Byte ) ausgewertet:

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

Erwartet X [A B C]als Eingabe, wobei jeder Punkt von der Form ist [double double]. Ausgang ist 1 oder 0.

Probieren Sie es online aus.

Ein großes Dankeschön geht an user23013 für das Speichern von 6 Zeichen (13 Byte unkomprimierter Code)!

Testfälle

$ 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
quelle
Ist das eine benannte Funktion?
Martin Ender
@ m.buettner: So ähnlich. Das offizielle Wiki besagt Folgendes: Block - Ein Programmabschnitt, der von einer einzigen Einheit abgegrenzt {und }als solche behandelt wird. Ähnlich wie Codeblöcke in C / Java, mit der Ausnahme, dass Blöcke erstklassige Objekte sind und Variablen zugewiesen werden können (wodurch Funktionen definiert werden).
Dennis
1
@xnor 1m<@m*bereitet 3 Paare von X und den nächsten ( i+1th) Eckpunkt des Dreiecks vor. @-@@-Verschiebt den aktuellen ( ith) Scheitelpunkt zum Ursprung (und spiegelt ihn, wenn dies nicht der @-\@-Fall ist, aber es spielt keine Rolle). @@*@@*>berechnet die Z-Achse des Kreuzprodukts, auch Determinante genannt, und gibt zurück, 1wenn es negativ ist. :+3%!Gibt zurück, ob sie alle gleich sind, dh alle 3 sind negativ oder nicht negativ, was mit Ausnahme der Kantenfälle positiv bedeutet. Ich denke, es ist schwieriger, CJam zu lesen als Golf zu spielen.
Jimmy23013
1
37 Bytes {[_1m<\]z\f{f{+~@-@@-}~@@*@@*>})-!}:T. Verwenden Sie 2m>oder Wm<für die Unicode-Sicherheit.
Jimmy23013
1
33 Bytes:{2*2/\f{f{+~@-@@-}~@@*@@*>})-!}:T
Jimmy23013
5

C - 156 Bytes

Die Eingabe besteht aus einem Array von 3 Gleitkommazahlen in X, 3 Gleitkommazahlen in Y und getrennten x- und y-Werten für den Testpunkt. Bonus: behandelt alle Randfälle!

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;}

Angepasst von PNPOLY.


quelle
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 - getestet in Javascript
bebe
@bebe - Das verursacht einen Syntaxfehler.
Derek 朕 朕 功夫
Dass keine Syntaxfehler auftreten.
bebe
4

Pyth 1.0.5 , 57 54 51

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

Definiert die Funktion g, die zwei Eingaben übernimmt: den Testpunkt und dann die Liste der Eckpunkte des Dreiecks. Ausgänge Trueund False. Hinweis: Zerstört die Eingabe, insbesondere b, die Liste der Eckpunkte des Dreiecks.

Probieren Sie es hier aus . Bei den letzten Zeichen gvwvwrufen Sie die Funktion mit einem Testfall in den nächsten beiden Zeilen auf.

Basierend auf diesem Algorithmus

Erläuterung:

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)

Der CJam-Pyth-Krieg tobt weiter!

isaacg
quelle
Dies sollte eine benannte Funktion sein. Ist wunter STDIN Eingang?
Xnor
@xnor Hoppla, ich habe diesen Teil der Beschreibung verpasst. Wird bearbeiten.
Isaacg
@xnor Sind Funktionen zum Ausdrucken der Antwort zulässig oder müssen sie die Antwort zurückgeben? Derzeit wird die Antwort ausgedruckt, aber ich könnte sie für ein weiteres Zeichen zurückgeben lassen.
Isaacg
Antwort zurücksenden.
xnor
Können Sie vielleicht Zeichen speichern, indem Sie den Zähler Zdurch einen leeren Satz ersetzen, mit dem Sie akkumulieren Z|=, und dann dessen Länge testen, um zu sehen, ob nur 0die angezeigt werden oder 1nicht? Die Strategie hat sich in Python als länger erwiesen, aber vielleicht lohnt es sich, Pyth-Primitive zu verwenden.
xnor
4

J 64 45 (42 ohne Zuordnung)

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

Die Zuordnung ist nicht erforderlich, damit das Objekt eine Funktion ist. Sie können sich also nicht sicher sein, ob Sie es zählen sollen oder nicht. Nutzen Sie die flexible Eingabe: Ich hätte gerne ein Array von (1 + Anzahl der Eckpunkte) x (Dimensionalität des Raums).

In der Hoffnung, hier ein paar zusätzliche Punkte zu erzielen ...: Dieses Ding funktioniert für jede Dimension von Simplex, nicht nur für Dreiecke in einer Ebene, sondern auch für eine dreiseitige Pyramide im 3D-Raum und so weiter. Es funktioniert auch, wenn die Anzahl der Eckpunkte des Simplex kleiner als (n + 1) ist. Dann wird berechnet, ob die Projektion des Punkts auf den Simplex innerhalb liegt oder nicht.

Es wird in Schwerpunktkoordinaten konvertiert und dann auf negative Koordinaten überprüft, um anzuzeigen, dass der Punkt außerhalb liegt. Denken Sie daran, J verwendet _ für negativ

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

Ein Lauf auf die gegebenen Beispiele:

   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
quelle
Ich habe nach einer benannten Funktion gefragt, damit die Zuweisungszeichen zählen. Hier sind einige Punkte für die Verallgemeinerung auf Polygone! ······
xnor
Nun, eigentlich verallgemeinere ich nicht auf Polygone, sondern auf N-dimensionale Simplexe mit maximalen N+1Eckpunkten. Zum Beispiel eine Pyramide mit 4 Ecken im 3-D-Raum oder ein Simplex mit 5 Ecken im 4-D-Raum. Die Anzahl der Eckpunkte kann niedriger sein als N+1. In diesem Fall prüft der Algorithmus, ob die orthogonale Projektion auf die Hyperebene, in der sich der Simplex befindet, innerhalb des Simplex liegt oder nicht (z. B. wird ein 2-Punkt-Simplex in 2D auf die Linie projiziert und überprüft ob diese Projektion zwischen den Endpunkten liegt)
jpjacobs
4

HTML5 + JS, 13b + 146b / 141b / 114 Zeichen

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]}

oder 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]}

oder ES6 unicode-obfuscated (114 Zeichen):

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

Demo: http://jsfiddle.net/xH8mV/

Unicode-Verschleierung erstellt mit: http://xem.github.io/obfuscatweet/

xem
quelle
Es scheint nicht das richtige Ergebnis zu liefern, wenn sich der Punkt in der Nähe der Seite befindet: jsfiddle.net/L2B2A Ich glaube, das liegt daran, dass alle Eingaben zwischen (-1,1) liegen und Ihr Code nur die 4 Pixel testet der Ursprung.
Derek 朕 朕 功夫
das ist richtig, um den Beispielen zu entsprechen, sollte ich den Ursprung und die Skalierung meiner Leinwand ändern, um Dreiecke innerhalb von [-1,1] zu behandeln. Aber warum sind diese Dreiecke überhaupt so klein?
Xem
Das Problem besagt, dass alle xy zwischen -1 und 1 liegen. Ich weiß nicht genau warum, aber ich glaube, Sie können einfach jede Eingabe mit 1e7 multiplizieren (um die Genauigkeit zu erhalten), um das richtige Ergebnis zu erhalten: D
Derek 朕 朕 功夫
Eine grafische Lösung, sehr clever!
XNOR
3

Python (65)

Die Leute scheinen damit fertig zu sein, also werde ich meine eigene Lösung zu meiner Frage posten.

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

Xist die komplexe Zahl, die die Testpunkte darstellt, und List eine Liste von drei Punkten, von denen jeder eine komplexe Zahl ist.

Zuerst erkläre ich eine weniger gute Version des Codes.

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)

Wir verschieben die Punkte A,B,C,Xso, dass sie Xam Ursprung liegen, und nutzen dabei die in Python integrierte komplexe Arithmetik. Wir müssen überprüfen, ob der Ursprung in der konvexen Hülle von enthalten ist A,B,C. Dies entspricht dem Ursprung, der immer auf der gleichen Seite (links oder rechts) der Liniensegmente AB, BC und AC liegt.

Ein Segment ABhat den Ursprung links, wenn man weniger als 180 Grad gegen den Uhrzeigersinn fährt, um von A nach B zu gelangen, und ansonsten rechts. Wenn wir die Winkel betrachten a, bund cdie diesen Abschnitten entsprechen, bedeutet dies , b-a < 180 degrees(entnommen Winkel im Bereich von 0 bis 360 Grad). Als komplexe Zahlen angle(B/A)=angle(B)/angle(A). Auch angle(x) < 180 degreesgenau auf den Punkt in der oberen Halbebene, den wir über prüfen imag(x)>0.

Ob der Ursprung also links von AB liegt, wird ausgedrückt als (A/B).imag>0. Wenn Sie prüfen, ob diese für jedes zyklische Paar in gleich sind A,B,C, sehen Sie, ob das Dreieck ABCden Ursprung enthält.

Kehren wir nun zum vollständigen Code für den Golfsport zurück

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

Wir generieren jedes zyklische Paar in (A-X,B-X,C-X)=(L[0]-X,L[1]-X,L[2]-X), indem wir negative Python-Listenindizes verwenden, die sich um ( L[-1]= L[2]) drehen . Um zu überprüfen, ob die Bools alle True( 1) oder alle False( 0) sind, fügen wir sie hinzu und überprüfen die Teilbarkeit durch 3, wie es bei vielen Lösungen der Fall war .

xnor
quelle
2

Fortran - 232 218 195 174

Wirklich grauenhaft. Die Funktion ist schrecklich, da die Daten an sie weitergegeben werden müssen und wir sie nicht vorverarbeiten können.

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

Der Rückgang um 14 Zeichen ist darauf zurückzuführen, dass ich vergessen habe, den Funktionsnamen aus meinen Testläufen zu übernehmen. Der weitere Rückgang ist auf die implizite Eingabe und den Verzicht auf die Änderung des Funktionsnamens zurückzuführen. Die nächsten 20 Zeichen kamen durch Einlesen der Punkte als einzelnes Array zustande. Das volle Programm ist

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
quelle
1
Sie können dies ein wenig 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);endverkürzen, indem Sie sich auf Fortrans implizite Eingabe verlassen und ein einzelnes Eingabearray verwenden, das alle 8 Zahlen enthält: Ich habe versucht, dies mithilfe von Listenoperationen weiter zu verkürzen, aber das hat leider nicht sehr gut geklappt.
Ventero
1
Noch kürzer durch Eliminieren häufigerer Unterausdrücke: 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);endIch hoffe, ich habe bei den Transformationen keine Fehler gemacht! Obwohl es so aussieht, als würde Ihr ursprünglicher Code nicht alle Testfälle bestehen.
Ventero
@Ventero: Ich kann nicht glauben, dass ich vergessen habe, das implizite Tippen zu missbrauchen :(. Vielen Dank für Ihre Hilfe!
Kyle Kanos
@Ventero: Es scheint auch, dass meine Antwort von der Ausrichtung des Dreiecks abhängt. Das erste TrueBeispiel in OP gibt an, Falseob ich Bund C's Werte vertausche , während ich Truefür die ursprüngliche Orientierung gebe .
Kyle Kanos
Ach ja, das Problem tritt auf, wenn (unter Wiederverwendung der Notation aus meinem vorherigen Kommentar) a < 0die zu testende Bedingung effektiv umgekehrt wird. Leider kann dies nicht einfach dadurch behoben werden, dass man alles in ein einwickelt abs, da dann der implizite Zustand bund ddas gleiche Vorzeichen averloren geht. Dies kann durch die Verwendung von etwas behoben werden (erneut die Verwendung der Notation und der vordefinierten Variablen aus meinem letzten Kommentar) 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)- was wahrscheinlich mehr Golf sein kann.
Ventero
2

MATLAB: 9!

Nicht viel von mir hier zu schreiben

inpolygon

Kann man so nennen:

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

Die Ausgabe wird einer Variablen mit dem Namen zugewiesen ans


Wenn ich tatsächlich eine Funktion schreiben müsste, könnte es so etwas wie optimiert werden:

function y=f(a,b,c,d)
inpolygon(a,b,c,d)
Dennis Jaheruddin
quelle
2
kann mit einem Funktionshandle kürzer sein: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]);}

Wahrscheinlich nicht so zeicheneffizient wie eine mathematische Methode, aber es macht Spaß, Bibliotheken zu benutzen. Übrigens auch eher langsam.

Nutzen Sie auch die Vorteile von "Sorgen Sie sich nicht um numerische Stabilität oder Gleitkommapräzision." - leider GraphicsPathAnwendungen ints intern, so dass ein Wert im Bereich von -1 <f <1 nur drei mögliche Werte haben. Da Floats nur eine Genauigkeit von 7 Stellen haben, multipliziere ich einfach mit 1e7, um sie in ganze Zahlen umzuwandeln. Hm, ich denke es verliert nicht wirklich an Präzision. Es ist auch auf eine andere Art ausnutzbar: Ich hätte wahrscheinlich den Vorteil ziehen können, die Präzision zu ignorieren und einfach die "falsche" Antwort gegeben zu haben.

Wenn ich die Zeichenkosten für das Importieren von Bibliotheken ignorieren darf, 149 (zumindest System.Linqund System.Drawingin den meisten WinForms-Projekten als Standard zu bezeichnen, kann sich aber als schwierig erweisen System.Drawing.Drawing2D):

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]);}

Testprogramm (ja, es ist hässlich):

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]);
    }
}
Bob
quelle
Nett, die Zeichenmaschine dazu bringen, die Arbeit zu erledigen.
XNOR
2

Haskell - 233 127

Verwendung von Kreuzprodukten wie hier beschrieben :

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

Vorherige Lösung implementiert unter Verwendung von Schwerpunktkoordinaten und den in dieser Stack Exchange- Antwort beschriebenen Formeln :

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)

Beide Funktionen gund hnehmen vier Paare auf, von denen das erste der Punkt ist, der auf Einschluss geprüft werden soll, und der Rest die Koordinaten der Eckpunkte des Dreiecks sind.

So testen Sie mit der Beispieleingabe:

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]

Ungolfed-Lösungen:

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
quelle
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

Direkt von meiner Antwort auf diese andere Frage kopiert

Test In FireFox / Firebug - Konsole

Ausgang alle 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)
]

Output alle 0s

;[
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
quelle
2

SmileBASIC, 111 100 Zeichen

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

Zeichnet ein Dreieck und überprüft die Farbe des Pixels am Punkt. Das Dreieck wird 99999x vergrößert und so verschoben, dass der zu überprüfende Punkt vor dem Zeichnen bei (0,0) liegt, um Genauigkeitsverluste zu minimieren.

12Me21
quelle
2

Intel 8087 FPU-Baugruppe, 222 220 Bytes

Verwendet nur die 8087-FPU-Hardware zur Berechnung. Hier ist die nicht zusammengebaute (auch in diesem Fall nicht bespielte) Version als MAKRO (erspart Ihnen die 220 Hex-Byte-Codes):

; 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

Erläuterung

Verwendet das Ermitteln, um die Fläche des ABC-Dreiecks zu berechnen, und dann das Dreieck, das aus dem X-Punkt und zwei weiteren Punkten des ABC-Dreiecks gebildet wird. Wenn die Fläche des Dreiecks ABC der Summe der Flächen der Dreiecke XBC + AXC + ABX entspricht, liegt der Punkt innerhalb des Dreiecks. Das Ergebnis wird als ZF zurückgegeben.

Was ist daran schön?

Alle mathematischen Operationen und Gleitkommaoperationen werden in Hardware mit einer erweiterten Genauigkeit von 80 Bit ausgeführt. Der endgültige Fließkommavergleich wird ebenfalls in Hardware durchgeführt und ist daher sehr genau.

Dies verwendet auch alle acht Stapelregister des 8087 auf einmal.

Was ist nicht ganz so ordentlich daran

Da die Punkte des Dreiecks während der Berechnung mehrmals in die Formeln eingefügt werden müssen, muss jede Variable im Speicher nacheinander in der richtigen Reihenfolge in die Stapelregister der FPU geladen werden. Dies kann zwar relativ einfach wie eine Funktion als MAKRO modelliert werden, bedeutet jedoch, dass der Code bei jeder Assembly erweitert wird, wodurch redundanter Code erstellt wird. 41 Bytes wurden gespart, indem einige der gleichen wiederholten Codesegmente in PROCs verschoben wurden. Allerdings ist der Code dadurch weniger lesbar, weshalb die obige Auflistung nicht vorhanden ist (weshalb sie als "ungolfed" gekennzeichnet ist).

Tests

Hier ist ein Testprogramm unter Verwendung von IBM DOS, das die Ausgabe zeigt:

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,'$'

Ausgabe

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
quelle
1

C 414 (war 465)

Golf gespielt

#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");}

Ursprüngliche Funktionsdeklaration zur Erklärung hinzugefügt

/**
* 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);

Als benannte Funktion umgeschrieben: Eingabe über stdin jeweils eine Zeile oder alle in einer Zeile durch Leerzeichen getrennt.

#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
quelle
3
Sie können einige Bytes einsparen, indem Sie Zeilenumbrüche und unnötige Leerzeichen entfernen. Außerdem haben Sie doubleneu definiert, Daber Sie verwenden immer noch doubleim Code.
Gronostaj
1

Java, 149 Zeichen

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;

Schrecklich, wenn ich bedenke, dass ich "Mathe" schreiben muss. jedes Mal. Dies ist das eigentliche Programm:

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));
}
}

wobei a das x von Punkt a ist, b das x von Punkt b ist, c für x von c ist, d y von a ist, e y von b ist, f das y von c ist und x und y das x und sind y des Punktes. Der Boolesche Wert k bestimmt, ob er wahr ist oder nicht.

colorado777
quelle
1
Wofür sind die 100*?
XNOR
1

JavaScript 125/198

Wenn Punkte in 8 Argumenten angegeben werden:

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}

Wenn Punkte in einem zweidimensionalen Array bereitgestellt werden:

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}}

Dieser Code verwendet keine dieser ausgefallenen Vektor-Mathematik. Stattdessen wird nur ein einfacher Algebra-Trick verwendet, um festzustellen, ob sich der Punkt innerhalb des Dreiecks befindet oder nicht. Die Formel:

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

was sagt, dass sich der Punkt auf welcher Seite einer Linie befindet , ergibt sich aus der Neuordnung der Definition der Neigung:

            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)

Wenn wir alle drei Seiten testen, sollten alle drei nur dann Zahlen mit demselben Vorzeichen ergeben, wenn sich der Punkt innerhalb des Dreiecks befindet, da wir ihn um das Dreieck testen. Wenn der Punkt auf einer Seite liegt, sollte einer der Tests 0 zurückgeben.

Testcode für 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
}

Bei der Konvertierung in CoffeeScript werden 97 Zeichen (ohne Leerzeichen oder Tabulatoren) gezählt:

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 Zeichen bei Konvertierung in 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 朕 朕 會
quelle
Das ist die "ausgefallene Vektormathematik", die ich verwende: D (nicht die ausgefallene baryzentrische Koordinatenmethode, die einige andere gewählt haben). Wie bei der Antwort, die am häufigsten gewählt wurde, können Sie mit ES6 einige Bytes einsparen und die Funktionen wie definieren d=(x,y,...)=>{...}. In Ihrem Fall können Sie noch mehr sparen, indem Sie CoffeeScript verwenden, was nicht erforderlich ist return: pastebin.com/RVFk1D5k ... und in jedem Fall können Sie ein Byte sparen, indem Sie <1anstelle von verwenden ==0.
Martin Ender
@ m.buettner: o Ich dachte, die Gleichung, die ich verwendet habe, habe nichts mit Vektoren zu tun (abgeleitet von der einfachen Algebra), aber anscheinend ergeben beide dieselbe Gleichung. Mathe ist wunderbar.
Derek 朕 朕 功夫
1

R 23

Inspiriert von MATLAB ,

SDMTools::pnt.in.poly()

heißt wie SDMTools::pnt.in.poly(point,triangle)wo pointist ein Vektor der Länge 2 und triangleist eine 3x2 Matrix von Eckpunkten. SDMTools ist auf CRAN verfügbar.

Shadowtalker
quelle
1

Mathematica, 38 Zeichen

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

Beispiel:

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

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

(* Wahr *)

David G. Stork
quelle
Es ist Standard, Leerzeichen als Zeichen zu zählen, aber vermutlich können Sie sie hier entfernen, ohne dass etwas kaputt geht.
8.
1
Außerdem müssen Sie Eingaben vornehmen und Ausgaben erzeugen, anstatt vordefinierte Variablen zu verwenden. Sie können nach einigen Mathematica-Antworten suchen, um zu sehen, wie sie es tun.
8.
0

C (gcc) , 108 Bytes

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;}

Probieren Sie es online!

Nimmt drei Kreuzprodukte und kehrt zurück, 1wenn sich das Vorzeichen der Komponente nicht ändert.

Ceilingcat
quelle