Count Number of Triples in an array that are collinear

I was asked this Interview Question (C++,algos)and had no idea how to solve it.

Given an array say Arr[N] containing Cartesian coordinates of N distinct points count the number of triples (Arr[P], Arr[Q], Arr[R]) such that P < Q < R < N and the points Arr[P], Arr[Q], Arr[R] are collinear (i.e lie on the same straigh开发者_如何学运维t line).

Any ideas? What algorithm can I use for this?

---

The following is probably not optimized, but its complexity is the one your interviewer requested.

First create a list of (a,b,c) values for each couple of points (N² complexity) --> (a,b,c) stands for the cartesian equation of a straight line a*x+b*y+c=0 Given two points and their coordinates (xa, ya) and (xb, yb), computing (a,b,c) is simple. Either you can find a solution to

ya=alpha*xa+beta  
yb=alpha*xb+beta

(if (xb-xa) != 0)
alpha = (yb-ya)/(xb-xa)
beta = ya - alpha*xa
a = alpha
b = -1
c = beta

or to

xa = gamma*ya+delta
xb = gamma*yb+delta
(you get the point)

The solvable set of equations can then be rewritten in the more general form

a*x+b*y+c = 0

Then sort the list (N² log(N²) complexity therefore N²log(N) complexity).

Iterate over elements of the list. If two sequential elements are equal, corresponding points are collinear. N² complexity.

You might want to add a last operation to filter duplicate results, but you should be fine, complexity-wise.

EDIT : i updated a bit the algorithm while coding it to make it more simple and optimal. Here it goes.

#include <map>
#include <set>
#include <vector>
#include <iostream>

struct StraightLine
{
    double a,b,c;
    StraightLine() : a(0.),b(0.),c(0.){}
    bool isValid() { return a!=0. || b!= 0.; }
    bool operator<(StraightLine const& other) const
    {
        if( a < other.a ) return true;
        if( a > other.a ) return false;
        if( b < other.b ) return true;
        if( b > other.b ) return false;
        if( c < other.c ) return true;
        return false;
    }
};

struct Point { 
    double x, y; 
    Point() : x(0.), y(0.){}
    Point(double p_x, double p_y) : x(p_x), y(p_y){}
};

StraightLine computeLine(Point const& p1, Point const& p2)
{
    StraightLine line;
    if( p2.x-p1.x != 0.)
    {
        line.b = -1;
        line.a = (p2.y - p1.y)/(p2.x - p1.x);
    }
    else if( p2.y - p1.y != 0. )
    {
        line.a = -1;
        line.b = (p2.x-p1.x)/(p2.y-p1.y);
    }
    line.c = - line.a * p1.x - line.b * p1.y;
    return line;
}

int main()
{
    std::vector<Point> points(9);
    for( int i = 0 ; i < 3 ; ++i )
    {
        for( int j = 0; j < 3 ; ++j )
        {
            points[i*3+j] = Point((double)i, (double)j);
        }
    }


    size_t nbPoints = points.size();
    typedef std::set<size_t> CollinearPoints;
    typedef std::map<StraightLine, CollinearPoints> Result;
    Result result;

    for( int i = 0 ; i < nbPoints ; ++i )
    {
        for( int j = i + 1 ; j < nbPoints ; ++j )
        {
            StraightLine line = computeLine(points[i], points[j]);
            if( line.isValid() )
            {
                result[line].insert(i);
                result[line].insert(j);
            }
        }
    }

    for( Result::iterator currentLine = result.begin() ; currentLine != result.end(); ++currentLine )
    {
        if( currentLine->second.size() <= 2 )
        {
            continue;
        }
        std::cout << "Line";
        for( CollinearPoints::iterator currentPoint = currentLine->second.begin() ; currentPoint != currentLine->second.end() ; ++currentPoint )
        {
            std::cout << " ( " << points[*currentPoint].x << ", " << points[*currentPoint].y << ")";
        }
        std::cout << std::endl;
    }
    return 0;
}

---

For the count of Collinear triplets, identify a line with any two points and then check whether a new line formed by any other two points might be coinciding or parallel and that needs to be taken care of while computing the collinear triplets.

To solve:

1. First, collect all points on a line using Map<Line, Set<Point2d>> as suggested in the question itself.
2. For triplets filter out those lines which have at least three points
3. Then compute nC3 for each of those add to global result.

