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

Numerically stable standard deviation calculation and code perforation

How would you implement a class which has an append(double x) function to collect values, and a get_std_dev() function which returns the standard deviation of the values collected?

Sounds like an easy problem, here is my guess at what your code would look like:

	class StdDevCalc {
	private:
	long long m_count;
	double m_sum_sq, m_sum, m_var;
	public:
	StdDevCalc() {
	m_sum_sq = m_sum = m_var = m_count = 0;
	}
	void append(double d) {
	m_count++;
	m_sum_sq += d * d;
	m_sum += d;
	if (m_count > 1)
	m_var = (m_sum_sq - m_sum * m_sum / m_count) / (m_count - 1);
	}
	double get_std_dev() {
	return sqrt(m_var);
	}
	};

view raw stddevcalc.cpp hosted with ❤ by GitHub

This looks like an standard implementation, but it contains some subtle bugs. These bugs do not show up in regular usage, but they lie patiently in wait. Remember the tricky binary search implementation bug which escaped detection in the JDK for about a decade and is now staple fodder of all technical interviews?