Compruebe si el punto se encuentra dentro del triángulo

40

Su objetivo es determinar si un determinado punto 2D X se encuentra dentro del área del triángulo con vértices dados A, B, C.

Escriba una función que tome las coordenadas del punto de prueba X y los tres vértices del triángulo (de modo que sea un total de 8 coordenadas) y devuelva Verdadero si el punto se encuentra dentro de ese triángulo y Falso si se encuentra afuera.

No te preocupes por los casos extremos. Si el punto se encuentra en el límite del triángulo (borde o vértice) o el triángulo es en realidad un segmento de línea, su código puede hacer lo que sea, incluido el bloqueo. Tampoco se preocupe por la estabilidad numérica o la precisión de punto flotante.

Su código debe ser una función con nombre. No se aceptarán fragmentos de código.

Pocos personajes ganan.

Entrada:

Ocho números reales que representan coordenadas. Los números estarán en el rango (-1,1).

El formato de entrada exacto es flexible. Podría, por ejemplo, tomar ocho números, una lista de ocho números, una lista de cuatro puntos, cada uno dado por una tupla, una matriz 2 * 4, cuatro números complejos, dos listas de las coordenadas x y coordenadas y, y así.

La entrada debe ser solo los números en algún contenedor, sin datos adicionales. No puede usar la entrada para hacer ningún preprocesamiento, ni puede requerir restricciones en la entrada, como exigir que los puntos se den en coordenada y ascendente. Su entrada debe permitir ocho coordenadas (aunque su código puede comportarse arbitrariamente en los casos límite mencionados anteriormente).

Por favor, indique su formato de entrada.

Salida:

El booleano True/ correspondiente False, el número correspondiente 1/ 0o los análogos en su idioma.

Casos de prueba

Las entradas reciben una lista [X,A,B,C]de cuatro tuplas, primero el punto de prueba y luego los tres vértices triangulares. Los he agrupado en aquellos cuyos resultados deberían ser Truey aquellos que deberían ser False.

True instancias:

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

[(-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
fuente
¿Cuál es tu definición de personaje? Ascii? Codificable en 7 bits? En un byte? Cualquier Unicode?
isaacg
¿Que sugieres? Ya hay soluciones que usan código comprimido.
xnor
Por lo general, creo que los bytes se usan para caracteres que no son Ascii, porque de lo contrario la ventaja Utf-32 es insuperable.
isaacg
Bueno, no puedo volver ahora; cualquier personaje Unicode es un personaje. Comprime si quieres.
xnor

Respuestas:

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}

Versión ECMAScript 6 (gracias m.buettner, guarda 6 caracteres)

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

Llámalo como tal (devoluciones trueo false):

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

Utiliza algunas matemáticas de coordenadas barcéntricas elegantes basadas en el código de esta respuesta . A continuación se presenta una versión sin golf para su disfrute de lectura:

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;
}
Abrahán
fuente
12
+1, ¡aunque solo sea para los nombres de los parámetros!
Matt
¿Por qué tienes que romper mi UserScript de conteo de caracteres?
kitcar2000
@ kitcar2000 ¿qué quieres decir?
Abraham
Las reglas dicen que los caracteres se cuentan, no los bytes. Entonces puede usar esto: xem.github.io/obfuscatweet para encajar en 122 caracteres
xem
1
¿Me equivoco, o podrías haber usado en (a*(l-n)+i*(g-e)+n*e-g*l)lugar 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

Mi primer intento de código de golf!

Código

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

Toma como entrada (x, y, t) donde (x, y) es el punto que estamos verificando y t es un triángulo t = ((x1, y1), (x2, y2), (x3, y3)).

Explicación

Estoy calculando los determinantes de las 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  |

Estos determinantes representan las distancias con signo desde los lados del triángulo hasta el punto (x, y). Si todos tienen el mismo signo, entonces el punto está en el mismo lado de cada línea y, por lo tanto, está contenido en el triángulo.

En el código anterior, a*y+c*b+d*x-d*a-c*y-b*xes un determinante de una de estas matrices.

