如何排序多行？

Question

我有一个由形成路径的单独的线串组成的多重线串。路径具有方向，必须对字符串进行排序以反映此顺序。要做到这一点，一些字符串必须反向指向与其他字符串相同的方向。 做这项任务的合适算法是什么？在

换言之，对列表进行排序的最佳方法是什么？在这种方法中，列表可以反转？Ie公司

输入：

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

输出：

^{pr2}$

Answer 1

Sorted()使用列表理解

例如：

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

输出：

^{pr2}$

Answer 2

由于找不到解决方案，我最终编写了这个算法。它可以完成任务，但可以更好地处理分支，即选择产生最长连续路径的分支。现在它只停留在第一条线段上，然后从这里开始。在

给定一个GeoJSON多行字符串几何体，该算法将线段排序为连续路径并返回一个新的几何体。在

代码是在DoWhat The F*ck You Want To Public许可证下授权的。在

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多行字符串几何体上对段进行排序），我认为Java/Kotlin解决方案可能会受到其他人的欢迎。在

我最初想出了一个我自己的解决方案，碰巧有点类似于@kissaprofetta。尽管我在方法上有一些不同之处：

• 我使用的距离算法更精确一点，用于地理定位，因为它考虑到地球不是二维平面/地图，而是一个球体。事实上，可以很容易地添加高程数据，更精确地说。在
• 向新的多行数组添加段的方法比@kissaprofeetta answer要少一些

