CODEWITHSUNDEEP
javascript
mx_code
mx_code

Reputation: 2517

How to do a recursive call for finding the sum of elements in an array of points?

The idea is to find the mid point of a bezeir curve. Following is the De Casteljau's algorithm for finding the midpoint of a curve with four points.

How can I implement such an algorithm in javascript using recursion?

Following is the four starting points. From here we start the algorithm and through recursion we arrive the tip of the tree.

(0, 0)
      \
       (1/2, 0) --> this node is calculated as follows [(x1 + x2)/2, (y1 + y2)/2]
      /        \
(1, 0)          (3/4, 1/4)
      \        /          \
       (1, 1/2)            (3/4, 1/2)
      /        \          /
(1, 1)          (3/4, 3/4)
      \        /
       (1/2, 1)
      /
(0, 1)

for example the sample input of points will be like this

const points = [[0,2], [4,5], [6,7], [3,8]]

output = [3,5]

// so the output will be just an array of two numbers for eg: [3,5] (just a rough figure for demo) which represents the midpoint of the above four points obtained by the above algorithm.

This is what I've tried. But it is entirely wrong. Can someone help?

    const mid = (array) => {
      if (array.length === 1) 
        return array
      else {
        array.map(point => [point[0] + point[1] + point[2]])
      }
    }

UPDATE

Remember each node is calculated as follows [(x1 + x2)/2, (y1 + y2)/2]. i.e., by taking the average of similar coordinates of two adjacent points.= .

UPDATE

The second code suggested by Nina Scholz works fine.

But I want to extend it further. Ninas code returns the first midpoint. But I want to extend it to find more points as illustrated below.

enter image description here

Upvotes: 4

Views: 189

Answers (3)

Nenad Vracar
Nenad Vracar

Reputation: 122047

You could do this with reduce and map which will work for the sub-arrays of any sizes assuming you they are of the same length.

const points = [[0,2], [4,5], [6,7], [3,8]]

function calc(data) {
  if (data.length == 1) return data;

  const points = data.reduce((r, e, i, a) => {
    if (a[i + 1]) r.push(e.map((n, j) => (n + a[i + 1][j]) / e.length))
    return r;
  }, [])

  return calc(points)
}

const result = calc(points);
console.log(result)

Upvotes: 1

MattM
MattM

Reputation: 11

Seems like a good use for the Reduce array method.

     array.reduce((acc, cur) => {
            return [(acc[0] + cur[0])/2, (acc[1] + cur[1])/2]
        })

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386600

You could take a recursive approach and get a single pair.

This approach takes only integer values.

const
    getB = array => {
        if (array.length === 1) return array[0];

        const result = [];

        for (let i = 1; i < array.length; i++) {
            result.push([Math.floor((array[i - 1][0] + array[i][0]) / 2), Math.floor((array[i - 1][1] + array[i][1]) / 2)]);
        }        

        return getB(result);
    },
    points = [[0, 2], [4, 5], [6, 7], [3, 8]];

console.log(getB(points));

Same approach without using integer values.

const
    getB = array => {
        if (array.length === 1) return array[0];

        const result = [];

        for (let i = 1; i < array.length; i++) {
            result.push([(array[i - 1][0] + array[i][0]) / 2, (array[i - 1][1] + array[i][1]) / 2]);
        }        

        return getB(result);
    },
    points = [[0, 2], [4, 5], [6, 7], [3, 8]];

console.log(getB(points));

Upvotes: 2

Related Questions