Estoy usando el hecho de que True+True+True==3y False+False+False==0para determinar si todos estos determinantes tienen el mismo signo.

Hago uso de los índices de lista negativa de Python usando en t[-1]lugar de t[(i+1)%3].

¡Gracias Peter por la idea de usar en s%3<1lugar de s in(0,3)verificar si s es 0 o 3!

Versión Sagemath

No es realmente una solución diferente, así que la incluyo en esta respuesta, una solución de Sagemath que usa 80 caracteres:

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

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

Alex L
fuente
1
¿Podría s in (0,3)acortarse a s%3<1?
Peter Taylor
1
El uso de índices negativos se puede ajustar para salvar uno más: -1,0,1 ... t[i]+t[i+1]es equivalente a0,1,2 ... t[i-1]+t[i]
Peter Taylor
@PeterTaylor ¡Absolutamente correcto! Lástima que eliminé el espacio in -1,0,1antes de leer esto. En realidad, tu camino es más legible, así que lo usaré de todos modos.
Alex L
1
Bienvenido a code golf! Puede deshacerse de los corchetes para la comprensión de la lista dentro de sumsi encierra los 0,1,2paréntesis, en cuyo caso un carácter reemplaza un espacio. La razón es que Python permite que la comprensión sin paréntesis se transmita a las funciones, pero las comas en la tupla desnuda la 1,2,3confunden porque intenta analizarlos como argumentos separados.
xnor
16

Mathematica, 67 bytes

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

La función toma dos argumentos, el punto Xy una lista de puntos {A,B,C}, a los que se hace referencia como #y #2respectivamente. Eso es si llamas

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

entonces obtendrás #as Xy #2as {A,B,C}. (Tenga en cuenta que hay otras dos funciones anónimas anidadas dentro del código:# y #2tienen un significado diferente dentro de ellas).

Aquí hay una explicación de la función en sí:

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

Tenga en cuenta que esta función realmente funcionará para cualquier n-gon convexo siempre que sus vértices se den en sentido horario o antihorario.

Martin Ender
fuente
¿No sería más eficiente verificar si el producto de las distancias es positivo que si todos los signos son iguales? No tengo Mathematica, pero parece que eso debería ser más fácil.
isaacg
@isaacg Hay tres términos, por lo que si todos son negativos, su producto es negativo y si todos son positivos, su producto es positivo. Su enfoque solo funciona si los signos de dos números son iguales.
Martin Ender
¿Por qué no usar Det?
alephalpha
@alephalpha Bueno, probablemente porque no lo pensé. : P ... Lo investigaré
Martin Ender
@alephalpha Hm no, no puedo encontrar una manera en este momento para construir las tres matrices requeridas en menos caracteres.
Martin Ender
7

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

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

Después de transformar la cadena Unicode, se evalúa el siguiente código ( 33 bytes ):

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

Espera X [A B C]como entrada, donde cada punto tiene la forma[double double] . La salida es 1 o 0.

Pruébalo en línea.

Un gran agradecimiento para user23013 por guardar 6 caracteres (13 bytes de código sin comprimir)!

Casos de prueba

$ 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
fuente
¿Es esa una función con nombre?
Martin Ender
@ m.buettner: más o menos. La wiki oficial dice lo siguiente: Bloque: una sección del programa delimitada por {y }y tratada como una sola unidad. Similar a los bloques de código en C / java, excepto que los bloques son objetos de primera clase y pueden asignarse a variables (definiendo así funciones).
Dennis
1
@xnor 1m<@m*prepara 3 pares de X y el siguiente ( i+1th) vértice del triángulo. @-@@-mueve el ivértice actual ( th) al origen (y se refleja si no fue así @-\@-, pero no importa). @@*@@*>calcula el eje z del producto cruzado, también conocido como determinante, y devuelve 1si es negativo. :+3%!devuelve si son todos iguales, es decir, los 3 son negativos o no negativos, lo que significa positivo a excepción de los casos límite. Creo que es más desafiante leer CJam que jugar al golf.
jimmy23013
1
37 Bytes: {[_1m<\]z\f{f{+~@-@@-}~@@*@@*>})-!}:T. Uso 2m>o Wm<para seguridad Unicode.
jimmy23013
1
33 bytes:{2*2/\f{f{+~@-@@-}~@@*@@*>})-!}:T
jimmy23013
5

