2
let input = [
  [[1, 4], [40, 4]],
  [[1, 5], [40, 5]],
  [[4, 7], [4, 24]],
  [[1, 9], [4, 1]],
  [[1, 2], [6, 4]],
  [[80, 4], [90, 4]],
  [[4, 1], [4, 40]],
  [[4, 35], [4, 29]],
  [[4, 28], [4, 35]],
  [[5, 3.6], [9, 5.2]],
]; // Input

Output = [
  [[[1, 4], [40, 4]], [[80, 4], [90, 4]]],
  [[[1, 5], [40, 5]]],
  [[[4, 7], [4, 24]], [[4, 1], [4, 40]]],
  [[[4, 35], [4, 29]], [[4, 28], [4, 35]]],
  [[[1, 9], [4, 1]]],
  [[[1, 2], [6, 4]], [[5, 3.6], [9, 5.2]]],
];

If given an input of series of each start and end coordinates of a line, for example, [[1,4],[40,4]] means that it has 2 points connecting [1,4] and [40,4] to form a straight line. My objective now is to group all those lines which share the same equation y=mx+c, together into a nested array as shown above. For example,

[[1,4],[40,4]] and [[80,4],[90,4]] share the same linear equation y=4

[[4,7],[4,24]],[[4,1],[4,40]]      share the same linear equation x=4

 [[1,2],[6,4]] and [[5,3.6],[9,5.2]]  share the same linear equation y=0.4x+1.6

[[1,9],[4,1]]   is alone and it has the linear equation of -2.67x+11.67

Here is my working codepen demo

I know how to code out to find those m and c in y=mx+c, but the problem is when for example,[[4,7],[4,24]] and [[4,1],[4,40]] , the m gradient becomes infinity which unsolvable.

Can anyone please guide me on this on how to get the correct output?

pilchard
  • 12,414
  • 5
  • 11
  • 23
Theodore John
  • 117
  • 6
  • Before calculating the slope (`m`) test for the `x` values: if they are the same, assign the slope to a categorical value (`foo`) and group those inputs accordingly, otherwise calculate its numerical value. By the way, mathematically you cannot have several image values for the same domain value (that is, those line parallel to the y axis you mentioned), so the best idea is simply eliminating those data arrays. – Gerardo Furtado Feb 08 '23 at 01:13
  • @GerardoFurtado, hello, thanks for replying :), but I cannot eliminate them because I need it. I am working on an app that has vertical and horizontal lines perfectly with gradient can be 0 to 90 :). This gets complicated haha – Theodore John Feb 08 '23 at 01:18
  • Yes, it does. In that case `x = k`, so just test for the `x` values being the same before calculating the slope, and group those cases by their `x` value. And sorry, when I said *"mathematically you can't..."* above I was talking about equations of functions, not the equations themselves. – Gerardo Furtado Feb 08 '23 at 01:19
  • @GerardoFurtado, thats smart. But if the gradient is too steep, it will cause the gradient to be of vey large which leads to inaccuracy sometimes. I am thinking of you know seperate those gradient 0 to 45 to an array and seperate those gradient 45 to 90 to a seperate array again. Then we have got the equation y=mx+c and x=my+c, this makes the gradient in both casses to be always less than 45 degree (Always Less than 1) :) – Theodore John Feb 08 '23 at 01:24

2 Answers2

2

You can calculate the slope equation for each set of points and assign it to each array item, then group:

const input=[[[1,4],[40,4]],[[1,5],[40,5]],[[4,7],[4,24]],[[1,9],[4,1]],[[1,2],[6,4]],[[80,4],[90,4]],[[4,1],[4,40]],[[4,35],[4,29]],[[4,28],[4,35]],[[5,3.6],[9,5.2]]];

const inputsWithSlope = input.map((points) => {
  const [[x, y], [x1, y1]] = points;
  const slope = (y1 - y) / (x1 - x)
  const b = y1 - slope * x1
  return {
    points,
    line: x1 == x ? `x = ${x}` : `y = ${slope}x + ${b}`
  }
})

const res = inputsWithSlope.reduce((acc, curr) => {
  const accProp = acc[curr.line]
  acc[curr.line] = !accProp ? [curr.points] : [...accProp, curr.points]
  return acc
}, {})
const result = Object.values(res)
result.forEach(e => console.log(JSON.stringify(e)))

To deal with the rounding issue, you'll have to round it:

