Как отсортировать MultiLineString? - PullRequest
Новая
       14

Как отсортировать MultiLineString?

0 голосов
/ 30 апреля 2018

У меня есть MultiLineString, состоящая из отдельных LineStrings, которые образуют путь. Путь имеет направление, и LineStrings должны быть отсортированы, чтобы отразить этот порядок. Для этого некоторые строки должны быть обращены, чтобы указывать в том же направлении, что и остальные. Какой будет подходящий алгоритм для решения этой задачи?

Другими словами, как лучше всего отсортировать список списков, где списки можно перевернуть? Т.е.

Введите: 

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

Выход: 

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

Ответы [ 3 ]

0 голосов
/ 17 мая 2018

Не найдя решения, я закончил тем, что написал этот алгоритм. Это делает работу, но может лучше обрабатывать ветви, т.е. выберите ветку, которая дала бы самый длинный непрерывный путь. Теперь он просто прилипает к первому отрезку и продолжает оттуда.

Учитывая геометрию 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
0 голосов
/ 27 февраля 2019

Несмотря на то, что вопрос требует решения на Python, и поскольку я попал на эту страницу с помощью поиска DuckDuckGo, пытаясь найти способ решить эту проблему (сортировка сегментов по геометрии GeoJson MultiLineString), я думаю, что Java / Kotlin решение может быть оценено другими людьми, попадающими сюда.

Изначально я придумал собственное решение, которое похоже на @kissaprofeetta. Хотя я подхожу к этому с некоторыми отличиями:

  • Алгоритм расстояния, который я использую, немного более точен и предназначен для использования в целях геолокации, поскольку он учитывает, что Земля - ​​это не 2D-плоскость / карта, а сфера. Фактически, данные высот также могут быть легко добавлены, чтобы быть еще более точными.
  • Способ добавления сегментов в новый массив MultiLineString немного менее изящен, чем ответ @kissaprofeetta

  • Я добавил чтение файлов 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))
}
0 голосов
/ 01 мая 2018

Sorted() со списком

Ex: 

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]]
...