C - 156 bytes

Las entradas son un conjunto de 3 flotadores en X, 3 flotadores en Y y x e y separados para el punto de prueba. Bono: maneja todos los casos de borde!

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

Adaptado de PNPOLY.


fuente
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 - probado en javascript
bebe
@bebe: eso provoca un error de sintaxis.
Derek 朕 會 功夫
Eso no causa un error de sintaxis.
bebe
4

Pyth 1.0.5 , 57 54 51

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

Define la función g, que toma dos entradas: el punto de prueba y luego la lista de los vértices del triángulo. Salidas Truey False. Nota: Destruye la entrada, específicamente b, la lista de los vértices del triángulo.

Probarlo aquí . Los últimos caracteres gvwvwllaman a la función con un caso de prueba en las siguientes dos líneas.

Basado en este algoritmo

Explicación:

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)

The CJam - ¡La guerra de Pyth continúa!

isaacg
fuente
Esta debería ser una función con nombre. ¿Está wtomando entrada STDIN?
xnor
@xnor Vaya, me perdí esa parte de la descripción. Se editará
isaacg
@xnor ¿Están permitidas las funciones que imprimen la respuesta, o deben devolver la respuesta? Actualmente, esto imprime la respuesta, pero podría hacer que regrese por un personaje más.
isaacg
Devuelve la respuesta.
xnor
¿Puede quizás guardar caracteres reemplazando el contador Zcon un conjunto vacío con el que acumula Z|=, luego pruebe su longitud para ver si solo se vieron 0o 1se vieron? La estrategia resultó más larga en Python, pero quizás valga la pena usar primitivas Pyth.
xnor
4

J 64 45 (42 sin asignación)

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

La asignación no es necesaria para que la cosa sea una función, por lo que no está seguro de contarla o no. Aprovechando la entrada flexible: me gustaría tener una matriz de (1 + número de vértices) x (dimensionalidad del espacio).

Con la esperanza de obtener algunos puntos extra aquí ...: Esto funciona para cualquier dimensión de simplex, no solo triángulos en un plano, sino también una pirámide de 3 lados en el espacio 3d y así sucesivamente. También funciona cuando el número de vértices del símplex es menor que (n + 1), luego calcula si la proyección del punto sobre el símplex está dentro o no.

Se convierte a coordenadas barcéntricas , luego verifica las negativas, lo que indica que el punto está fuera. Tenga en cuenta que J usa _ para negativo

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

Una carrera en los ejemplos dados:

   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
fuente
Pedí una función con nombre, por lo que los caracteres de asignación cuentan. ¡Aquí hay algunos puntos para generalizar a polígonos! ······
xnor
Bueno, en realidad, no generalizo mucho a los polígonos, sino a los símplex N-dimensionales, con N+1vértices máximos . Por ejemplo, una pirámide de 4 vértices en el espacio 3-D, o un simplex de 5 vértices en el espacio 4-D. El número de vértices puede ser menor que N+1, en cuyo caso el algoritmo analiza si la proyección ortogonal en el hiperplano en el que reside el simplex se encuentra dentro del simplex o no (por ejemplo, se proyectará un simplex de 2 puntos en 2-D en la línea y se comprobará si esta proyección se encuentra entre los puntos finales)
jpjacobs
4

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

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

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

o ES6 unicode-ofuscado (114 caracteres):

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

demostración: http://jsfiddle.net/xH8mV/

Ofuscación Unicode realizada con: http://xem.github.io/obfuscatweet/

