Reducing code duplication in a geometric function

Given a large bounding rectangle ("envelope"), a list of points, and a maximal aspect ratio, the goal is to find a rectangle within the envelope, whose aspect ratio is bounded within the given aspect ratio, that contains a largest number of points from the list.

For example: if the envelope is the rectangle with corners (0,0) and (80,200), and the points are {(0,0),(0,60),(0,100),(0,140),(0,200)}, and the maximum aspect ratio is 1, then a possible solution is the square: with corners (0,60) and (80,140), that contains 3 of the points in the list.

My algorithm is relies on the following observation: suppose the envelope is taller than it is long (i.e. its y span is larger than its x span, as in the example). Then an optimal square can always contain the entire x span; the only thing to determine is the optimal y span. So, I just loop over all unique y values of the points, and look for the minimal y value that gives a square with the largest number of points.

If the envelope is longer than it is tall (i.e. its y span is larger than its x span, as in the example), then the exact same algorithm should work, only this time we should loop over the y values.

And here is my problem: the implementation (shown below) contains two exact duplicates of the same algorirthm, with the only difference being that x in one version becomes y in the other version and vice versa.

My question is: is there a way to prevent this duplication?

```
var _ = require("underscore");

/**
* @param points array of points, e.g. [{x:0,y:0}, {x:100,y:100}, etc.]
* @param envelope defines the bounding rectangle, e.g. {minx: 0, maxx: 100, miny: 0, maxy: 200}
* @param maxAspectRatio number>=1: the maximum width/height ratio of the returned rectangle.
* @return a rectangle contained within the envelope, with aspect ratio at most maxAspectRatio, that contains a largest number of points.
*/
var squareWithMaxNumOfPoints = function(points, envelope, maxAspectRatio) {
if (!maxAspectRatio) maxAs

The obvious solution is move the max-point-coverage logic into a function, and then call it with an array of just the x or y values, the min/max boundaries, and the "span" (i.e. largest width/height allowed).

In other words, start by checking if the square can perfectly cover the envelope, like you do now, and if it can, you're done. If not, start by filtering the points to remove those that fall outside the envelope in either dimension before proceeding. Right now, you're only discarding point based on either its x or y coordinate, which means you might end up finding points you shouldn't.

For instance, if the envelope is (0, 0) (200, 100), and there's a single point (100, 300), you'd find it because it's x coordinate is well within 0-200, and that's the only thing you filter. But its y coordinate is way off.

So, given a list of points contained in the envelope, you can focus on either x or y coordinates, as needed. That means starting by plucking the x or y properties from the (already filtered) points array, and passing it on to the aforementioned function.

Update 1: You can't use uniq on the 1D values, as it'll make points that lie on the same line count as just 1 point. Hence, you're not guaranteed to actually find the square containing the most points, since it'd favor 5 scattered points over 10 points that lie in a line.

Also, added a quick demo.

Update 2: Fixed a bug in my code that would cause the while loop to "give up" immediately in some situations. I've update the code, and the demo link above

I'd suggest something like this:

function findBounds(values, minValue, maxValue, span) {
  var offset = minValue,
      maxCount = 0,
      lowerBoundary,
      upperBoundary,
      prevValue,
      i, l;

  values = values.slice(0).sort(function (a, b) { return a -b; });

  // optimization: If there aren't enough points left to
  // beat the maxCount we don't have to bother looking.
  while(values.length > maxCount) {
    lowerBoundary = values.shift();

    if(lowerBoundary === prevValue) {
      continue; // skip if value is the same as the previous one
    }
    prevValue = lowerBoundary;

    upperBoundary = Math.min(lowerBoundary + span, maxValue);

    // similar optimization; stop once we exceed
    // the upperBoundary value, and see how far we got
    for( i = 0, l = values.length ; i  upperBoundary ) {
        break;
      }
    }

    if( 1 + i > maxCount ) { // add 1 because we shifted the array
      offset = Math.min(lowerBoundary, maxValue - span);
      maxCount = 1 + i;
    }

    if(lowerBoundary + span > maxValue) {
      break; // no need to keep looking if we'd exceed the bounding box
    }
  }

  return {
    min: offset,
    max: offset + span,
    count: maxCount
  };
}

Which can use like so (for x, as an example):

var values = points.pluck("x");
    bounds = findBounds(values, envelope.minx, envelope.maxx, largestWidthPerHeight),
    result = {
      minx: bounds.min,
      maxx: bounds.max,
      miny: envelope.miny,
      maxy: envelope.maxy
    };

And "vice-versa" for y.

StackExchange Code Review Q#46531, answer score: 4