Code for the above problem below

    import java.util.*;

    public class CollinearTriplets {

        public static void main(String[] args) {
            Point2d A[] = new Point2d[8];
            A[0] = new Point2d(0, 0);
            A[1] = new Point2d(1, 1);
            A[2] = new Point2d(2, 2);
            A[3] = new Point2d(3, 3);
            A[4] = new Point2d(3, 2);
            A[5] = new Point2d(4, 2);
            A[6] = new Point2d(5, 1);
            A[7] = new Point2d(4, 4);

            System.out.println(countCollinear(A));
        }


        public static int factorial(int n) {
            int fact = 1;
            for (int i = 1; i <= n; i++) {
                fact = fact * i;
            }
            return fact;
        }

        private static int combinations(int n, int r) {
            return factorial(n) / (factorial(n - r) * factorial(r));
        }

        private static long countCollinear(Point2d[] points) {
            Map<Line, Set<Point2d>> lineToPoints = new HashMap<>();
            long result = 0;

            for (int i = 0; i < points.length; i++) {
                for (int j = i + 1; j < points.length; j++) {
                    double slope = 0d, xIntercept, yIntercept; // Default slope paralell to y-axis
                    if (points[i].x == points[j].x) {
                        slope = Double.MAX_VALUE; // Horizontal slope parallel to x-axis
                    } else if (points[i].y != points[j].y) {
                        xIntercept = points[j].x - points[i].x;
                        yIntercept = points[j].y - points[i].y;
                        slope = yIntercept / xIntercept;
                    }
                    Line currLine = new Line(points[i], slope);
                    if (Objects.isNull(lineToPoints.get(currLine))) {
                        lineToPoints.put(currLine, new HashSet<>());
                    }
                    lineToPoints.get(currLine).add(points[i]);
                    lineToPoints.get(currLine).add(points[j]);
                }

            }
            for (Line line : lineToPoints.keySet()) {
                int size = lineToPoints.get(line).size();
                if (size >= 3) {
                    result = result + combinations(size, 3);
                }
            }
            return result;
        }

        /**
         * Line which contains the starting point and slope so that you can identify exact line
         * equals method is overridden to check whether any new line is coinciding or parallel
         */
        static class Line {
            Point2d point;
            double slope;

            public Line(Point2d point, double slope) {
                this.point = point;
                this.slope = slope;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (!(o instanceof Line)) return false;
                Line line = (Line) o;

                if (line.slope == this.slope)
                    return ((((double) (line.point.y - this.point.y)) / (line.point.x - this.point.x)) == this.slope);
                return false;
            }

            @Override
            public int hashCode() {
                return Objects.hash(slope);
            }
        }

        static class Point2d {
            int x;
            int y;

            public Point2d(int x, int y) {
                this.x = x;
                this.y = y;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (!(o instanceof Point2d)) return false;
                Point2d point2d = (Point2d) o;
                return x == point2d.x &&
                        y == point2d.y;
            }

            @Override
            public int hashCode() {
                return Objects.hash(x, y);
            }
        }
    }

The time complexity for above code O(N^2) and space complexity is O(N)

---

If it's 2 dimension points: 3 points (P,Q,R) are collinear if (P,Q), (P,R) define the same slope.

m = (p.x - q.x) / (p.y - q.y)  ; slope

Somehow you need to check all possible combinations and check, an efficient algo is trick as the first naive is N*(N-1)*(N-2)...

---

Instead of 3 loops, whish is O(n³), precompute the slopes of all lines given by two points Arr[P], Arr[Q]. That's O(n²). Then compare these slopes.

You can improve that further sorting the lines by their slope during computation or afterwards, which is O(n log n). After that finding lines with the same slope is O(n).

But you may have to pay a price for that by implementing a data structure, when you want to know, which points are collinear.

I think the key point of an interview question is not to give the perfect algorithm, but to identify and discuss the problems within an idea.

Edit:

Brute force approach:

#include <iostream>
#include <vector>

struct Point { int x, y; };
bool collinear(Point P, Point Q, Point R)
{
  // TODO: have to look up for math ... see icCube's answer
  return false; 
}

