Python 中没有重叠的路径连接点

Question

我想要一个像这样连接点的路径： enter image description here

根据我的尝试，这是我在 Python 中能够实现的结果： enter image description here

看起来很简单。可能吗？

Answer 1

你每次都让线路以最短路径从一个点连接到另一个点吗？看起来是这样的。我建议你标记你放置的每个点，这样你就可以按照你放置所有东西的方式连接所有东西。

Answer 2

看起来像旅行商问题。我上网查了一下，发现了一个关于旅行商问题的图书馆。 https://pypi.org/project/python-tsp/。它应该可以创建有效的非重叠路线。一旦它给你一个排列，使用这些点并组织你的新点列表。

示例：

points2=[]
for i in permutation:
    points2.append(points[i])

之后，你可以绘制points2。

Answer 3

points=[[2031.0974638138432, 8871.788899127823],
 [1946.0939073523768, 8687.702718346474],
 [1868.9610243990464, 8542.951197953029],
 [2061.006139498597, 8393.47953820238],
 [2163.3253106537886, 8264.46188196409],
 [2541.119051912334, 8232.994153653774],
 [2785.1108448732557, 8292.782817554034],
 [2967.711185007007, 8424.947266512696],
 [2967.711185007007, 8602.739911576653],
 [2709.552146487491, 8752.211571327301],
 [2429.355105791343, 8808.853442507185],
 [2150.732166552858, 8744.34463924972],
 [2087.7665291581216, 8531.937522878434],
 [2402.594716131818, 8379.319070407408],
 [2638.7157524747163, 8461.135134180222],
 [2446.670637375166, 8541.377851316203],
 [2492.849155914053, 8630.642922304622],
 [2444.788613747456, 8669.072915834848],
 [2366.462005771966, 8620.088463227232]]

starting=5



import math
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model(points,starting):
    """Stores the data for the problem."""
    data = {}
    # Locations in block units
    data['locations'] = points  
    data['num_vehicles'] = 1
    data['depot'] = starting
    return data


def compute_euclidean_distance_matrix(locations):
    """Creates callback to return distance between points."""
    distances = {}
    for from_counter, from_node in enumerate(locations):
        distances[from_counter] = {}
        for to_counter, to_node in enumerate(locations):
            if from_counter == to_counter:
                distances[from_counter][to_counter] = 0
            else:
                # Euclidean distance
                distances[from_counter][to_counter] = (int(
                    math.hypot((from_node[0] - to_node[0]),
                               (from_node[1] - to_node[1]))))
    return distances


def print_solution(manager, routing, solution):
    """Prints solution on console."""
    index = routing.Start(0)
    plan_output = []
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output.append(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
   
    return plan_output
    


def main(points,starting=0):
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model(points,starting)

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(len(data['locations']),
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    distance_matrix = compute_euclidean_distance_matrix(data['locations'])

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        return print_solution(manager, routing, solution)


if __name__ == '__main__':
    permutation = main(points,starting=starting)
    points2=[]
    for i in permutation:
        points2.append(points[i])
    x,y = map(list,zip(*points2))
    from matplotlib import pyplot as plt
    plt.plot(x,y,'-o')

Python 中没有重叠的路径连接点

Path Connecting Points without overlapping in Python

python

shortest-path

shapely