Vérifiez si le point est à l'intérieur du triangle

40

Votre objectif est de déterminer si un point 2D donné X se situe dans la zone du triangle avec les sommets A, B, C donnés.

Ecrivez une fonction qui prend les coordonnées du point de test X et des trois sommets du triangle (donc 8 coordonnées au total) et renvoie Vrai si le point se trouve à l'intérieur de ce triangle et Faux s'il se trouve à l'extérieur.

Ne vous inquiétez pas des cas de bord. Si le point se trouve sur la limite du triangle (arête ou sommet) ou si le triangle est en fait un segment de ligne, votre code peut faire n'importe quoi, y compris un crash. Ne vous inquiétez pas non plus de la stabilité numérique ou de la précision en virgule flottante.

Votre code doit être une fonction nommée. Les extraits de code ne seront pas acceptés.

Le moins de personnages gagne.

Contribution:

Huit nombres réels représentant des coordonnées. Les chiffres vont se situer dans la plage (-1,1).

Le format d'entrée exact est flexible. Vous pouvez, par exemple, prendre huit chiffres, une liste de huit chiffres, une liste de quatre points chacun donnée par un tuple, une matrice 2 * 4, quatre nombres complexes, deux listes de coordonnées x et y, etc.

L'entrée doit simplement correspondre aux numéros d'un conteneur, sans données supplémentaires. Vous ne pouvez pas utiliser l'entrée pour effectuer un prétraitement, ni imposer de contrainte à l'entrée, telle que demander que les points soient donnés en coordonnée y ascendante. Votre entrée doit autoriser huit coordonnées (bien que votre code puisse se comporter de manière arbitraire dans les cas extrêmes mentionnés précédemment).

Veuillez indiquer votre format d'entrée.

Sortie:

Soit le booléen True/ False, le numéro 1/ 0, ou les analogues de votre langue.

Cas de test

Les entrées reçoivent une liste [X,A,B,C]de quatre tuples, le point de test en premier, puis les trois sommets du triangle. Je les ai regroupés dans ceux dont les résultats devraient être Trueet ceux qui devraient être False.

True instances:

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

