# Like a path-segment; touched for the very first time

Given an ordered list of 2 or more 2D cartesian points, output a truthy value if either the path touches itself or self-intersects; otherwise output a falsy value if it does not touch itself or self-intersect.

You may assume that consecutive points in the list are distinct.

### Examples:

(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


Note all the co-ordinates I gave here are integers. You may support co-ordinate inputs of whatever you like out of {integer, decimal, rational, floating-point, ...}. But your implementations calculations must give the correct answers for any inputs given.

• what a good title A+ – undergroundmonorail Oct 3 '17 at 22:50
• Initial scene of Reservoir Dogs, anyone? – Luis Mendo Oct 3 '17 at 23:03
• Forgive me if I'm misunderstanding but how is the last test case non-intersecting? i.imgur.com/wiNMByd.png – totallyhuman Oct 4 '17 at 0:36
• @icrieverytim It is not a closed walk. The last point does not connect to the first. – HyperNeutrino Oct 4 '17 at 0:41

# Python 2, 315309298382380 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]])


Try it online!

Uses the algorithm from here, combined with this SO answer for collinear segments.

Edit: Fixed for line segments continuing in the same direction (eg (0,0),(1,0),(2,0)) by removing the middle point, (resulting in (0,0),(2,0)).

• You can save two bytes by replacing all two occurrences of two spaces with a single tab. – Jonathan Frech Oct 4 '17 at 15:20
• *((n*N>0)+(m*M>0)<1) -> *(n*N<=0>=m*M). – Jonathan Frech Oct 4 '17 at 15:27

# 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


Function named i that, passed a set of points, returns 0 or 1. Semicolons and line breaks are interchangeable for ending a command, I just lumped a few things together for the sake of keeping the code visibly short since we're not used to legible code around here anyway.

Eukleides is a plane geometry language primarily for graphical output, but with decent programmatic abilities as well. I thought it'd be great for this task, but a few things frustrated me. First, it's worth noting that sets in Eukleides are essentially arrays of points, and when applicable are rendered out as paths made of connected line segments. Eukleides supports the iterative generation of sets via loci, akin to a for-loop that creates a set in the process. Had I been able to use a locus, it would have shaved off bytes, but apparently Eukleides doesn't like to reference a partially-formed locus from within itself.

The other major frustration was that if, seemingly, two identical line segments are on top of each other, intersection only returns one offending point (which makes sense, I suppose, there would be infinite intersections). My method is essentially to build up the path one step behind, and test the next line segment for intersections with the path. Because of the aforementioned intersection behavior I check separately for whether or not the point is on the path.

Edit: Cut off 1 byte by reordering the or statement to allow for the removal of a space before or; 5 more bytes by changing that if block into a ternary operation.

Test cases:

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