Line segment intersection

It looks like an easy problem, it has a trove of information on it and Bryce Boe even has a two line solution for it. However, his program does not handle improper intersections, i.e. when one end of one of the segments lies on the other line. Since a point lying on the line does not make triangles with different orientations (since it has zero area), his program does not count it as an intersection.

The highest voted answer on the stack overflow question needs special care while handling vertical lines (And it is general outline for a solution, not actual code).

Now there are multiple methods of correcting these problems, and this is one of them:

	def intersects(line_1, line_2):
	"""Whether line_1 and line_2 intersect or not."""
	A, B = line_1
	C, D = line_2
	if _ccw(A,C,D) != _ccw(B,C,D) and _ccw(A,B,C) != _ccw(A,B,D):
	# If the triangle pairs ACD, BCD and ABC, ABD have different
	# orientations, then the segments have to intersect
	return True
	for pt in line_2:
	if are_coll(A, B, pt):
	# check if pt is between A and B
	if sorted([A, B, pt])[1] == pt:
	return True
	for pt in line_1:
	if are_coll(C, D, pt):
	# check if pt is between A and D
	if sorted([C, D, pt])[1] == pt:
	return True
	return False
	def are_coll(p1, p2, p3, eps=1e-6):
	"""Determines whether given three points are collinear or not."""
	x, y = 0, 1
	lhs = (p2[x] - p1[x]) * (p3[y] - p1[y])
	rhs = (p2[y] - p1[y]) * (p3[x] - p1[x])
	return abs(lhs - rhs) < eps
	def _ccw(A,B,C):
	"""Determines whether triangle ABC is clockwise or anti-clockwise."""
	return (C[1]-A[1])*(B[0]-A[0]) > (B[1]-A[1])*(C[0]-A[0])

view raw intersection.py hosted with ❤ by GitHub

Use this function to test the implementation:

	def test_intersects():
	line_1 = ((0, 0), (1, 1))
	line_2 = ((2.5, 2.5), (1.5, 1.5)) # No intersection
	assert not intersects(line_1, line_2)
	line_1 = ((0, 0), (1, 1))
	line_2 = ((0, 0.5), (1, 0.5)) # Intersects
	assert intersects(line_1, line_2)
	line_1 = ((0, 0), (1, 1))
	line_2 = ((0.5, 0.5), (1.5, 1.5)) # Overlaps
	assert intersects(line_1, line_2)
	line_1 = ((0, 0), (1, 1))
	line_2 = ((0.5, 0.5), (1, .5)) # One point on line
	assert intersects(line_1, line_2)

view raw test_intersection.py hosted with ❤ by GitHub