[(-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
la source
Quelle est votre définition d'un personnage? Ascii? Encodable en 7 bits? Dans un octet? Unicode?
isaacg
Que suggérez-vous? Il existe déjà des solutions qui utilisent du code compressé.
xnor
En général, je pense que les octets sont utilisés pour les caractères non-Ascii, car sinon, l'avantage Utf-32 est insurmontable.
isaacg
Eh bien, je ne peux pas y retourner maintenant; tout caractère Unicode est un caractère. Compresse si tu veux.
xnor

Réponses:

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}

Version ECMAScript 6 (merci m.buettner, enregistre 6 caractères)

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

Appelez-le comme tel (retourne trueou false):

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

Utilise des calculs de coordonnées barycentriques sophistiqués basés sur le code de cette réponse . Voici une version non-golfée pour votre plus grand plaisir de lecture:

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
la source
12
+1, ne serait-ce que pour les noms de paramètres!
Matt
Pourquoi devez-vous casser mon UserScript de comptage de caractères ???
kitcar2000
@ kitcar2000 qu'est-ce que tu veux dire?
Abraham
Les règles indiquent que les caractères sont comptés, pas les octets. Vous pouvez donc utiliser ceci: xem.github.io/obfuscatweet pour tenir dans 122 caractères
xem
1
Est-ce que je me trompe ou auriez-vous pu utiliser (a*(l-n)+i*(g-e)+n*e-g*l)au lieu de (-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

Ma première tentative de code-golf!

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

Prend comme entrée (x, y, t) où (x, y) est le point que nous vérifions et t est un triangle t = ((x1, y1), (x2, y2), (x3, y3)).

Explication

Je calcule les déterminants des matrices

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

Ces déterminants représentent les distances signées entre les côtés du triangle et le point (x, y). S'ils ont tous le même signe, le point se trouve du même côté de chaque ligne et est donc contenu dans le triangle.

Dans le code ci-dessus, a*y+c*b+d*x-d*a-c*y-b*xest un déterminant de l'une de ces matrices.

J'utilise le fait que True+True+True==3et False+False+False==0pour déterminer si ces déterminants ont tous le même signe.

Je me sers des index de liste négatifs de Python en utilisant à la t[-1]place de t[(i+1)%3].

Merci Peter pour l'idée d'utiliser s%3<1au lieu de s in(0,3)vérifier si s vaut 0 ou 3!

Sagemath Version

Ce n'est pas vraiment une solution différente, alors je l'inclus dans cette réponse, une solution sagemath de 80 caractères:

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

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

Alex L
la source
1
Pourrait s in (0,3)être raccourci à s%3<1?
Peter Taylor
1
L'utilisation d'indices négatifs peut être modifiée pour en économiser un: -1,0,1 ... t[i]+t[i+1]équivalent à0,1,2 ... t[i-1]+t[i]
Peter Taylor
@PeterTaylor Absolument raison! Dommage que j'ai supprimé l'espace in -1,0,1avant de lire ceci. En fait, votre chemin est plus lisible, donc je l’utiliserai quand même.
Alex L
1
Bienvenue au code golf! Vous pouvez supprimer les crochets pour la compréhension de la liste à l'intérieur du sumsi vous mettez les 0,1,2parenthèses, auquel cas un caractère en remplaçant un espace. La raison en est que Python autorise la transmission de la compréhension non encadrée dans des fonctions, mais les virgules du nuplet nu le 1,2,3confondent car il tente de les analyser en tant qu'arguments séparés.
xnor
16

Mathematica, 67 octets

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

La fonction prend deux arguments, le point Xet une liste de points {A,B,C}, désignés respectivement par #et #2. C'est si vous appelez

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

alors vous obtiendrez au #fur Xet à #2mesure {A,B,C}. (Notez qu’il existe deux autres fonctions anonymes imbriquées dans le code #et qu’elles #2ont une signification différente.)

Voici une explication de la fonction elle-même:

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

Notez que cette fonction fonctionnera réellement pour tout n-gon convexe tant que ses sommets sont donnés dans le sens horaire ou anti-horaire.

Martin Ender
la source
Ne serait-il pas plus efficace de vérifier si le produit des distances est positif que si tous les signes sont égaux? Je n'ai pas Mathematica, mais il semble que cela devrait être plus facile.
isaacg
@isaacg Il y a trois termes, donc s'ils sont tous négatifs, leur produit est négatif et s'ils sont tous positifs, leur produit est positif. Votre approche ne fonctionne que si les signes de deux nombres doivent être égaux.
Martin Ender
Pourquoi ne pas utiliser Det?
alephalpha
@alephalpha Eh bien, probablement parce que je n'y ai pas pensé. : P ... Je vais regarder dans cela
Martin Ender
@alephalpha Hm non, je ne trouve pas le moyen de construire les trois matrices requises en moins de caractères.
Martin Ender
7

CJam, 66 63 59 52 46 34 32 31 30 28 caractères

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

Après avoir transformé la chaîne Unicode, le code suivant ( 33 octets ) est évalué:

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

Attend X [A B C]comme entrée, où chaque point est de la forme [double double]. La sortie est 1 ou 0.

Essayez-le en ligne.

Un grand merci à user23013 pour avoir enregistré 6 caractères (13 octets de code non compressé)!

Cas de test

$ 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
la source
Est-ce une fonction nommée?
Martin Ender
@ m.buettner: En quelque sorte. Le wiki officiel dit ce qui suit: Block - une section de programme délimitée par {et }et traitée comme une seule unité. Similaire aux blocs de code en C / java, les blocs exceptés sont des objets de première classe et peuvent être affectés à des variables (définissant ainsi des fonctions).
Dennis
1
@xnor 1m<@m*prépare 3 paires de X et le prochain i+1sommet du triangle. @-@@-déplace le ( ith) sommet actuel vers l'origine (et inversé s'il ne l'était pas @-\@-, mais cela n'a pas d'importance). @@*@@*>calcule l'axe z du produit croisé, dit déterminant, et retourne 1s'il est négatif. :+3%!renvoie si elles sont toutes identiques, c'est-à-dire que les 3 sont négatives ou non négatives, ce qui signifie positives sauf pour les cas extrêmes. Je pense qu'il est plus difficile de lire CJam que de jouer au golf.
jimmy23013
1
37 Octets {[_1m<\]z\f{f{+~@-@@-}~@@*@@*>})-!}:T. Utilisez 2m>ou Wm<pour la sécurité Unicode.
jimmy23013
1
33 octets:{2*2/\f{f{+~@-@@-}~@@*@@*>})-!}:T
jimmy23013
5

