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
/ 0
o 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 True
y 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)]
Respuestas:
Javascript / ECMAScript 6,
161159158/152Javascript:
Versión ECMAScript 6 (gracias m.buettner, guarda 6 caracteres)
Llámalo como tal (devoluciones
true
ofalse
):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:
fuente
(a*(l-n)+i*(g-e)+n*e-g*l)
lugar de(-g*l+a*(-n+l)+i*(g-e)+n*e)
?Python 2.7
1281271171101091039995949190Mi primer intento de código de golf!
Código
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.
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*x
es un determinante de una de estas matrices.Estoy usando el hecho de que
True+True+True==3
yFalse+False+False==0
para determinar si todos estos determinantes tienen el mismo signo.Hago uso de los índices de lista negativa de Python usando en
t[-1]
lugar det[(i+1)%3]
.¡Gracias Peter por la idea de usar en
s%3<1
lugar des 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:
donde
p=[x,y]
yt=[[x1,y1],[x2,y2],[x3,y3]]
fuente
s in (0,3)
acortarse as%3<1
?-1,0,1 ... t[i]+t[i+1]
es equivalente a0,1,2 ... t[i-1]+t[i]
in -1,0,1
antes de leer esto. En realidad, tu camino es más legible, así que lo usaré de todos modos.sum
si encierra los0,1,2
paré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 la1,2,3
confunden porque intenta analizarlos como argumentos separados.Mathematica, 67 bytes
La función toma dos argumentos, el punto
X
y una lista de puntos{A,B,C}
, a los que se hace referencia como#
y#2
respectivamente. Eso es si llamasentonces obtendrás
#
asX
y#2
as{A,B,C}
. (Tenga en cuenta que hay otras dos funciones anónimas anidadas dentro del código:#
y#2
tienen un significado diferente dentro de ellas).Aquí hay una explicación de la función en sí:
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.
fuente
Det
?CJam,
66635952463432313028 caracteresDespués de transformar la cadena Unicode, se evalúa el siguiente código ( 33 bytes ):
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
fuente
{
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).1m<@m*
prepara 3 pares de X y el siguiente (i+1
th) vértice del triángulo.@-@@-
mueve eli
vé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 devuelve1
si 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.{[_1m<\]z\f{f{+~@-@@-}~@@*@@*>})-!}:T
. Uso2m>
oWm<
para seguridad Unicode.{2*2/\f{f{+~@-@@-}~@@*@@*>})-!}:T
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!
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 javascriptPyth 1.0.5 ,
575451Define la función g, que toma dos entradas: el punto de prueba y luego la lista de los vértices del triángulo. Salidas
True
yFalse
. Nota: Destruye la entrada, específicamente b, la lista de los vértices del triángulo.Probarlo aquí . Los últimos caracteres
gvwvw
llaman a la función con un caso de prueba en las siguientes dos líneas.Basado en este algoritmo
Explicación:
The CJam - ¡La guerra de Pyth continúa!
fuente
w
tomando entrada STDIN?Z
con un conjunto vacío con el que acumulaZ|=
, luego pruebe su longitud para ver si solo se vieron0
o1
se vieron? La estrategia resultó más larga en Python, pero quizás valga la pena usar primitivas Pyth.J
6445 (42 sin asignación)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
Una carrera en los ejemplos dados:
fuente
N+1
vé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 queN+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)HTML5 + JS, 13b + 146b / 141b / 114 caracteres
HTML:
JS (146b):
o ES6 (141b):
o ES6 unicode-ofuscado (114 caracteres):
demostración: http://jsfiddle.net/xH8mV/
Ofuscación Unicode realizada con: http://xem.github.io/obfuscatweet/
fuente
Pitón (65)
La gente parece haber terminado de enviar, así que publicaré mi propia solución a mi pregunta.
X
es el número complejo que representa los puntos de prueba, yL
es una lista de tres puntos, cada uno un número complejo.Primero, explicaré una versión menos codificada del código;
Cambiamos los puntos
A,B,C,X
para queX
estén en el origen, aprovechando la aritmética compleja incorporada de Python. Necesitamos verificar si el origen está contenido en el casco convexo deA,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
AB
tiene 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 ángulosa
,b
yc
correspondientes a estos puntos, esto significab-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 degrees
exactamente 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 enA,B,C
nos dice si el triánguloABC
contiene el origen.Ahora, volvamos al código totalmente golfizado.
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 allTrue
(1
) o allFalse
(0
), los agregamos y verificamos la divisibilidad entre 3, como lo hicieron muchas soluciones.fuente
Fortran -
232218195174Malditamente horrible. La función es horrenda debido al requisito de que los datos se le pasen y no podamos preprocesarlos.
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
fuente
logical function T(x);real x(8);p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3);s=x(6)-x(4);u=x(7)-x(3);v=x(8)-x(4);o=r*v-u*s;T=ALL([p*(s-v)+q*(u-r)+o,p*v-q*u,q*r-p*s]>=o);end
he intentado acortar esto aún más mediante el uso de operaciones de lista, pero desafortunadamente eso no funcionó muy bien.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.True
ejemplo en OP daFalse
si cambiaréB
yC
valores 's mientras que daTrue
para la orientación original.a < 0
, que invierte efectivamente la condición que tiene que probar. Desafortunadamente, esto no se puede solucionar envolviendo todo en unaabs
, ya que la condición implícita deb
yd
con el mismo signoa
se 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.MATLAB: 9!
No mucho de mí para escribir aquí
Se puede llamar así:
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:
fuente
f=@(a,b,c,d)inpolygon(a,b,c,d)
C # 218 (149?)
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,
GraphicsPath
usaint
s 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.Linq
ySystem.Drawing
son bastante estándar en la mayoría de los proyectos de WinForms, peroSystem.Drawing.Drawing2D
pueden ser un poco exagerados):Programa de prueba (sí, es feo):
fuente
Haskell -
233127Usando productos cruzados como se describe aquí :
Solución anterior implementada usando coordenadas barcéntricas y las fórmulas descritas en esta respuesta de Stack Exchange :
Ambas funciones
g
yh
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:
Soluciones sin golf:
fuente
JavaScript (ES6) 120
Copiado directamente de mi respuesta a esta otra pregunta
Prueba en la consola FireFox / FireBug
Salida todos los 1s
Salida de todos los 0s
fuente
SmileBASIC,
111100 caracteresDibuja 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.
fuente
Ensamblaje Intel 8087 FPU,
222220 bytesUtiliza 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):
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:
Salida
fuente
C 414 (antes 465)
Golfed
Declaración de función original agregada para explicación
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.
fuente
double
redefinido comoD
pero todavía lo usadouble
en el código.Java, 149 caracteres
Horrible teniendo en cuenta que tengo que escribir "Matemáticas". cada vez. Este es el programa real:
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.
fuente
100*
?JavaScript 125/198
Si se proporcionan puntos en 8 argumentos:
Si los puntos se proporcionan en una matriz bidimensional:
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:
que dice que el punto está en qué lado de una línea , se deriva de reorganizar la definición de pendiente:
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/
97 caracteres (sin contar espacios ni pestañas) cuentan si se convierten en CoffeeScript:
115 caracteres si se convierten en ES6:
fuente
d=(x,y,...)=>{...}
. En su caso, puede ahorrar aún más utilizando CoffeeScript, que no necesitareturn
: pastebin.com/RVFk1D5k ... y, en cualquier caso, puede guardar un byte utilizando en<1
lugar de==0
.R, 23
Inspirado por MATLAB ,
llamado como
SDMTools::pnt.in.poly(point,triangle)
dondepoint
es un vector de longitud 2 ytriangle
es una matriz de vértices de 3x2. SDMTools está disponible en CRAN.fuente
Mathematica, 38 caracteres
Ejemplo:
(* Cierto *)
fuente
C (gcc) , 108 bytes
Pruébalo en línea!
Toma tres productos cruzados y devuelve
1
si el signo delk̂
componente no cambia.fuente