xem
fuente
No parece producir el resultado correcto cuando el punto está cerca del lado: jsfiddle.net/L2B2A Creo que esto se debe a que todas las entradas están entre (-1,1), y su código solo está probando los 4 píxeles alrededor el origen.
Derek 朕 會 功夫
así es, para ajustar los ejemplos, debería cambiar el origen y la escala de mi lienzo para manejar triángulos dentro de [-1,1]. ¿Pero por qué esos triángulos son tan pequeños de todos modos?
xem
el problema dice que todos los xy están entre -1 y 1. Realmente no sé por qué, pero creo que puede multiplicar cada entrada por 1e7 (para mantener la precisión) puede obtener el resultado correcto: D
Derek 朕 會 功夫
¡Una solución gráfica, muy inteligente!
xnor
3

Pitón (65)

La gente parece haber terminado de enviar, así que publicaré mi propia solución a mi pregunta.

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

X es el número complejo que representa los puntos de prueba, y L es una lista de tres puntos, cada uno un número complejo.

Primero, explicaré una versión menos codificada del código;

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)

Cambiamos los puntos A,B,C,Xpara que Xestén en el origen, aprovechando la aritmética compleja incorporada de Python. Necesitamos verificar si el origen está contenido en el casco convexo de A,B,C. Esto es equivalente al origen que siempre se encuentra en el mismo lado (izquierdo o derecho) de los segmentos de línea AB, BC y AC.

Un segmento ABtiene el origen a la izquierda si uno viaja en sentido antihorario menos de 180 grados para ir de A a B, y a la derecha de lo contrario. Si consideramos los ángulos a, by ccorrespondientes a estos puntos, esto significa b-a < 180 degrees(ángulos tomados en el rango de 0 a 360 grados). Como los números complejos, angle(B/A)=angle(B)/angle(A). Además, angle(x) < 180 degreesexactamente para el punto en el medio plano superior, que verificamos a través deimag(x)>0 .

Entonces, si el origen se encuentra a la izquierda de AB se expresa como (A/B).imag>0. Comprobar si todos son iguales para cada par cíclico en A,B,Cnos dice si el triángulo ABCcontiene el origen.

Ahora, volvamos al código totalmente golfizado.

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

Generamos cada par cíclico (A-X,B-X,C-X)=(L[0]-X,L[1]-X,L[2]-X), aprovechando los índices negativos de la lista de Python que se envuelven ( L[-1]= L[2]). Para verificar que los Bools son all True( 1) o all False( 0), los agregamos y verificamos la divisibilidad entre 3, como lo hicieron muchas soluciones.

xnor
fuente
2

Fortran - 232 218 195 174

Malditamente horrible. La función es horrenda debido al requisito de que los datos se le pasen y no podamos preprocesarlos.

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 disminución de 14 caracteres se debe a que olvidé jugar el nombre de la función de mis ejecuciones de prueba. La disminución adicional se debe al tipeo implícito y al olvido de cambiar el nombre de la función. Los siguientes 20 caracteres salieron debido a la lectura de los puntos como una sola matriz. El programa completo es

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
fuente
1
Puede hacer esto un poco más corto confiando en el tipeo implícito de Fortran y utilizando una sola matriz de entrada que contenga los 8 números: 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);endhe intentado acortar esto aún más mediante el uso de operaciones de lista, pero desafortunadamente eso no funcionó muy bien.
Ventero
1
Aún más corto al eliminar subexpresiones más comunes: logical function T(x);real x(8);p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3);s=x(6)-x(4);u=x(7)-x(3);v=x(8)-x(4);a=r*v-u*s;b=p*v-q*u;d=q*r-p*s;T=ALL([a-b-d,b,d]>=a);end¡espero no haber cometido ningún error en las transformaciones! Aunque parece que su código original no pasa todas las pruebas.
Ventero
@Ventero: No puedo creer que olvidé abusar de la escritura implícita :(. ¡Gracias por tu ayuda!
Kyle Kanos
@Ventero: Además, parece que mi respuesta depende de la orientación del triángulo. El primer Trueejemplo en OP da Falsesi cambiaré By Cvalores 's mientras que da Truepara la orientación original.
Kyle Kanos
Ah, de hecho, el problema es causado cuando (reutilizando la notación de mi comentario anterior) a < 0, que invierte efectivamente la condición que tiene que probar. Desafortunadamente, esto no se puede solucionar envolviendo todo en una abs, ya que la condición implícita de by dcon el mismo signo ase pierde. Esto se puede solucionar mediante el uso de algo como (de nuevo, reutilizando la notación y las variables predefinidas de mi último comentario) 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), que probablemente se pueda jugar más.
Ventero
2