C - 156 octets

Les entrées sont un tableau de 3 flottants dans X, 3 flotteurs dans Y et de séparer x et y pour le point de test. Bonus: gère tous les cas!

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

Adapté de PNPOLY.


la source
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 - testé en javascript
bebe
@bebe - Cela provoque une erreur de syntaxe.
Derek k 會 功夫
Cela ne provoque pas d' erreur de syntaxe.
bebe
4

Pyth 1.0.5 , 57 54 51

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

Définit la fonction g, qui prend deux entrées: le point de test, puis la liste des sommets du triangle. Sorties Trueet False. Remarque: détruit l'entrée, en particulier b, la liste des sommets du triangle.

Essayez ici . Les derniers caractères gvwvwappellent la fonction avec un scénario de test sur les deux lignes suivantes.

Basé sur cet algorithme

Explication:

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)

La guerre CJam - Pyth continue!

isaacg
la source
Cela devrait être une fonction nommée. Est-ce que wprendre l'entrée STDIN?
xnor
@xnor Oups, j'ai raté cette partie de la description. Va éditer.
isaacg
@xnor Les fonctions qui affichent la réponse sont-elles autorisées ou doivent-elles renvoyer la réponse? Actuellement, ceci affiche la réponse, mais je pourrais le renvoyer pour un caractère supplémentaire.
isaacg
Renvoie la réponse.
xnor
Pouvez-vous peut-être sauvegarder des personnages en remplaçant le compteur Zpar un ensemble vide avec lequel vous vous êtes accumulé Z|=, puis en tester la longueur pour voir s'il ne s'agit que 0de ou 1ont été vus? La stratégie s'est avérée plus longue en Python, mais peut-être que ça vaut la peine d'utiliser des primitives Pyth.
xnor
4

J 64 45 (42 sans affectation)

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

L'affectation n'est pas nécessaire pour que la chose soit une fonction, il est donc incertain de la compter ou non. Profitant de l'entrée flexible: j'aimerais avoir un tableau de (1 + nombre de sommets) x (dimensionnalité de l'espace).

En espérant marquer quelques points supplémentaires ici ...: Cette chose fonctionne pour toutes les dimensions du simplexe, pas seulement les triangles dans un plan, mais également une pyramide à 3 faces dans un espace 3D, etc. Cela fonctionne également lorsque le nombre de sommets du simplex est inférieur à (n + 1), puis il calcule si la projection du point sur le simplex est à l'intérieur ou non.

Il convertit en coordonnées barycentriques , puis vérifie les négatives, indiquant que le point est à l'extérieur. Ne pense pas que J utilise _ pour négatif

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

Une analyse des exemples donnés:

   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
la source
J'ai demandé une fonction nommée, donc les caractères d'attribution comptent. Voici quelques points pour généraliser aux polygones! ······
xnor le
En fait, je ne généralise pas tout à fait les polygones, mais les simplexes à N dimensions, avec des N+1sommets maximum . Par exemple, une pyramide à 4 sommets dans un espace à trois dimensions ou un simplex à cinq sommets dans un espace à quatre dimensions. Le nombre de sommets peut être inférieur à N+1. Dans ce cas, l'algorithme détermine si la projection orthogonale sur l'hyperplan du simplex réside ou non dans le simplex (par exemple, un simplex à 2 points en 2D sera projeté sur la ligne et coché). si cette projection se situe entre les points finaux)
jpjacobs
4

HTML5 + JS, 13b + 146b / 141b / 114 caractères

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

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

ou ES6 unicode-obscurci (114 caractères):

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

démo: http://jsfiddle.net/xH8mV/

Obfuscation Unicode réalisée avec: http://xem.github.io/obfuscatweet/

