The blog of dlaa.me

I happened across another coding puzzle recently that caught my interest. (If you're curious, here is a link to the puzzle I discussed a few weeks ago about implementing a weird kind of addition.) The problem this time is as follows:

You are given an array of coordinates, coordinates[i] = [x,y], where [x,y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

I saw an approach to solving this that didn't thrill me, so I wanted to solve it for myself.

If you're going to do the same, stop reading now because there are spoilers ahead!

As an aside, one thing I don't love about this problem is that it requires a certain amount of geometry knowledge to solve and furthermore the solution I use benefits from experience with trigonometric functions. However, one can be a perfectly good programmer without knowing either of these topics and they're not likely to come up in most roles. I try to avoid questions like this when I'm interviewing because they're likely to favor some backgrounds over others. That said, I didn't come up with this scenario and it's still interesting to think about, so let's go.

The first thing is to figure out how to approach the problem. If you remember much about linear equations, you might think to use the equation for a line to solve this: y = mx + b. If the slope, m, and the y-intercept, b, are the same for all pairs of points, then they all lie on the same line. This is helpful, but the equation starts to fall apart for points that lie on the same vertical line (for example, along the y-axis) because the slope there is infinite. Now, maybe you are comfortable dealing with infinity or risking division by zero, but I am not. That makes the vertical line scenario a special case and "special case" is often another phrase for "bug farm".

We don't want to use the slope equation, but we're in luck because there's something similar that's easier to work with: angle. Specifically:

The Math.atan2() function returns the angle in the plane (in radians) between the positive x-axis and the ray from (0,0) to the point (x,y), for Math.atan2(y,x).

That's not a solution as-is, but if we choose two points from the input and subtract the corresponding x and y coordinates, we get coordinates that define a ray in the manner described above. Now, two sets of points on line segments sharing the same angle (as calculated above) will be parallel, but not necessarily collinear. However, if we use the same point to calculate the angle to every other point of the input, that should be sufficient to determine collinearity of the set. In words:

If the angle of the line segment made up by pairing the first point of the input array with every other point of the array is the same, then we know all those rays point in the same direction and all originate at the same point (the first point) and therefore all the points are on the same line!

We're nearly there, but there's one more observation: two rays that go in exactly opposite directions from the same point are also on the same line. For example, the line segment defined by two points on a ray with an angle of 10° to the x-axis are parallel to the segment corresponding to two points on a ray with an angle of 190° to the x-axis. So instead of worrying about all 360°, we can focus on just the first 180°. The modulo operator provides an easy way to map angles between 180° and 360° into the range of 0° to 180°. (Except that the atan2 function returns values in radians instead of degrees because "Why not?" so we're going to be dealing with π.)

With all that behind us, the following algorithm should make sense. There are a few subtleties so it correctly handles empty lists as well as lists with just one point and also lists where the same point appears multiple times. In addition, it bails out as soon as it finds a non-collinear point for efficiency. Here's the code - as is the custom with JavaScript, there's no parameter validation, but this is intended to work for all valid inputs:

function arePointsCollinear(points) {
  let angle = null;
  const first = points[0];
  for (let i = 1; i < points.length; i++) {
    const current = points[i];
    const deltaX = current[0] - first[0];
    const deltaY = current[1] - first[1];
    if (deltaX || deltaY) {
      const theta = (Math.atan2(deltaY, deltaX) + Math.PI) % Math.PI;
      if (angle === null) {
        angle = theta;
      } else if (angle !== theta) {
        return false;
      }
    }
  }
  return true;
}