将多点线（坐标数组）拆分为线段数组的算法

Question

抱歉，如果这有点令人困惑，但我已经坚持了很长时间。我正在开发具有 lat/lng 坐标的地图应用程序。为了简化它，我将使用整数。

假设我有一条 n 点线，其中 n > 0（在本例中 n = 3）。

这条线在代码中表示为 x,y 点数组

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

我需要找到一种方法将其转换为线段数组，其中下一段从最后一段的点开始。

例如，从上一个转换而来的新数组如下所示：

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

我希望这是有道理的。如果 n 为 1、5、200 等，这应该有效。
我只需要算法，所以 psuedocode 可以正常工作。如果你一定要会一门语言，那么 typescript 或 c# 是我最好的。

提前感谢您的任何 help/tips。我很感激。

Answer 1

    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);

输出：

Answer 2

Typescript 版本 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

Answer 3

语言：打字稿

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;
}

插图

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)));

Answer 4

这是经典Fence Post problem。

算法是输出数组中索引i的每一项都是由位置i的元素和输入数组的 i+1 位置的元素。输出数组比输入数组包含 one-fewer 个元素。如果输入数组中有 N 个元素，则输出数组中有 N-1 个元素。

在 JavaScript 中可以像这样巧妙地完成：

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);

这里使用map为原数组中的每一项准备一对。该对由项目及其后的项目组成。我们可以接受这样一个事实，即 JavaScript 语言将通过返回 undefined 来容忍访问超出数组末尾的项目。结果中的最后一项将包含该对中未定义的第二个元素，因为它试图访问刚好超过数组末尾的项目。这是合法的，但不受欢迎，所以我们可以 slice 最后一个元素（删除它）。

可能是最清楚的方法：

大多数强类型语言不允许您访问 N 项数组的索引 N 处的项，因此实际上，使用直接循环或映射构造输出数组，其中 i 来自 0 到 N-2 是最好的，只有索引 [i] 和 [i+1] 处的 select 个项目。

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);

我将上面的内容写为 output[i] = [input[i], input[i + 1]] 和 pre-declared 输出数组的长度，因为这会产生与算法表达方式最匹配的代码。

Answer 5

在 C# 中，这可以用一个简单的 LINQ 表达式来完成：

var result = input.Zip(input.Skip(1)).ToArray();

您将收到一个值元组数组，其中每个元组包含一对点。

在线演示：https://dotnetfiddle.net/b6z0es

Answer 6

我们可以编写一个简单的 aperture 函数，它沿着您的数组移动给定长度（此处 2）的滑动 window：

const aperture = (n) => (xs) => 
  xs .length < n ? [] : [xs .slice (0, n), ... aperture (n) (xs .slice (1))]
  
const result = aperture (2) ([[1, 1], [2, 2], [3, 3]])

console .log (JSON.stringify (result))

这样的函数有很多种写法，其实在之前的三个回答中，我写的是three different implementations。

将多点线（坐标数组）拆分为线段数组的算法

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

javascript

c#

arrays

algorithm

typescript

插图

可能是最清楚的方法：