xem
la source
Il ne semble pas que le résultat soit correct lorsque le point est proche du côté: jsfiddle.net/L2B2A Je pense que cela est dû au fait que toutes les entrées sont comprises entre (-1,1) et que votre code ne teste que les 4 pixels autour l'origine.
Derek 會 功夫
c'est vrai, pour adapter les exemples, je devrais changer l'origine et l'échelle de ma toile pour gérer les triangles à l'intérieur de [-1,1]. Mais pourquoi ces triangles sont-ils si petits de toute façon?
xem
le problème dit que tous les xy sont compris entre -1 et 1. Je ne sais pas vraiment pourquoi, mais je pense que vous pouvez simplement multiplier chaque entrée par 1e7 (pour maintenir la précision), vous pouvez obtenir le résultat correct: D
Derek 會 會 功夫
Une solution graphique, très astucieuse!
xnor
3

Python (65)

Les gens semblent avoir fini de soumettre, alors je vais poster ma propre solution à ma question.

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

Xest le nombre complexe représentant les points de test et Lest une liste de trois points, chacun étant un nombre complexe.

Premièrement, je vais expliquer une version moins codée du code;

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)

Nous décalons les points A,B,C,Xpour qu'ils Xsoient à l'origine, tirant parti de l'arithmétique complexe intégrée de Python. Nous devons vérifier si l’origine est contenue dans la coque convexe de A,B,C. Cela équivaut à l'origine se trouvant toujours du même côté (gauche ou droite) des segments AB, BC et AC.

Un segment ABa l'origine sur la gauche si l'on se déplace dans le sens anti-horaire de moins de 180 degrés pour aller de A à B, et sur la droite sinon. Si nous considérons les angles a, bet ccorrespondant à ces points, cela signifie b-a < 180 degrees(angles pris dans la plage de 0 à 360 degrés). Comme nombres complexes, angle(B/A)=angle(B)/angle(A). Aussi, angle(x) < 180 degreesexactement pour le point dans le demi-plan supérieur, que nous vérifions via imag(x)>0.

Ainsi, l’origine à gauche de AB est exprimée par (A/B).imag>0. En vérifiant si elles sont toutes égales pour chaque paire cyclique en A,B,Cnous indique si le triangle ABCcontient l'origine.

Revenons maintenant au code entièrement joué au golf

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

Nous générons chaque paire cyclique dans (A-X,B-X,C-X)=(L[0]-X,L[1]-X,L[2]-X), en tirant parti des indices de liste Python négatifs qui enveloppent ( L[-1]= L[2]). Pour vérifier que les Bools sont all True( 1) ou all False( 0), nous les ajoutons et vérifions la divisibilité par 3, à l'instar de nombreuses solutions.

Xnor
la source
2

Fortran - 232 218 195 174

C'est affreux. La fonction est épouvantable à cause du fait que les données lui sont transmises et nous ne pouvons pas le prétraiter.

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

La diminution de 14 caractères est due au fait que j'ai oublié de jouer au golf le nom de la fonction de mes tests. La diminution supplémentaire est due au typage implicite et à l’oubli du changement du nom de la fonction. Les 20 caractères suivants ont été supprimés suite à la lecture des points sous forme de tableau unique. Le programme complet est

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
la source
1
Vous pouvez le rendre un peu plus court en vous appuyant sur le typage implicite de Fortran et en utilisant un seul tableau d'entrées contenant les 8 nombres: 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);endj'ai essayé de le raccourcir davantage en utilisant des opérations de liste, mais malheureusement, cela n'a pas très bien fonctionné.
Ventero
1
Encore plus court en éliminant les sous-expressions plus courantes: 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);endj'espère ne pas avoir commis d'erreur dans les transformations! Bien qu'il semble que votre code d'origine ne passe pas tous les tests.
Ventero
@Ventero: Je ne peux pas croire que j'ai oublié d'abuser de la frappe implicite :(. Merci pour votre aide!
Kyle Kanos
@ Ventero: En outre, il semble que ma réponse dépend de l'orientation du triangle. Le premier Trueexemple dans OP donne Falsesi je permute Bavec Cles valeurs de tout en donnant Truepour l’orientation originale.
Kyle Kanos
Ah, en effet, le problème vient de (réutiliser la notation de mon commentaire précédent) a < 0, ce qui inverse la condition que vous devez tester. Malheureusement, cela ne peut pas simplement être corrigé en enveloppant le tout dans un abs, comme dans le cas de la condition implicite, bet en dayant le même signe que celui qui aest perdu. Cela peut être corrigé en utilisant quelque chose comme (encore une fois, en réutilisant la notation et les variables prédéfinies de mon dernier commentaire) 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)- ce qui peut probablement être joué davantage au golf.
Ventero
2

