Eliminate Items From Array To Reach Fixed Length - JavaScript

user_3289949 0
Viewed 123

I am trying to write a JavaScript function that removes items from an array to reach a defined length. The function should eliminate the "gaps" evenly through the array. I need this function to simplify polygon vertices for canvas drawing.

This is how it should work:

enter image description here

This is the code I came up with:

function simplify(array, vertices) {

  // Calculate gap size
  var gap = array.length - vertices;
  gap = Math.floor(array.length / gap);

  var count = 0;
  var result = [];

  // Fill a new array
  for (var i = 0; i < array.length; i++) {
    if (count == gap) {
      count = 0;
    } else {
      result.push(array[i]);
      count++;
    }
  }

  // Eliminate 1 item in the middle if length is odd
  if (result.length > vertices) {
    result.splice(Math.floor(result.length / 2), 1);
  }
  return result;
}

// This gives the wrong result depending on the length of the input!
// The result should be an array with the length of 3
console.log(simplify([
  { x: 10, y: 20 },
  { x: 30, y: 40 },
  { x: 40, y: 50 },
  { x: 50, y: 60 }
], 3))

However, this only seems to work sometimes and the problem may be in the math. What's the algorithm that can achieve this or what am I doing wrong?

math canvas geometry arrays javascript
3 Answers

Maybe this will help

Suppose you have a string of length n, and you want it to be length m. You have n-2 elements to pick from, and m-2 elements to pick for your new array. Now, suppose you have currently picked i elements and have passed j elements. If i/j < (m-2)/(n-2) then you are behind. You probably ought to take another element. What you really want to know, for a maximally even selection, is whether (i+1)/(j+1) or i/(j+1) is closer to your target of (m-2)/(n-2). If overflow isn't a problem, you can do a little algebra to figure out that this is equivalent to whether (i+1)(n-2) - (j+1)(m-2) is more or less than (n-2)/2; more means i is better (so don't take this one), while less means i+1 is better.

user_60980090

I solved this in the same way I do nearest-neighbor texture lookups. The floating point step variable (greater than zero) is floored to the next lower index, but when 'floor(i*step)' is greater than 'i' it takes it's first jump.

   function simplify(array, vertices){

      vertices = vertices || 1;///No div by zeros please :)

      var result = [];

      var step = array.length/vertices;

      for(var i=0;i<vertices;i++){
         result.push(array[Math.floor(step*i)]);
      }

      return result;

   }


//Testing it out
   var testarr = [];

   for(var ai=0;ai<51;ai++){
      testarr[ai] = {
         x:ai,
         y:10*ai
      }
   }

   console.log(testarr.slice(0));

   var ret = simplify(testarr, 29);

   console.log(ret.slice(0));

Incidentally,

   function simplify_bilinear(array, vertices){

      var result = [];

      var step = array.length/vertices;

      for(var i=0;i<vertices;i++){
         var fistep = Math.floor(i*step);//The nearest neighbor index
         var current = array[fistep];//This element
         var next = array[fistep+1];//The next element
         var mix = (i*step)-fistep;//The fractional ratio between them. As this approaches 1, the mix approaches the next value.
         //mix = mix * mix * (3 - 2 * mix);//Optional (s-curve) easing between the positions. Better than linear, anyway.
         //Alternately to the above//mix = Math.sin((mix*2 - 1)*Math.PI)*.5+.5;///for a sinusoid curve
         //True Bezier would be optimal here but beyond this scope 
         var mixed_point = {
            x:current.x+(next.x-current.x)*mix,//basic mixing, ala 'mix' in your average math library
            y:current.y+(next.y-current.y)*mix,
         }
         result.push(mixed_point);
      }

      return result;

   }

is a bilinear mag-filter, if you would ever like to up the count instead of lowering it. This could branch if the desired-length('vertices') is greater than the 'array.length'. Also a useful algorithm for software audio synth.

user_49271580

If you just want to eliminate items to cut that array to a desired length. Use the Array.splice() function.

So if your desiredLength = 3 for example. And you have an array = [1,2,3,4,5].

array.splice(0,desiredLength).length == desiredLength should be true.

user_27019520
Related