## Collinearity

### June 17, 2014

We’ll follow the essay written by Brian Hayes in the book *Beautiful Code* compiled by Andy Oram and Greg Wilson.

Hayes’ first solution is to calculate the slope *m* and *y*-intercept *b* of the two points *p* = (*px*,*py*) and *q* = (*qx*,*qy*) and determine if point *r* = (*rx*,*ry*) is on the line *y* = *m x* + *b*:

`(define (naive-collinear? px py qx qy rx ry)`

(let* ((m (/ (- qy py) (- qx px))) (b (- py (* m px))))

(= ry (+ (* m rx) b))))

```
```

`> (naive-collinear? 1 2 3 4 5 6)`

#t

> (naive-collinear? 1 2 3 4 5 7)

#f

> (naive-collinear? 1 1 2 1 3 1)

#t

> (naive-collinear? 1 1 1 2 1 3)

Exception in /: undefined for 0

Type (debug) to enter the debugger.

The trick is finding the slope and intercept. If the line is vertical, both are undefined, leading to a divide-by-zero error. Hayes solves the problem by returning a non-integer value instead of the divide-by-zero error:

`(define (slope px py qx qy)`

(if (= px qx) #f (/ (- qy py) (- qx px))))

```
```(define (intercept px py qx qy)

(let ((m (slope px py qx qy)))

(if m (- py (* m px)) #f)))

(define (less-naive-collinear? px py qx qy rx ry)

(let ((m (slope px py qx qy))

(b (intercept px py qx qy)))

(if m (= ry (+ (* m rx) b)) (= px rx))))

`> (less-naive-collinear? 1 2 3 4 5 6)`

#t

> (less-naive-collinear? 1 2 3 4 5 7)

#f

> (less-naive-collinear? 1 1 2 1 3 1)

#t

> (less-naive-collinear? 1 1 1 2 1 3)

#t

Hayes’ second solution is to compute the slopes of the two lines *pq* and *qr*; if the slopes are the same, the two lines must be the same, because they share point *q*:

`(define (mm-collinear? px py qx qy rx ry)`

(equal? (slope px py qx qy) (slope qx qy rx ry)))

```
```

`> (mm-collinear? 1 2 3 4 5 6)`

#t

> (mm-collinear? 1 2 3 4 5 7)

#f

> (mm-collinear? 1 1 2 1 3 1)

#t

> (mm-collinear? 1 1 1 2 1 3)

#t

This works in Scheme but not in other languages, because `equal?`

can compare two numbers for equality and also two booleans. In languages with only a numeric comparison, that would be more complicated:

`(define (typed-mm-collinear? px py qx qy rx ry)`

(let ((pq-slope (slope px py qx qy))

(qr-slope (slope qx qy rx ry)))

(or (and pq-slope qr-slope (= pq-slope qr-slope))

(and (not pq-slope) (not qr-slope)))))

```
```

`> (typed-mm-collinear? 1 2 3 4 5 6)`

#t

> (typed-mm-collinear? 1 2 3 4 5 7)

#f

> (typed-mm-collinear? 1 1 2 1 3 1)

#t

> (typed-mm-collinear? 1 1 1 2 1 3)

#t

Hayes’ third solution considers the three points as the corners of a triangle and determines they all fall on a line when the lengths of two of the lines equal the length of the third:

`(define (distance px py qx qy)`

(define (square x) (* x x))

(sqrt (+ (square (- qx px)) (square (- qy py)))))

```
```(define (triangle-collinear? px py qx qy rx ry)

(let ((pq (distance px py qx qy))

(qr (distance qx qy rx ry))

(rp (distance rx ry px py)))

(let ((sidelist (sort > (list pq qr rp))))

(= (car sidelist) (+ (cadr sidelist) (caddr sidelist))))))

`> (triangle-collinear? 1 2 3 4 5 6)`

#t

> (triangle-collinear? 1 2 3 4 5 7)

#f

> (triangle-collinear? 1 1 2 1 3 1)

#t

> (triangle-collinear? 1 1 1 2 1 3)

#t

That works, and there is no problem with vertical lines because there is no division, but it may incorrectly report that three-non-collinear points are collinear because the square root is less than the precision of the calculation; consider, for instance, the triangle (0,0), (*x*,1), (2*x*,0) with a very large *x*.

`> (let ((x #e1e100))`

(triangle-collinear? 0 0 x 1 (* 2 x) 0))

#f