MATLAB: 9!

No mucho de mí para escribir aquí

inpolygon

Se puede llamar así:

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

La salida se asigna a una variable llamada ans


Si realmente tuviera que escribir una función, podría ser algo así, probablemente podría optimizarse:

function y=f(a,b,c,d)
inpolygon(a,b,c,d)
Dennis Jaheruddin
fuente
2
puede ser más corto usando un controlador de función: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]);}

Probablemente no sea tan eficiente en caracteres como un método matemático, pero es un uso divertido de las bibliotecas. Por cierto, también bastante lento.

Aprovechando también "No se preocupe por la estabilidad numérica o la precisión de punto flotante". - desafortunadamente, GraphicsPathusa ints internamente, por lo que un valor en el rango -1 <f <1 solo puede tener tres valores posibles. Como las carrozas solo tienen 7 dígitos de precisión, simplemente multiplico por 1e7 para convertirlas en números enteros. Hm, supongo que realmente no está perdiendo precisión. También es explotable de otra manera: probablemente podría haber aprovechado el hecho de ignorar la precisión y haber dado la respuesta "incorrecta".

Si se me permite ignorar el costo de caracteres de importar bibliotecas, 149 (como mínimo, System.Linqy System.Drawingson bastante estándar en la mayoría de los proyectos de WinForms, pero System.Drawing.Drawing2Dpueden ser un poco exagerados):

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

Programa de prueba (sí, es feo):

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]);
    }
}
Mover
fuente
Lindo, conseguir que el motor de dibujo haga el trabajo.
xnor
2

Haskell - 233 127

Usando productos cruzados como se describe aquí :

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

Solución anterior implementada usando coordenadas barcéntricas y las fórmulas descritas en esta respuesta de 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)

Ambas funciones gyh toman cuatro pares, el primero de los cuales es el punto a probar para su inclusión y el resto son las coordenadas de los vértices del triángulo.

Para probar con la entrada de muestra:

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]

Soluciones sin golf:

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

Copiado directamente de mi respuesta a esta otra pregunta

Prueba en la consola FireFox / FireBug

Salida todos los 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)
]

Salida de todos los 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
fuente
2

SmileBASIC, 111 100 caracteres

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

Dibuja un triángulo y verifica el color del píxel en el punto. El triángulo se escala 99999x y se desplaza para que el punto a verificar esté en (0,0) antes de ser dibujado, para minimizar la pérdida de precisión.

12Me21
fuente
2

Ensamblaje Intel 8087 FPU, 222 220 bytes

Utiliza solo el hardware 8087 FPU para calcular. Aquí está la versión sin ensamblar (no protegida también en este caso) como MACRO (le ahorrará los 220 códigos de bytes hexadecimales):

; 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

Explicación

Utiliza el determinante para calcular el área del triángulo ABC, y luego el triángulo formado con el punto X y otros dos puntos del triángulo ABC. Si el área del triángulo ABC es igual a la suma de las áreas de los triángulos XBC + AXC + ABX, entonces el punto está dentro del triángulo. El resultado se devuelve como ZF.

¿Qué hay de bueno en esto?

Todas las operaciones matemáticas y de coma flotante se realizan en hardware con una precisión extendida de 80 bits. La comparación final de coma flotante también se realiza en hardware, por lo que será muy precisa.

Esto también usa los ocho registros de la pila del 8087 a la vez.

Lo que no es tan bueno de esto

