[SOLVED] Algorithm to split a multi-point line (array of coords) into an array of line segments

Issue

Sorry if this is kind of confusing but I’ve been stuck on this for a long time. I’m working on a mapping application with lat/lng coordinates. To simplify it, I’ll use whole numbers.

Let’s say I have an n point line where n > 0 (in this case n = 3).

This line is represented in code as an array of x,y points

[
   [1, 1]    // E
   [2, 2]    // F
   [3, 3]    // G
]

I need to find a way to convert this into an array of line segments where the next segment starts at the point of the last one.

For example, the new array converted from the last would look like this:

[
   [            //Line segment 1
      [1, 1]    // Point E
      [2, 2]    // Point F
   ],
   [            //Line segment 2
      [2, 2]    // Point F
      [3, 3]    // Point G
   ]
]

I hope this makes sense. This should work if n is 1, 5, 200, etc.
I just need the algorithm so psuedocode works fine. If you must have a language than typescript or c# are my best ones.

Thank you in advance for any help/tips. I appreciate it.

Solution

This is a classic Fence Post problem.

The algorithm is that each item at index i in the output array is a pair consisting of the element at position i and the element at position i+1 of the input array. The output array contains one-fewer elements than the input array. If there are N elements in the input array there are N-1 elements in the output array.

In JavaScript it can be done with some cleverness like this:

const input = [
  [1, 1],
  [2, 2],
  [3, 3]
];

const output = input.map((_, i, a) => [a[i], a[i + 1]]).slice(0, -1);

console.log(output);

Here map is used to prepare a pair for each item in the original array. That pair consists of the item and the item after it. We can embrace the fact that the JavaScript language will tolerate accessing items beyond the end of the array by returning undefined. The last item in the result will contain an undefined second element of the pair as it tries to access the item just past the end of the array. This is legal, but undesired, so we can just slice that last element away (remove it).

Probably the most clear way:

Most strongly typed languages will not permit you to access the item at index N of an array of N items, so really, constructing your output array with a straightforward loop or map where i goes from 0 to N-2 is best and just select items at index [i] and [i+1] for your pair.

const input = [
  [1, 1],
  [2, 2],
  [3, 3]
];

const output = new Array(input.length - 1);
for (let i = 0; i < input.length - 1; ++i)
  output[i] = [input[i], input[i + 1]];

console.log(output);

I wrote the above as output[i] = [input[i], input[i + 1]] and pre-declared the length of the output array because this yields code that most closely matches the way the algorithm is expressed.

Answered By – Wyck

Answer Checked By – David Marino (BugsFixing Volunteer)