• 我已经添加了GeoJson文件的读取和已排序GeoJson的写入

  import com.google.gson.Gson
  import com.google.gson.GsonBuilder
  import org.xml.sax.SAXException
  import java.io.File
  import java.io.IOException
  import java.io.PrintWriter
  import javax.xml.parsers.ParserConfigurationException
  
  const val ADDITION_MODE_BEGINNING_TO_BEGINNING = 0
  const val ADDITION_MODE_BEGINNING_TO_END = 1
  const val ADDITION_MODE_END_TO_BEGINNING = 2
  const val ADDITION_MODE_END_TO_END = 3
  
  data class MultiLineString2(
      val type: String,
      val coordinates: ArrayList<ArrayList<ArrayList<Double>>>
  )
  
  fun sortSegmentsOfGeoJsonRoute(routeId: Int)
  {
      try {
          val gson = GsonBuilder().setPrettyPrinting().create()
          val geoJsonRoute = gson.fromJson(
              File("src/main/assets/geojson/" + routeId + ".geojson").readText(),
              MultiLineString2::class.java
          )
          val newTrackSegments = ArrayList<ArrayList<ArrayList<Double>>>()
          newTrackSegments.add(geoJsonRoute.coordinates.first())
  
          geoJsonRoute.coordinates.forEach { newSegment ->
              if (!newTrackSegments.contains(newSegment)) {
                  var existingSegmentAsReference: ArrayList<ArrayList<Double>>? = null
                  var minDistanceToNewSegment = Double.MAX_VALUE
                  var additionMode = 0
  
                  newTrackSegments.forEach { existingSegment ->
                      val existingSegmentEnd = existingSegment.lastIndex
                      val newSegmentEnd = newSegment.lastIndex
                      val distFromBeginningToBeginning = distance(existingSegment[0][1], newSegment[0][1], existingSegment[0][0], newSegment[0][0])
                      val distFromBeginningToEnd = distance(existingSegment[0][1], newSegment[newSegmentEnd][1], existingSegment[0][0], newSegment[newSegmentEnd][0])
                      val distFromEndToBeginning = distance(existingSegment[existingSegmentEnd][1], newSegment[0][1], existingSegment[existingSegmentEnd][0], newSegment[0][0])
                      val distFromEndToEnd = distance(existingSegment[existingSegmentEnd][1], newSegment[newSegmentEnd][1], existingSegment[existingSegmentEnd][0], newSegment[newSegmentEnd][0])
  
                      var curMinDistance = Math.min(distFromBeginningToBeginning, distFromBeginningToEnd)
                      curMinDistance = Math.min(curMinDistance, distFromEndToBeginning)
                      curMinDistance = Math.min(curMinDistance, distFromEndToEnd)
  
                      if (curMinDistance <= minDistanceToNewSegment) {
                          minDistanceToNewSegment = curMinDistance
  
                          when (curMinDistance) {
                              distFromBeginningToBeginning -> additionMode = ADDITION_MODE_BEGINNING_TO_BEGINNING
                              distFromBeginningToEnd -> additionMode = ADDITION_MODE_BEGINNING_TO_END
                              distFromEndToBeginning -> additionMode = ADDITION_MODE_END_TO_BEGINNING
                              distFromEndToEnd -> additionMode = ADDITION_MODE_END_TO_END
                          }
  
                          existingSegmentAsReference = existingSegment
                      }
                  }
  
                  addTrackSegment(existingSegmentAsReference, additionMode, newSegment, newTrackSegments)
              }
          }
          val sortedGeoJsonRoute = MultiLineString2("MultiLineString", newTrackSegments)
  
          val geoJsonRouteWriter = PrintWriter("src/main/assets/geojson/" + routeId + "-sorted.geojson")
          geoJsonRouteWriter.append(gson.toJson(sortedGeoJsonRoute))
          geoJsonRouteWriter.close()
      } catch (ex: ParserConfigurationException) { }
      catch (ex: SAXException) { }
      catch (ex: IOException) { }
      catch (ex: Exception) {
          print(ex.localizedMessage)
      }
  }
  
  private fun addTrackSegment(
      existingSegmentAsReference: ArrayList<ArrayList<Double>>?,
      additionMode: Int,
      newSegment: ArrayList<ArrayList<Double>>,
      newTrackSegments: ArrayList<ArrayList<ArrayList<Double>>>
  ) {
      if (existingSegmentAsReference != null) {
          when (additionMode) {
              ADDITION_MODE_BEGINNING_TO_BEGINNING -> {
                  val segmentToBeAdded = newSegment.reversed() as ArrayList<ArrayList<Double>>
                  val indexWhereToAddNewSegment = Math.max(0, newTrackSegments.indexOf(existingSegmentAsReference))
  
                  newTrackSegments.add(indexWhereToAddNewSegment, segmentToBeAdded)
              }
              ADDITION_MODE_BEGINNING_TO_END -> {
                  val indexWhereToAddNewSegment = Math.max(0, newTrackSegments.indexOf(existingSegmentAsReference))
  
                  newTrackSegments.add(indexWhereToAddNewSegment, newSegment)
              }
              ADDITION_MODE_END_TO_BEGINNING -> {
                  newTrackSegments.add(newSegment)
              }
              ADDITION_MODE_END_TO_END -> {
                  newTrackSegments.add(newSegment.reversed() as ArrayList<ArrayList<Double>>)
              }
          }
      }
  }
  
  fun distance(lat1: Double, lat2: Double, lon1: Double, lon2: Double): Double
  {
      val earthRadius = 6371
  
      val latDistance = Math.toRadians(lat2 - lat1)
      val lonDistance = Math.toRadians(lon2 - lon1)
      val a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2) + (Math.cos(Math.toRadians(lat1)) * Math.cos(
          Math.toRadians(lat2)
      ) * Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2))
      val c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a))
      val distance = earthRadius.toDouble() * c * 1000.0
  
      /* If you add el1 and el2 parameters, as elevation, then you coud make this change to take it in account for the distance. You'll have to remove, obviously, the return line that is now below this multiline comment
          val height = el1 - el2
          distance = Math.pow(distance, 2.0) + Math.pow(height, 2.0)
          return Math.sqrt(distance) */
  
      return Math.sqrt(Math.pow(distance, 2.0))
  }