Maximum Number of points on a line from origin

app.js

/* line {x,y,dx,dy} */
var points = [{x:1,y:1},{x:2,y:2},{x:1,y:2},{x:1,y:3},{x:1,y:4}];


var maxNumberOfPoints = 1;


points.forEach(function(pointA) {
  var numberOfPointsA = 1;
  var atan = Math.atan2(pointA.y, pointA.x);
  points.forEach(function(pointB) {
     if(pointA == pointB) {
        return;
     }
     var atanJ = Math.atan2(pointB.y, pointB.x);
     if(atanJ == atan || Math.abs(atanJ) + Math.abs(atan) == Math.PI)  {
        //we got one!
        numberOfPointsA++;
     }
  });
  maxNumberOfPoints = Math.max(numberOfPointsA, maxNumberOfPoints);
});

console.log("maxNumberOfPoints atan2:", maxNumberOfPoints);

It was close. The missing part was that instead of comparing angles from one point to another (which go from the origin), you'd need to compare angles from two points.

I hacked in a change that will get the right answer on the test set. I think some changes would be necessary on the counter mechanism (what happens if they aren't in order?) and possibly to handle compliments (what happens if there are points on both sides) to get it fully working in all scenarios, but this is the piece that was missing to define a line.

/* line {x,y,dx,dy} */
var points = [{x:1,y:1},{x:2,y:2},{x:1,y:2},{x:1,y:3},{x:1,y:4}];

var maxNumberOfPoints = 1;

points.forEach(function(pointA) {
  var numberOfPointsA = 1;
  var lastAngleAB = false;
  points.forEach(function(pointB) {
     if(pointA == pointB) {
        return;
     }
     var dx = pointB.x - pointA.x;
     var dy = pointB.y - pointA.y;
     var angleAB = Math.atan2(-dy, dx);
     if(!lastAngleAB || angleAB == lastAngleAB)      {
        //we got one!
        numberOfPointsA++;
     }
     console.log(pointA, pointB, numberOfPointsA);
     lastAngleAB = angleAB;
  });
  maxNumberOfPoints = Math.max(numberOfPointsA, maxNumberOfPoints);
});

console.log("maxNumberOfPoints:", maxNumberOfPoints);

Thanks for the help @nfreymuth-telepathy

I guess my brain wasn't firing on all cylinders on Friday. I've changed your code a bit to account for more test cases, instead of tracking only the last angle I needed to keep an object (hash/map) to track the counts at each angle, this now works for all of my test cases:

/*** poor man's test data, all test cases should return 5 ***/
//vertical line test
//var points = [{x:1,y:1},{x:2,y:2},{x:1,y:2},{x:1,y:3},{x:-1,y:4},{x:10,y:0},{x:1,y:-1},{x:1,y:-2}];
//horizontal line test
//var points = [{x:2,y:2},{x:-15,y:2},{x:1,y:2},{x:1,y:1},{x:2,y:2},{x:2000,y:2},{x:1,y:-1},{x:1,y:-2}];
//diag line test, positive x, negative y slope
//var points = [{x:-1,y:3},{x:1,y:-1},{x:0,y:1},{x:-2,y:5},{x:0,y:0},{x:1,y:1},{x:2,y:2},{x:1,y:2},{x:-3,y:7}];
//diag line test, positive x, positive y slope, interspersed points
var points = [{x:-1,y:-3},{x:1,y:1},{x:0,y:-1},{x:-2,y:-5},{x:0,y:0},{x:1,y:1},{x:2,y:2},{x:1,y:2}];

var maxNumberOfPoints = 1;

points.forEach(function(pointA) {
  var angleCounts = {};//indexed by angle, value is number of points at that angle
  points.forEach(function(pointB) {
      if(pointA == pointB) {
        return;
      }
      var dx = pointB.x - pointA.x;
      var dy = pointB.y - pointA.y;
      var angleAB = Math.abs(Math.atan2(dy, dx));
      if(!(angleAB in angleCounts)) {
        angleCounts[angleAB] = 2;
      } else {
        angleCounts[angleAB]++;
      }
      console.log(angleCounts[angleAB], pointA, pointB, dx, dy, angleAB);
  });
  for(var a in angleCounts) {
    maxNumberOfPoints = Math.max(angleCounts[a], maxNumberOfPoints);
  }
});

console.log("maxNumberOfPoints:", maxNumberOfPoints);

I'm not sure what should be returned in the case there are duplicate points, right now it doesn't de-duplicate so it counts dupes towards the max.

Obviously if I was doing this for real I would use a real unit test suite like mocha or tape, but my poor mans un-comment method works for this :)