How to determine if some line segments are collinear

Question

Let's say I have several Line Segments that are connected to each other and make a Polyline.

How can I determine if they are on a single straight line?

Is there a rather efficient algorithm for this? Or I will need to go the traditional way and go through all the lines and compare them with each other?

Answer 1

Three points are collinear if the determinant

|x1 y1 1|
|x2 y2 1| = x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2
|x3 y3 1|

is zero. That's equivalent to stating that the area of the triangle formed by these three is zero, since the area would be half the value of this determinant by Heron's formula.

The determinant of three vectors can also be expressed as a triple product, i.e. a dot product where one factor is a cross product. Which means that

(x1, y1, 1) × (x2, y2, 1) = (y1 - y2, x2 - x1, x1*y2 - y1*x2) = (a, b, c)

describes a line spanned by these two points. It corresponds to the equation ax + by + c = 0.

So you can start with two points (for numeric reasons you might want to space them as far apart as possible), compute that cross product as above to obtain a,b,c, then plug every other point into the equation ax+by+c=0 and see whether you really get zero (or something close to zero, for numeric reasons).