Como los puntos del triángulo deben volver a conectarse a las fórmulas varias veces durante el cálculo, requiere que cada variable en la memoria se cargue en los registros de la pila de la FPU, uno por vez, en el orden correcto. Si bien esto puede modelarse con bastante facilidad como una función como MACRO, significa que el código se expande cada vez en el ensamblaje, creando código redundante. Se guardaron 41 bytes moviendo algunos de los mismos segmentos de código repetidos a PROC. Sin embargo, hace que el código sea menos legible, por lo que la lista anterior no tiene (por lo que está etiquetado como "sin golf").

Pruebas

Aquí hay un programa de prueba usando IBM DOS que muestra la salida:

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

Salida

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

C 414 (antes 465)

Golfed

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

Declaración de función original agregada para explicación

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

Reescrito como una función con nombre: ingrese a través de stdin una cada línea o todas en una línea separadas por espacios.

#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
fuente
3
Puede guardar algunos bytes deshaciéndose de nuevas líneas y espacios innecesarios. Además, ha doubleredefinido como Dpero todavía lo usa doubleen el código.
gronostaj
1

Java, 149 caracteres

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 teniendo en cuenta que tengo que escribir "Matemáticas". cada vez. Este es el programa real:

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

donde a es la x del punto a, b es la x del punto b, c para x de c, d es y de a, e es y de b, f es la y de c, y x e y son la x y y del punto. El k booleano determina si es verdadero o no.

colorado777
fuente
1
¿Para qué sirven 100*?
xnor
1

JavaScript 125/198

Si se proporcionan puntos en 8 argumentos:

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 los puntos se proporcionan en una matriz bidimensional:

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

Este código no usa ninguna de esas matemáticas vectoriales elegantes. En cambio, solo usa un simple truco de álgebra para determinar si el punto está dentro del triángulo o no. La formula:

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

que dice que el punto está en qué lado de una línea , se deriva de reorganizar la definición de pendiente:

            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 probamos los 3 lados, los 3 deberían arrojar algunos números con el mismo signo solo cuando el punto está dentro del triángulo ya que lo estamos probando alrededor del triángulo. Si el punto está de lado, una de las pruebas debería devolver 0.

Código de prueba jsFiddle: http://jsfiddle.net/DerekL/zEzZU/

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

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

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

97 caracteres (sin contar espacios ni pestañas) cuentan si se convierten 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 caracteres si se convierten 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 朕 會 功夫
fuente
Esa es la "matemática vectorial elegante" que estoy usando: D (sin embargo, no es el enfoque de coordenadas baricéntricas elegante que tomaron otros). Al igual que la respuesta más votada, puede guardar algunos bytes utilizando ES6 y definiendo las funciones como d=(x,y,...)=>{...}. En su caso, puede ahorrar aún más utilizando CoffeeScript, que no necesita return: pastebin.com/RVFk1D5k ... y, en cualquier caso, puede guardar un byte utilizando en <1lugar de ==0.
Martin Ender
@ m.buettner: o Pensé que la ecuación que usé no tiene nada que ver con vectores (derivados de álgebra simple) pero aparentemente ambos producen la misma ecuación. Las matemáticas son maravillosas.
Derek 朕 會 功夫
1

R, 23

Inspirado por MATLAB ,

SDMTools::pnt.in.poly()

llamado como SDMTools::pnt.in.poly(point,triangle)donde pointes un vector de longitud 2 y trianglees una matriz de vértices de 3x2. SDMTools está disponible en CRAN.

Shadowtalker
fuente
1

Mathematica, 38 caracteres

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

Ejemplo:

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

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

(* Cierto *)

David G. Stork
fuente
Es estándar contar espacios como caracteres, pero presumiblemente aquí puede eliminarlos sin que nada se rompa.
xnor
1
Además, debe tomar entrada y producir salida en lugar de usar variables predefinidas. Puede buscar algunas respuestas de Mathematica para ver cómo lo hacen.
xnor
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;}

Pruébalo en línea!

Toma tres productos cruzados y devuelve 1si el signo del componente no cambia.

techo
fuente