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.

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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.