Punto en casco convexo (2D)

10

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

Alexandre Halm
fuente
3
¿Qué es una "estructura de datos ad hoc"?
DavidC
"funciones / operadores elementales" es demasiado vago.
xnor
@DavidCarraher: algo así como un Polígono, o un Triángulo, o un Segmento (cualquier cosa que exista solo para resolver problemas geométricos).
Alexandre Halm
2
@AlexandreHalm Tu edición ayudó mucho. Creo que "elemental" no es la palabra correcta. Pensé que eliminaría las incorporaciones de uso general como sorto round. Creo que es más claro simplemente decir que no se permite nada hecho específicamente para la geometría. Sin embargo, ¿qué pasa con una función para agregar dos listas como vectores? ¿O una función para encontrar el argumento (ángulo) de un número complejo?
xnor
1
Es por eso que los Diamantes solicitan a las personas que usen Sandbox antes de publicar nuevos desafíos.
gato

Respuestas:

9

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)
Ana
fuente
¿Hay alguna posibilidad de que sus soluciones (al menos la de Python, no tengo idea si J puede hacer eso) reciban información de STDIN? Creo que sería más fácil comparar soluciones con un campo de juego nivelado. Asumir que la entrada ya es un conjunto preformateado de números o puntos complejos es un poco IMO extenso.
Alexandre Halm
@AlexandreHalm Se agregó el programa completo.
Ell
Debe dividir sus soluciones en una respuesta por idioma.
Mego
4

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

han
fuente
2

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.

Alexandre Halm
fuente
0

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.

Alexandre Halm
fuente