MATLAB: 9!

Pas beaucoup de moi pour écrire ici

inpolygon

Peut être appelé comme suit:

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

La sortie est affectée à une variable nommée ans


Si je devais écrire une fonction, ce pourrait être quelque chose comme ça, pourrait probablement être optimisé:

function y=f(a,b,c,d)
inpolygon(a,b,c,d)
Dennis Jaheruddin
la source
2
peut être plus court en utilisant une poignée de fonction: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]);}

Probablement pas aussi efficace en caractères qu'une méthode mathématique, mais c'est une utilisation amusante des bibliothèques. Incidemment, aussi plutôt lent.

Tirez également parti de "Ne vous inquiétez pas non plus de la stabilité numérique ou de la précision en virgule flottante." - malheureusement, GraphicsPathutilise ints en interne, donc une valeur dans la plage -1 <f <1 ne peut avoir que trois valeurs possibles. Comme les flotteurs n'ont que 7 chiffres de précision, je multiplie simplement par 1e7 pour les transformer en nombres entiers. Hm, je suppose que ce n'est pas vraiment perdre toute précision. C'est aussi exploitable d'une autre manière: j'aurais probablement pu profiter d'ignorer la précision et simplement donner la "mauvaise" réponse.

Si je suis autorisé à ignorer le coût en caractères d'importation de bibliothèques, 149 (à tout le moins, System.Linqet System.Drawingsont assez standard sur la plupart des projets WinForms, mais System.Drawing.Drawing2Dpeut être un peu exagéré):

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

Programme de test (oui, c'est moche):

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
la source
Mignon, obtenir le moteur de dessin pour faire le travail.
xnor
2

Haskell - 233 127

Utilisation de produits croisés comme décrit ici :

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

Solution précédente mise en œuvre à l'aide de coordonnées barycentriques et des formules décrites dans cette réponse 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)

Les deux fonctions get hprennent quatre paires, la première est le point à tester pour l'inclusion et le reste étant les coordonnées des sommets du triangle.

Pour tester avec l'entrée d'exemple:

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]

Solutions non-golfées:

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

Directement copié de ma réponse à Cette autre question

Test dans la console FireFox / FireBug

Sortie tous les 1

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

Sortir tous les 0