> (let ((x #e1e500))

(triangle-collinear? 0 0 x 1 (* 2 x) 0))

#t

Hayes’ fourth and final solution notes that the area of the triangle formed by the three points is zero if and only if the three points are collinear. This sounds similar to the third solution, but isn’t; for a triangle like the one that spoiled the third solution, the area is large when *x* is large, so there is no problem of the area vanishing into zero:

`(define (area-collinear? px py qx qy rx ry)`

(= (* (- px rx) (- qy ry)) (* (- qx rx) (- py ry))))

```
```

`> (area-collinear? 1 2 3 4 5 6)`

#t

> (area-collinear? 1 2 3 4 5 7)

#f

> (area-collinear? 1 1 2 1 3 1)

#t

> (area-collinear? 1 1 1 2 1 3)

#t

> (let ((x #e1e100))

(area-collinear? 0 0 x 1 (* 2 x) 0))

#f

> (let ((x #e1e500))

(area-collinear? 0 0 x 1 (* 2 x) 0))

#f

And that’s it. No `if`

s, no square roots, no divide-by-zero errors. Beautiful. Given the exact rational arithmetic of Scheme, it never fails; for languages that perform floating point arithmetic, it is still possible for this function to fail, but it is much more robust in the face of bad inputs than `triangle-collinear?`

And it’s also very fast, faster than any of the alternatives, with only four subtractions, two multiplications, and a numeric comparison.

You can run the program at http://programmingpraxis.codepad.org/aM0MIJaI.

In Python.

My simple solution uses the fact that point lying on the same line form a triangle of area zero.

This code just does that.

Using area of triangle is 0, includes duplicate points and avoids zero division.

(define re real-part) (define im imag-part) (define mag magnitude)

(define (dot u w) (+ (* (re u) (re w)) (* (im u) (im w))))

(define (collinearish? u v w)

(let ((uv (- u v)) (uw (- u w)) (eps 1e-14))

(or (< (mag uv) eps) (< (mag uw) eps)

(< (abs (- (cos 0) (abs (/ (dot uv uw) (mag uv) (mag uw))))) eps))))

A complex solution, pun intended, to within an epsilon: representing points as rectangular numbers in the obvious way, then computing the cosine of the angle between two vectors. (Or if at least one of the two vectors is null, the three points are at most two, and so collinear.)

If A, B and C are collinear, the vector product of AB and AC is zero.

bool collinear(x1, y1, x2, y2, x3, y3) {

return ((x2 – x1)*(y3 – y1) – (x3 – x1)*(y2 – y1) == 0);

}

I like pbo’s solution – it’s equivalent to taking AB and BC, rotating BC 90 degrees and taking the dot product. This gives |AB| *

We can extend to a nice floating point solution, for consistency (and to minimize rounding errors) we will take all three difference vectors and work with the two longest ones (this also deals nicely with have two of the points very close to each other). Having calculated the dot product, we then scale by the length of the longest vector to get a dimensionless indication of collinearity (so scaling up all the points by a constant factor doesn’t affect the result). For simplicity, we use the taxicab metric for computing vector lengths. (Needs C++11 for auto).

Here is a Racket Solution. I use the fact that three collinear points produce a triangle of area 0. My solution uses an epsilon value to take into account error propagation in floating point, so it is a probabilistic method, although very accurate.

I used the same approach as pbo:

Codepad

Attempt to embed:

module Collinear (collinear) where

(.-) :: Num a => (a, a) -> (a, a) -> (a, a)

(x1, x2) .- (y1, y2) = (x1 – y1, x2 – y2)

cross :: Num a => (a, a) -> (a, a) -> a

(x1, x2) `cross` (y1, y2) = x1 * y2 – x2 * y1

collinear :: (Num a, Eq a) => (a, a) -> (a, a) -> (a, a) -> Bool

collinear v1 v2 v3 = (v1 .- v2) `cross` (v1 .- v3) == 0

Javascript Code…

/*input*/

var points = [

{

x : 5,

y : 5

},

{

x : 15,

y : 15

},

{

x : 40,

y : 40

}

];

/*logic*/

function isCoLinear(points){

return (Math.atan( Math.abs((points[1][“y”] – points[0][“y”])/(points[1][“x”] – points[0][“x”])) ) * (180/Math.PI)) ===

(Math.atan( Math.abs((points[2][“y”] – points[0][“y”])/(points[2][“x”] – points[0][“x”])) ) * (180/Math.PI))

}

isCoLinear(points);