Home > Mobile >  Algorithm to split a multi-point line (array of coords) into an array of line segments
Algorithm to split a multi-point line (array of coords) into an array of line segments

Time:03-21

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).
enter image description here

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.

CodePudding user response:

    var pts = new[] { (1, 1), (2, 2), (3, 3) };
    var prevPt = pts[0];
    var segments = pts.Skip(1).Select(pt =>
    {
        var seg = new { a = prevPt, b = pt };
        prevPt = pt;
        return seg;
    });
    foreach (var s in segments) Console.WriteLine(s.a   "-"   s.b);

output:

enter image description here

CodePudding user response:

Typescript version FWIW

type Pair<T> = [T, T];
const points: Pair<number>[] = [
  [1, 1],    // E
  [2, 2],    // F
  [3, 3],    // G
];

function buildSegments(points: Pair<number>[]): Pair<number>[][] {
  const collection = [];

  for (let i = 1; i < points.length; i  ) {
    const segment = [
      [
        points[i - 1][0],
        points[i - 1][1]
      ],
      [
        points[i][0],
        points[i][1]
      ]
    ];
    collection.push(segment);
  }

  return collection as Pair<number>[][];
}

console.log(buildSegments(points));

Playground

CodePudding user response:

Language: Typescript

type Point = [number, number];
type LineSegment = [Point, Point];
type LineSegments = LineSegment[];

function calculate_line_segmenmts(points: Point[]) {
    let lineSegments: LineSegments = [];
    if (points && points.length) {
        const pointPairs: LineSegments = points
            .map((currentPoint: Point, currIndex: number) => [currentPoint, points[currIndex   1] || []] as LineSegment);

        lineSegments = pointPairs.slice(0, pointPairs.length - 1);
    }

    return lineSegments;
}

Illustration

function calculate_line_segmenmts(points) {
  let lineSegments = [];
  if (points && points.length) {
    const pointPairs = points
      .map((currentPoint, currIndex) => [currentPoint, points[currIndex   1] || []]);
    lineSegments = pointPairs.slice(0, pointPairs.length - 1);
  }
  return lineSegments;
}
const points = [
  [1, 1],
  [2, 2],
  [3, 3],
  [4, 4]
];
console.log('[Empty Points]', calculate_line_segmenmts([]));
console.log('[1 Point]', calculate_line_segmenmts([
  [1, 2]
])); // <-- Return empty as there is only 1 point, where as a segment requires at least 2
console.log('[2 Points]', '\n', JSON.stringify(calculate_line_segmenmts([
  [1, 2],
  [2, 3]
])));
console.log('[Multiple Points]', '\n', JSON.stringify(calculate_line_segmenmts(points)));

  • Related