Antecedentes

El casco convexo de un número finito de puntos es el polígono convexo más pequeño que contiene todos los puntos, ya sea como vértices o en el interior. Para obtener más información, consulte esta pregunta en PGM que la define muy bien .

Entrada

N+1Coordenadas bidimensionales ( N >= 3) pasadas STDIN(con otras entradas de golf habituales permitidas también) en el siguiente formato (el número de decimales puede variar, pero puede suponer que sigue siendo "razonable" y cada número puede representarse como un flotador):

0.00;0.00000
1;0.00
0.000;1.0000
-1.00;1.000000

Salida

Un valor verdadero impreso en STDOUT(o equivalente) si el primer punto de la lista ( (0.00;0.00000)en el ejemplo anterior) está en el casco convexo de los otros N puntos, y un valor falso de lo contrario.

Este es el código de golf , por lo que gana la solución más corta en bytes.

• Casos de borde: puede devolver cualquier valor (pero no bloquearse) si el punto se encuentra en el borde del casco convexo (es decir, en un lado o en un vértice en la frontera exterior del casco), ya que es una probabilidad cero evento (bajo cualquier probabilidad razonable).

• Prohibido : cualquier cosa (lenguaje, operador, estructura de datos, incorporado o paquete) que existe solo para resolver problemas geométricos (por ejemplo, ConvexHull de Mathematica ). Se permiten herramientas matemáticas de propósito general (vectores, matrices, números complejos, etc.).

Pruebas

• Debería regresar TRUE: spiralTest1-TRUE , squareTest1-TRUE
• Debería regresar FALSE: spiralTest2-FALSE , squareTest2-FALSE

J 40 39 34 bytes

3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

Una función diádica anónima, tomando un punto, p , como uno de sus argumentos, y una lista de puntos, P , como el otro argumento (no importa qué argumento es cuál), y regresando 0o 1, si p está fuera o dentro del casco convexo de P , respectivamente. El punto p , y los puntos en P , se toman como números complejos.

Ejemplo

  is_inside =: 3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

  0.5j0.5  is_inside  0j0 0j1 1j0 1j1
1
  1.5j0.5  is_inside  0j0 0j1 1j0 1j1
0

o...

Python 2, función, 121 103programa completo 162

Python 3, 149 bytes

import sys,cmath as C
p,q,*P=[complex(*eval(l.replace(*";,")))for l in sys.stdin]
A=[C.phase((r-p)/(q-p+(q==p)))for r in P]
print(max(A)-min(A)>C.pi)

Toma entrada, en el mismo formato que la publicación original, a través de STDIN e imprime un valor booleano que indica si p está en el casco convexo de P

Explicación

El programa prueba si la diferencia entre los ángulos máximo y mínimo (con signo) entre cualquier punto r en P , p , y un punto arbitrario fijo q en P (solo usamos el primer punto en P ), es inferior a 180 °. En otras palabras, prueba si todos los puntos en P están contenidos en un ángulo de 180 ° o menos, alrededor de p . p está en el casco convexo de P si y solo si esta condición es falsa.

A costa de unos pocos bytes más, podemos usar un método similar que no requiere que calculemos ángulos explícitamente: tenga en cuenta que la condición anterior es equivalente a decir que p está fuera del casco convexo de P si y solo si existe una línea l a p , de modo que todos los puntos en P estén en el mismo lado de l . Si existe una línea de este tipo, también existe una línea que incide en uno (o más) de los puntos en P (podemos rotar l hasta que toque uno de los puntos en P ).

A (tentativamente) encontrar esta línea, se comienza por dejar que l sea a través de la línea P y el primer punto en P . Luego iteramos sobre el resto de los puntos en P ; si uno de los puntos está a la izquierda de l (suponemos que hay cierta direccionalidad en todo, izquierda o derecha realmente no importa), reemplazamos l con la línea que pasa por p y ese punto, y continuamos. Después de iterar sobre todo P , si (y solo si) p está fuera del casco convexo, entonces todos los puntos en P deben estar a la derecha de (o sobre) l . Verificamos que usando un segundo pase sobre los puntos en P.

Python 2, 172 bytes

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=reduce(lambda*x:x[C(*x)],P)
print any(C(l,q)for q in P)

