Collinearity

June 17, 2014

Beware: today’s exercise sounds simple but is actually quite complex if you don’t look at it properly.

Your task is to write a function that takes three points in the x,y plane and determines if they are collinear; be sure to handle vertical lines and horizontal lines properly. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

9 Responses to “Collinearity”

  1. Paul said

    In Python.

    def is_collinear(x1, y1, x2, y2, x3, y3):
        return x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) == 0
        
    assert is_collinear(0, 0, 1, 0, 2, 0)
    assert is_collinear(0, 0, 0, 1, 0, 2)
    assert is_collinear(0, 0, 1, 1, 2, 2)
    assert not is_collinear(0, 0, 1, 1, 2, 3)
    
  2. My simple solution uses the fact that point lying on the same line form a triangle of area zero.
    This code just does that.

    
    import math
    
    class Point:
        def  __init__(self,x,y):
            self.x = x;
            self.y = y;
    
    def distance(p1,p2):
        return  math.sqrt(math.pow(p1.x - p2.x, 2) + math.pow(p1.y - p2.y, 2))
    
    def getArea(pa,pb,pc):
        '''
        Uses Heron's Formula
        '''
        a = distance(pb,pc)
        b = distance(pa,pc)
        c = distance(pa,pb)
        s  =  (a +b  +c )/2
        return math.sqrt(s*(s-a)*(s-b)*(s-c))
        
    
    def is_Collinear(p1,p2,p3): 
        '''
        Collinear points form a traingle of area zero
        '''
        return getArea(p1,p2,p3) == 0
    
    
  3. Rutger said

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

    def collinear(x1,y1,x2,y2,x3,y3):
    	return x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)==0
    
    assert collinear(0,0, 0,0, 0,0)
    assert collinear(1,2, 1,3, 1,4)
    assert collinear(1,3, 2,2, 3,1)
    assert collinear(1,1, 2,2, -3,-3)
    
  4. Jussi Piitulainen said


    (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.)

  5. pbo said

    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);
    }

  6. matthew said

    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).

    #include <iostream>
    
    template <typename T>T square(T x) { return x*x; }
    template <typename T>T abs(T x) { return (x>=0) ? x : -x; }
    
    template <typename T>
    struct Vector
    {
       Vector(T x_, T y_) : x(x_), y(y_){}
       Vector(const Vector &p) : x(p.x), y(p.y) {}
       friend Vector operator-(Vector p, Vector q) { 
          return Vector(p.x-q.x, p.y-q.y);
       }
       T taxi() { return abs(x) + abs(y); } // Max would do too
       T x;
       T y;
    };
    
    
    template <typename T>
    T check(Vector<T> p, Vector<T> q, Vector<T> r)
    {
      Vector<T> a = p-q;
      Vector<T> b = q-r;
      Vector<T> c = r-p;
      // Sort a,b,c by taxi metric
      // Numerically more stable and we will should consistent
      // results regardless of point order.
      if (a.taxi() < b.taxi()) std::swap(a,b);
      if (b.taxi() < c.taxi()) std::swap(b,c);
      if (a.taxi() < b.taxi()) std::swap(a,b);
      // This is the perpendicular distance of point b from line a,
      // scaled by the taxi length of a. Since taxi length is no more
      // that sqrt(2) larger than the true length, this is fine.
      T res = abs(a.x*b.y - a.y*b.x)/square(a.taxi());
      return res;
    }
    
    Vector<float> rvector(float x, float y)
    {
      return Vector<float>(x,y);
    }
    
    int main(int argc, char *argv[])
    {
       {
          float x0 = 0.3333333;
          float y0 = 0.4444444;
          float k = 0.12345;
          auto p = rvector(1*k*x0,1*k*y0);
          auto q = rvector(2*k*x0,2*k*y0);
          auto r = rvector(3*k*x0,3*k*y0);
          auto s = rvector(3*k*x0,2*k*y0);
          std::cout << check(p,q,r) << "\n";
          std::cout << check(q,r,p) << "\n";
          std::cout << check(r,p,q) << "\n";
          std::cout << check(p,q,s) << "\n";
          std::cout << check(q,s,p) << "\n";
          std::cout << check(s,p,q) << "\n";
       }
       {
          float x = 1.23456789e10;;
          for (float k = 9.87654321e-10; k < 1e10; k *= 100) {
             auto p = rvector(0,0);
             auto q = rvector(k*x,k);
             auto r = rvector(2*k*x,0);
             std::cout << check(p,q,r) << "\n";
          }
       }
       {
          float x = 1e-10;;
          auto p = rvector(x,x);
          auto q = rvector(-x,x);
          auto r = rvector(1,1);
          std::cout << check(p,q,r) << "\n";
       }
    }
    
  7. 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.

    #lang racket
    (define (point x y)
      (cons x y))
    
    (define (x point)
      (car point))
    
    (define (y point)
      (cdr point))
    
    (define (distance p1 p2)
      (sqrt (+ (sqr (- (x p1)
                       (x p2)))
               (sqr (- (y p1)
                       (y p2))))))
    
    (define epsilon 0.001)
    
    (define (collinear? p1 p2 p3)
      (let ((a (distance p1 p2))
            (b (distance p2 p3))
            (c (distance p3 p1)))
        (let ((s (/ (+ a b c) 2)))
          (< (sqrt (foldr *
                          1
                          (map (lambda (x) (- s x))
                               (list 0 a b c))))
             epsilon))))
    
  8. treeowl said

    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

  9. Subhranshu said

    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);

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: