Dada una lista ordenada de 2 o más puntos cartesianos 2D, genera un valor verdadero si la ruta se toca a sí misma o se auto-intersecta; de lo contrario, generará un valor falso si no se toca a sí mismo o no se cruza automáticamente.

Puede suponer que los puntos consecutivos en la lista son distintos.

Ejemplos:

(0,0), (1,0) -> falsey
(0,0), (1,0), (0,0) -> truthy
(0,0), (1,0), (1,1), (0,0) -> truthy
(0,0), (2,0), (1,1), (1,-1) -> truthy
(0,0), (10,0), (0,1), (10,1), (0,2), (10,2) -> falsey

Tenga en cuenta que todas las coordenadas que di aquí son enteros. Puede admitir entradas de coordenadas de lo que quiera de {entero, decimal, racional, coma flotante, ...}. Pero sus cálculos de implementación deben dar las respuestas correctas para cualquier entrada dada.

Python 2 , 315 309 298 382 380 372 bytes

s=sorted
w=lambda(x,y),(X,Y),(z,w):(X-x)*(w-y)-(z-x)*(Y-y)
def I(a,b):p,q=s(a);P,Q=s(b);n,N,m,M=w(p,q,P),w(p,q,Q),w(P,Q,p),w(P,Q,q);return(q>=P)*(Q>=p)if{n,N,m,M}=={0}else(b[1]!=a[0])*(n*N<=0>=m*M)
def f(l):
 i=0
 while i<len(l)-2:
	x=l[i:i+3];i+=1
	if w(*x)==0and s(x)==x:l.pop(i);i-=1
 L=zip(l,l[1:]);return any(I(*l)for l in[(k,x)for i,k in enumerate(L)for x in L[:i]])

Pruébalo en línea!

Utiliza el algoritmo de aquí , combinado con esta respuesta SO para segmentos colineales.

Editar: Corregido para segmentos de línea que continúan en la misma dirección (p (0,0),(1,0),(2,0). Ej. ) Al eliminar el punto medio, (lo que resulta en (0,0),(2,0)).

Eukleides , 154 148 bytes

number i (set p)
g=card(p);h=g;n=0;e=p[0];q=e.e
for d in p
if h<g-1 
q=q.e
n=card(intersection(d.e,q))>1or d on q?1|n
end
e=d;h=h-1
end;return n;end

La función llamada iasí, pasó un conjunto de puntos, devuelve 0 o 1. Los puntos y líneas y los saltos de línea son intercambiables para finalizar un comando, solo reuní algunas cosas para mantener el código visiblemente corto ya que no estamos acostumbrados a ser legible código por aquí de todos modos.

Eukleides es un lenguaje de geometría plana principalmente para salida gráfica, pero con habilidades programáticas decentes también. Pensé que sería genial para esta tarea, pero algunas cosas me frustraron. Primero, vale la pena señalar que los conjuntos en Eukleides son esencialmente conjuntos de puntos y, cuando corresponde, se representan como rutas hechas de segmentos de línea conectados. Eukleides admite la generación iterativa de conjuntos a través de loci, similar a un ciclo for que crea un conjunto en el proceso. Si hubiera podido usar un locus, habría reducido los bytes, pero aparentemente a Eukleides no le gusta hacer referencia a un locus parcialmente formado desde dentro de sí mismo.

La otra gran frustración fue que si, aparentemente, dos segmentos de línea idénticos están uno encima del otro, intersectionsolo devuelve un punto ofensivo (lo que tiene sentido, supongo, habría infinitas intersecciones). Mi método es esencialmente construir la ruta un paso atrás y probar el siguiente segmento de línea para intersecciones con la ruta. Debido al comportamiento de intersección mencionado anteriormente, verifico por separado si el punto está en el camino o no .

Editar : Corte 1 byte reordenando la orinstrucción para permitir la eliminación de un espacio antes or; 5 bytes más al cambiar ese ifbloque en una operación ternaria.

Casos de prueba:

ta=point(0,0).point(1,0)
tb=point(0,0).point(1,0).point(0,0)
tc=point(0,0).point(1,0).point(1,1).point(0,0)
td=point(0,0).point(2,0).point(1,1).point(1,-1)
te=point(0,0).point(10,0).point(0,1).point(10,1).point(0,2).point(10,2)
print i(ta);print i(tb);print i(tc);print i(td);print i(te)

0
1
1
1
0