;[
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
la source
2

SmileBASIC, 111 100 caractères

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

Dessine un triangle et vérifie la couleur du pixel au point. Le triangle est redimensionné à 99999x et décalé de manière à ce que le point à vérifier soit à (0,0) avant d'être tracé, afin de minimiser la perte de précision.

12Me21
la source
2

Assemblage Intel 8087 FPU, 222 220 octets

Utilise uniquement le matériel 8087 FPU à calculer. Voici la version non assemblée (ungolfed dans ce cas aussi) en tant que MACRO (vous épargnera les codes à 220 octets):

; 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

Explication

Utilise le déterminé pour calculer l'aire du triangle ABC, puis le triangle formé avec le point X et deux autres points du triangle ABC. Si l'aire du triangle ABC est égale à la somme des aires des triangles XBC + AXC + ABX, alors le point est dans le triangle. Le résultat est renvoyé sous forme de ZF.

Qu'est-ce qui est chouette

Toutes les opérations mathématiques et à virgule flottante sont effectuées de manière matérielle avec une précision étendue de 80 bits. La comparaison finale en virgule flottante est également effectuée dans le matériel, elle sera donc très précise.

Cela utilise également les huit registres de pile du 8087 en même temps.

Qu'est-ce qui n'est pas aussi net dans cette affaire?

Comme les points du triangle doivent être rebranchés à plusieurs reprises dans les formules pendant le calcul, il faut que chaque variable en mémoire soit chargée dans les registres de pile de la FPU, l'un après l'autre, dans le bon ordre. Bien que cela puisse être assez facilement modélisé comme une fonction en tant que MACRO, cela signifie que le code est développé à chaque assemblage, créant ainsi un code redondant. 41 octets ont été sauvegardés en déplaçant certains des mêmes segments de code répétés dans PROCs. Cependant, cela rend le code moins lisible, donc la liste ci-dessus est sans lui (c'est pourquoi il est étiqueté comme "non golfé").

Des tests

Voici un programme de test utilisant IBM DOS montrant la sortie:

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

Sortie

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 Ko
la source
1

C 414 (était 465)

Golfé

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

Déclaration de fonction originale ajoutée pour l'explication

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

Réécrit comme une fonction nommée: saisissez via stdin une ligne ou toutes les lignes en une ligne séparées par des espaces.

#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
la source
3
Vous pouvez économiser des octets en vous débarrassant des nouvelles lignes et des espaces inutiles. En outre, vous avez doubleredéfini comme Dmais vous utilisez toujours doubledans le code.
gronostaj
1

Java, 149 caractères

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;

Horrible vu que je dois écrire "Math". à chaque fois. Voici le programme actuel:

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

où a est le x du point a, b est le x du point b, c pour x de c, d est y de a, e est y de b, f est le y de c, et x et y sont les x et y du point. Le booléen k détermine si c'est vrai ou pas.

colorado777
la source
1
Quels sont les 100*pour?
xnor
1

JavaScript 125/198

Si les points sont fournis dans 8 arguments:

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}

Si des points sont fournis dans un tableau à 2 dimensions:

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

Ce code n'utilise aucun de ces mathématiques vectorielles fantaisie. Au lieu de cela, il n’utilise qu’une simple astuce algébrique pour déterminer si le point est à l’intérieur du triangle ou non. La formule:

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

qui dit que le point est de quel côté d'une ligne , est dérivé de la réorganisation de la définition de la pente:

            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)

Si nous testons les 3 côtés, tous les 3 devraient donner des nombres avec le même signe que lorsque le point est à l'intérieur du triangle, car nous le testons tout autour du triangle. Si le point est d'un côté, l'un des tests doit renvoyer 0.

Code de test 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
}

Si 97 caractères (sans compter les espaces et les tabulations) sont convertis en 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 caractères si convertis en 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 會 功夫
la source
C'est la « fantaisie mathématiques vecteur » J'utilise: D (pas la fantaisie coordonnée barycentrique approche quelques autres ont, cependant). Comme la réponse la plus votée, vous pouvez économiser quelques octets en utilisant ES6 et en définissant les fonctions comme d=(x,y,...)=>{...}. Dans votre cas, vous pouvez économiser encore plus en utilisant CoffeeScript, qui n'a pas besoin de return: pastebin.com/RVFk1D5k ... et dans tous les cas, vous pouvez enregistrer un octet en utilisant à la <1place de ==0.
Martin Ender
@ m.buettner: o Je pensais que l'équation que j'avais utilisée n'avait rien à voir avec des vecteurs (dérivés de l'algèbre simple), mais apparemment, ils donnent la même équation. Les maths sont merveilleux.
Derek k 會 功夫
1

R, 23

Inspiré par MATLAB ,

SDMTools::pnt.in.poly()

appelé comme SDMTools::pnt.in.poly(point,triangle)pointest un vecteur de longueur 2 et triangleest une matrice de sommets 3x2. SDMTools est disponible sur CRAN.

shadowtalker
la source
1

Mathematica, 38 caractères

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

Exemple:

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

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

(* Vrai *)

David G. Stork
la source
Il est standard de compter les espaces en tant que caractères, mais ici, vous pouvez probablement les supprimer sans que rien ne se casse.
XNOR
1
En outre, vous devez prendre des entrées et produire des sorties plutôt que d'utiliser des variables prédéfinies. Vous pouvez rechercher certaines réponses de Mathematica pour voir comment elles le font.
XNOR
0

C (gcc) , 108 octets

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

Essayez-le en ligne!

Prend trois produits croisés et renvoie 1si le signe du composant ne change pas.

plafondcat
la source