Dada uma lista ordenada de 2 ou mais pontos cartesianos 2D, produza um valor de verdade se o caminho tocar a si próprio ou se interceptar; caso contrário, produza um valor falso se não se tocar ou se interceptar.

Você pode assumir que pontos consecutivos na lista são distintos.

Exemplos:

(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

Observe que todas as coordenadas que dei aqui são números inteiros. Você pode oferecer suporte a coordenar entradas do que quiser, entre {número inteiro, decimal, racional, ponto flutuante, ...}. Mas seus cálculos de implementações devem fornecer as respostas corretas para quaisquer entradas fornecidas.

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

Experimente online!

Usa o algoritmo daqui , combinado com esta resposta SO para segmentos colineares.

Editar: corrigido para segmentos de linha que continuam na mesma direção (por exemplo (0,0),(1,0),(2,0)) removendo o ponto do meio (resultando em (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

Função denominada ithat, passou por um conjunto de pontos, retorna 0 ou 1. Ponto-e-vírgula e quebras de linha são intercambiáveis ​​para finalizar um comando. Apenas agrupei algumas coisas para manter o código visivelmente curto, pois não estamos acostumados a legibilidade. código por aqui de qualquer maneira.

Eukleides é uma linguagem de geometria plana principalmente para saída gráfica, mas com habilidades programáticas decentes também. Eu pensei que seria ótimo para esta tarefa, mas algumas coisas me frustraram. Primeiro, é importante notar que os conjuntos no Eukleides são essencialmente matrizes de pontos e, quando aplicáveis, são renderizados como caminhos feitos de segmentos de linha conectados. Eukleides suporta a geração iterativa de conjuntos via loci, semelhante a um loop for que cria um conjunto no processo. Se eu fosse capaz de usar um locus, ele teria raspado bytes, mas aparentemente Eukleides não gosta de fazer referência a um locus parcialmente formado a partir de si.

A outra grande frustração foi que, se, aparentemente, dois segmentos de linha idênticos estiverem em cima um do outro, intersectionretornará apenas um ponto ofensivo (o que faz sentido, suponho, haveria interseções infinitas). Meu método é essencialmente construir o caminho um passo atrás e testar o próximo segmento de linha para interseções com o caminho. Devido ao comportamento de interseção mencionado acima, verifico separadamente se o ponto está ou não no caminho.

Editar : corte 1 byte reordenando a orinstrução para permitir a remoção de um espaço antes or; 5 bytes a mais, alterando esse ifbloco para uma operação ternária.

Casos de teste:

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