const input=[[[1,4],[40,4]],[[1,5],[40,5]],[[4,7],[4,24]],[[1,9],[4,1]],[[1,2],[6,4]],[[80,4],[90,4]],[[4,1],[4,40]],[[4,35],[4,29]],[[4,28],[4,35]],[[5,3.6],[9,5.2]]];

const inputsWithSlope = input.map((points) => {
  const [[x, y], [x1, y1]] = points;
  const slope = (y1 - y) / (x1 - x)
  const b = y1 - slope * x1
  return {
    points,
    line: x1 == x ? `x = ${x}` : `y = ${slope.toFixed(2)}x + ${b.toFixed(2)}`
  }
})

const res = inputsWithSlope.reduce((acc, curr) => {
  const accProp = acc[curr.line]
  acc[curr.line] = !accProp ? [curr.points] : [...accProp, curr.points]
  return acc
}, {})
const result = Object.values(res)
result.forEach(e => console.log(JSON.stringify(e)))
Spectric
  • 30,714
  • 6
  • 20
  • 43
  • Hello, I think there is a bug in your code. [[1,2],[6,4]] and [[5,3.6],[9,5.2]] was not group together in an array ? :) They share the same equation m=0.4 with c=1.6 to form y=mx+c – Theodore John Feb 08 '23 at 02:02
  • floating point... `1.5999999999999996` vs `1.6`. You're going to have to round to a sane decimal. see [How to deal with floating point number precision in JavaScript?](https://stackoverflow.com/questions/1458633/how-to-deal-with-floating-point-number-precision-in-javascript) and the perennial [Is floating point math broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) – pilchard Feb 08 '23 at 02:03
  • @TheodoreJohn It seems to be working in the snippet. They are grouped together. – Spectric Feb 08 '23 at 02:04
  • @TheodoreJohn OK. I've updated my answer to round the decmials (as pilchard suggested). – Spectric Feb 08 '23 at 02:07
  • 2 is pretty conservative and has it's own problems, worth reading the linked questions for more precise control. – pilchard Feb 08 '23 at 02:10
  • @Spectric, hi, thanks for updating :), your output is perfect but its a string, can it be converted to a nested array with numbers in it? – Theodore John Feb 08 '23 at 02:10
  • @TheodoreJohn `result` is the nested array. I'm just printing out each item line by line so it's easier to read. – Spectric Feb 08 '23 at 02:11
  • right, got it :) – Theodore John Feb 08 '23 at 02:13
  • 1
    @Hi, it works fine now , thank you :), now I can proceed with my app haha – Theodore John Feb 08 '23 at 02:15
0

Here's my take at it. The strategy is to first get a description of the line for each pair of points, and then group those together into a map of maps, first keyed by slopes, and then by intercepts (either x or y, depending on if the line is vertical or not), and then extract the groups into a single array.

let input=[ [[1,4],[40,4]] , [[1,5],[40,5]] , [[4,7],[4,24]] ,[[1,9],[4,1]], [[1,2],[6,4]], [[80,4],[90,4]] , [[4,1],[4,40]] , [[4,35],[4,29]] , [[4,28],[4,35]] ,[[5,3.6],[9,5.2]] ] ; 

// a function to get the slope and intercept of the line formed by a pair of points
function describeLine([[x1, y1], [x2, y2]]) {
  if (x1 == x2) { // vertical line
    return {m: "vertical", x: x1}
  }
  const p1 = x1 > x2 ? { x: x1, y: y1 } : { x: x2, y: y2 }
  const p2 = x1 < x2 ? { x: x1, y: y1 } : { x: x2, y: y2 }
  
  const m = (p1.y - p2.y) / (p1.x - p2.x)
  const y = y1 - m * x1
  return { m, y }
}

// this runs through the input array and accumulates all the pairs of points into a dictionary structure keyed by slope and then intercept
// so for a line with slope 2 and y-intercept 3, it would go into the map at { 2 : { 3: [[ [point 1], [point2]] ], [ line 2 with same props] ...
const maps = input.reduce((acc, line) => {
    const desc = describeLine(line)
    const m = acc[desc.m] || { }
    if (desc.x) { // vertical line
      x = m[desc.x] || []
      return { ...acc, [desc.m]: { ...m, [desc.x]: [ ...x, line ]}}
    } else {
      y = m[desc.y] || []
      return { ...acc, [desc.m]: { ...m, [desc.y]: [ ...y, line ]}}
    }
}, {})

// once we've accumulated that structure, we can just collect the individual arrays into one big array
const sameLines = Object.values(maps).flatMap(Object.values)
console.log(JSON.stringify(sameLines, null, 2))
anqit
  • 780
  • 3
  • 12