Alternativamente, para hacer lo mismo en una sola pasada, dejar a la izquierda una realidad entre dos puntos, q y r , en P , de modo que q esté a la izquierda de r si q está a la izquierda de la línea que pasa por p y r . Tenga en cuenta que a la izquierda de es una relación de orden en P si y sólo si todos los puntos de P están en el mismo lado de algunos línea que pasa por p , es decir, si p se encuentra fuera del casco convexo de P . El procedimiento descrito anteriormente encuentra el punto mínimo en PWRT este orden, es decir, el punto "más a la izquierda" en P . En lugar de realizar dos pases, podemos encontrar el máximo (es decir, el punto "más a la derecha"), así como el mínimo, puntos en P wrt en el mismo orden en un solo pase, y verificar que el mínimo esté a la izquierda del máximo, es decir, efectivamente, que a la izquierda de es transitivo.

Esto funcionaría bien si p está fuera del casco convexo de P , en cuyo caso a la izquierda de es realmente una relación de orden, pero puede romperse cuando p está dentro del casco convexo (por ejemplo, trate de averiguar qué sucedería si nos encontramos con este algoritmo, donde los puntos de P son los vértices de un pentágono regular, corriendo hacia la izquierda, y p . es su centro) Para dar cabida, alteramos ligeramente el algoritmo: seleccionamos un punto q en P , y bisect P a lo largo de la línea que pasa por p y q (es decir, dividimos P alrededor de qwrt a la izquierda de.) Ahora tenemos una "parte izquierda" y una "parte derecha" de P , cada una contenida en un medio plano, de modo que a la izquierda de es una relación de orden en cada uno; encontramos el mínimo de la parte izquierda y el máximo de la parte derecha, y los comparamos como se describió anteriormente. Por supuesto, no tenemos que dividir físicamente P , simplemente podemos clasificar cada punto en P mientras buscamos el mínimo y el máximo, en una sola pasada.

Python 2, 194 bytes

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=r=P[0]
for q in P:
 if C(P[0],q):l=q*C(l,q)or l
 elif C(q,r):r=q
print C(l,r)

Octava, 82 72 bytes

d=dlmread(0,";");i=2:rows(d);~isna(glpk(i,[d(i,:)';~~i],[d(1,:)';1]))&&1

La idea es verificar si el programa lineal min {c'x: Ax = b, e'x = 1, x> = 0} tiene una solución, donde e es un vector de todos, las columnas de A son las coordenadas de la nube de puntos, y b es el punto de prueba, y c es arbitraria. En otras palabras, tratamos de representar b como una combinación convexa de columnas de A.

Para ejecutar el script, use octave -f script.m <input.dat

R, 207 bytes

d=read.csv(file("stdin"),F,";")
q=function(i,j,k)abs(det(as.matrix(cbind(d[c(i,j,k),],1))))
t=function(i,j,k)q(i,j,k)==q(1,i,j)+q(1,i,k)+q(1,j,k)
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

El script toma sus entradas de STDIN, por ejemplo Rscript script.R < inputFile.

Genera todos los triángulos desde los Núltimos puntos (la última línea,apply(combn(... ) y verifica si el primer punto está en el triángulo usando la tfunción.

tusa el método de área para decidir si Uestá en ABC: (escribir (ABC)para el área de ABC) Uestá en ABCiff (ABC) == (ABU) + (ACU) + (BCU). Además, las áreas se calculan utilizando la fórmula determinante (ver aquí una buena demostración de Wolfram).

Sospecho que esta solución es más propensa a errores numéricos que la otra, pero funciona en mis casos de prueba.

R, 282 bytes

d=read.csv(file("stdin"),F,";")
p=function(a,b)a[1]*b[1]+a[2]*b[2]
t=function(a,b,c){A=d[a,];
U=d[1,]-A
B=d[b,]-A
C=d[c,]-A
f=p(C,C)
g=p(B,C)
h=p(U,C)
i=p(B,B)
j=p(U,B)
k=f*i-g*g
u=i*h-g*j
v=f*j-g*h
min(u*k,v*k,k-u-v)>0}
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

El script toma sus entradas de STDIN, p. Ej. Rscript script.R < inputFile .

Genera todos los triángulos desde los Núltimos puntos (la última líneaapply(combn(... ) y verifica si el primer punto está en el triángulo usando la tfunción.

tusa el método barcéntrico para decidir si Uestá en ABC: (escribiendo XYpara el vector Xto Y) ya que (AB,AC)es una base para el plano (excepto en los casos degenerados donde A, B, C están alineados), AUpuede escribirse como AU = u.AB + v.ACy Uestá en el triángulo iff u > 0 && v > 0 && u+v < 1. Consulte, por ejemplo, aquí para obtener una explicación más detallada y un buen gráfico interactivo. NB: para guardar algunos caracteres y evitar errores DIV0, solo calculamos un acceso directo a uyv y una prueba modificada ( min(u*k,v*k,k-u-v)>0).

Los únicos operadores matemáticos utilizados son +, -, *, min()>0.