如何对MultiLineString进行排序？

Question

我有一个MultiLineString，由形成路径的各个LineStrings组成。路径具有方向，并且必须对LineStrings进行排序以反映此顺序。要做到这一点，必须颠倒一些字符串以指向与其余字符串相同的方向。什么是合适的算法来完成这项任务？

换句话说，对列表列表进行排序的最佳方法是什么，列表可以反转？即

输入：

[2, 1] [4, 5] [0, 1] [5, 6] [9, 8]

输出：

[0, 1] [1, 2] [4, 5] [5, 6] [8, 9] 

Answer 1

Sorted()与列表理解

例如：

l = [[2, 1] ,[4, 5], [0, 1], [5, 6], [9, 8]]
print(sorted([sorted(i) for i in l]))

输出：

[[0, 1], [1, 2], [4, 5], [5, 6], [8, 9]]

Answer 2

由于未能找到解决方案，我最终编写了这个算法。它完成了这项工作，但可以更好地处理分支，即。选择会产生最长连续路径的分支。现在它只是坚持第一线段并从那里继续。

给定GeoJSON MultiLineString几何，算法将线段排序为连续路径并返回新几何。

该代码根据您想要公共许可证做什么来获得许可。

import math
from collections import namedtuple
from operator import attrgetter 
from copy import deepcopy


def arrange_geometry(original_geometry):
    def distance(coords1, coords2):
        return math.sqrt(math.pow(coords1[0] - coords2[0], 2) + math.pow(coords1[1] - coords2[1], 2))

    MinDistance = namedtuple('MinDistance', 'target distance offset reverse_target')
    geometry = deepcopy(original_geometry)

    if geometry['type'] == 'MultiLineString':
        lines = geometry['coordinates']
        sorted_multistring = [lines.pop(0)]

        while lines:
            min_distances = []

            for line in lines:
                source_a = sorted_multistring[0][0]
                source_b = sorted_multistring[-1][-1]

                target_a = line[0]
                target_b = line[-1]

                distances = [
                    MinDistance(target=line, distance=distance(source_b, target_a), offset=1, reverse_target=False),
                    MinDistance(target=line, distance=distance(source_a, target_a), offset=-1, reverse_target=True),
                    MinDistance(target=line, distance=distance(source_b, target_b), offset=1, reverse_target=True),
                    MinDistance(target=line, distance=distance(source_a, target_b), offset=-1, reverse_target=False)
                ]

                min_distance = min(distances, key=attrgetter('distance'))
                min_distances.append(min_distance)

            min_distance = min(min_distances, key=attrgetter('distance'))
            target = min_distance.target

            if min_distance.reverse_target:
                target.reverse()

            if min_distance.offset == 1:
                sorted_multistring.append(target)
            else:
                sorted_multistring.insert(0, target)

            lines.remove(target)

        geometry['coordinates'] = sorted_multistring

    return geometry

Answer 3

即使这个问题需要Python解决方案，并且我通过DuckDuckGo搜索到达此页面试图找到解决此问题的方法（在GeoJson MultiLineString几何上对段进行排序），我认为Java / Kotlin解决方案可能是得到其他人的赞赏。

我最初提出了一个我自己的解决方案，它恰好类似于@kissaprofeetta。虽然我接近它但有一些不同之处：

• 我使用的距离算法更精确，旨在用于地理位置，因为它考虑到地球不是2D平面/地图，而是球体。实际上，高程数据也可以轻松添加，甚至更精确。
• 将段添加到新的MultiLineString数组的方式比@kissaprofeetta回答的要简单一点
• 我已经添加了GeoJson文件的读取和已排序的GeoJson的编写 qazxsw poi