int main()
{
  std::vector<Point> v;

  Point a;
  while (std::cin >> a.x >> a.y)
  {
    v.push_back(a);
  }

  int count = 0;
  for (int p = 0; p < v.size(); ++p)
  {
    for (int q = p+1; q < v.size(); ++q)
    {
      for (int r = q+1; r < v.size(); ++r)
      {
        if (collinear(v[p], v[q], v[r])) ++count;
      }
    }  
  }
  std::cout << count << '\n';
  return 0;
}

---

It's trivial to see that you can get all the pairs of points and their slope & y-intercepts in O(n^2) time. So the output is:

IndexB Slope Y-Intercept IndexA

Of course, we won't insert any entries where IndexA = IndexB.

Let's have this table indexed on (IndexB,Slope,Y), which forces our insert into this table as O(log(n))

After we fill out this table with new records (B',S',Y',A'), we check to see if we already have an element such that B'=A of the existing table and B!=A' of the new record (meaning we have a unique triplet) that matches the slope and Y-intercept (meaning collinear). If this is the case and A < B < B', increment the count by 1.

EDIT: One clarifying remark. We need to make sure that we fill this table "backwards" first, taking all the pairs that wouldn't satisfy A < B (< C). This ensures that they will exist in the table before we start testing for their existence.

EDIT: Wow my C++ is rusty... took a while.

#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>
#include <math.h>

using namespace std;

#define ADD_POINT(xparam,yparam) { point x; x.x = xparam; x.y = yparam; points.push_back(x); };

#define EPSILON .001

class line {
public:
  double slope;
  double y;
  int a;
  int b;

  bool operator< (const line &other) const{
    if(this->a < other.a)
      return true;
    else if(this->a==other.a){
      if(this->slope-other.slope < -EPSILON)
        return true;
      else if(fabs(this->slope-other.slope) < EPSILON){
        if(this->y-other.y < -EPSILON)
          return true;
        else
          return false;
      }else
        return false;
    }else
      return false;
  }

  line(double slope, double y, int a, int b){
    this->slope = slope;
    this->y = y;
    this->a = a;
    this->b = b;
  }

  line(const line &other){
    this->slope = other.slope;
    this->y = other.y;
    this->a = other.a;
    this->b = other.b;
  }
};

class point {
public:
  double x;
  double y;
};

int main(){
  vector<point> points;
  ADD_POINT(0,0);
  ADD_POINT(7,28);
  ADD_POINT(1,1);
  ADD_POINT(2,3);
  ADD_POINT(2,4);
  ADD_POINT(3,5);
  ADD_POINT(3,14);
  ADD_POINT(5,21);
  ADD_POINT(9,35);

  multiset<line> lines;
  for(unsigned int x=0;x<points.size();x++){
    for(unsigned int y=0;y<points.size();y++){
      if(x!=y){ // No lines with the same point
        point a = points[x];
        point b = points[y];
        double slope = (a.y-b.y)/(a.x-b.x);
        double yint;
        yint = a.y-a.x*slope;
        line newline(slope,yint,x,y);
        lines.insert(newline);
      } 
    }
  }

  for(multiset<line>::const_iterator p = lines.begin(); p != lines.end(); ++p){
    //cout << "Line: " << p->a << " " << p->b << " " << p->slope << " " << p->y << endl;
    line theline = *p;
    line conj(theline.slope,theline.y,theline.b,-1);
    multiset<line>::iterator it;
    pair<multiset<line>::iterator,multiset<line>::iterator> ret;
    ret = lines.equal_range(conj);
    for(it = ret.first; it!=ret.second; ++it){
      //cout << "  Find: " << it->a << " " << it->b << " " << it->slope << " " << it->y << endl;
      int a = theline.a;
      int b = theline.b;
      int c = it->b;
      if(a < b && b < c){
        cout << a << " " << b << " " << c << std::endl;
      }
    }
  }


  //cout << points[0].x << std::endl;

}

---

I have this solution tell if there is a better one,

Sort all the points according to the slope they make with the x axis or any other axis you want ( O(n* logn) ). Now all you have to do if go through the sorted list and find points which have same slope either inpositive or negative direction( this can be done in linear time i.e. O(n) ) . Lets say you get m such points for one case then increment the answer by C(m,3)..

Total time depends on how good you implement C(m,3)

But asymptotically O(N logN)

Edit: After seeing icCube's comment i realize that we cannot take any axis..so for the above defined algo taking the slope calculating point as one of the n points ( thus n times ) should be my best guess. But it makes the algorithm N*N*Log(N)