Punkt auf Ebene der geg Punkt auf Ebene am nähstem

[elchico]

Hallo zusammen,


Ich stehe vor folgendem Problem:
Ich habe eine 2D-Matrix gegeben ((0, 0) - (10,10)) und einen Punkt auf der Matrix (5,5).
Außerdem habe ich verschiedene Linien in dieser Matrix definiert (z.B. Linie [(0,3) - (0,7)] und Linie [(2,4) - (7,4)].

Nun besteht meine Aufgabe darin, die Linie zu finden, deren Start- oder Endwert meinem Punkt (5,5) am nächsten ist (wenn es zwei gleich-weit entfernte Linien gäbe, dürfte ich frei entscheiden).
Anschließend wird mein Punkt(5,5) zu dem Endpunkt der gerade ermittelten Linie und das Spiel geht von vorne los.
Damit soll ich die Liste mit den Linien "sortieren", sodass der kürzeste Weg beschritten wird, wenn ich die Linien nacheinander "ablaufen" solle.


Ich habe keinen Ansatz gefunden...
Über Anregungen wäre ich sehr dankbar
VG
elchico

[BlackJack]

@elchico: Wenn man den insgesamt kürzesten Weg sucht kann man IMHO nicht ”greedy” vorgehen weil es sein könnte das man an einer Stelle einen längeren Schritt wählen muss als den lokal kürzesten um den global kürzesten zu bekommen. Beispiel:

Code: Alles auswählen

            +--b--+
S +-a-+
         +---------------------------c-----------------------------------+

`S` ist der Startpunkt. Da wäre der linke Punkt von `a` am nächsten. Wenn man `a` abgelaufen ist wäre der linke Punkt von `c` am nächsten. Von dessen anderen Ende müsste man dann weit zurückgegen zum rechten Punkt von `b`. Kürzer wäre aber wenn man von `a` erst zum weiter entfernten linken Punkt von `b` springt und vom anderen Ende von `b` dann zum linken Punkt von `c`.

[elchico]

stimmt, soweit hatte ich nicht gedacht.

OK, dann suche ich den absolut kürzesten Weg (also in deinem Beispiel erst a, dann b, dann c)

Hast du auch Ideen zur Umsetzung ?
Wie gesagt, ich komme schon gar nicht dazu, "a" zu finden ... geschweige denn, wie ich den absolut kürzesten Weg finden soll.

[BlackJack]

@elchico: Das lässt sich leicht zu einem Graphenproblem umformulieren. Der Startpunkt und die Liniendendpunkte sind Knoten. Jeder Knoten ist mit jedem anderen Knoten durch eine Kante verbunden. Das Kantengewicht ist die Entfernung zwischen den Punkten die durch die jeweiligen Knoten repräsentiert werden. Jetzt suchen wir den Weg mit dem geringsten Gewicht vom Startpunkt der a) jeden Knoten besucht, b) dabei keine Kante mehr als einmal verwendet, und c) jede Kante die für eine Linie steht beinhaltet. a) und b) sind die üblichen Bedigungen, das heisst man muss eigentlich nur einen Standardalgorithmus adaptieren, so dass auch c) erfüllt ist.

[/me]

Wenn man es nicht zwangsweise selber programmieren muss, dann kann man dafür networkx verwenden.

[BlackJack]

@/me: Wobei ich da jetzt auf Anhieb keine Idee hätte wie man `networkx` die Bedingung c) beibringt, ausser das man wirklich alle Pfade erzeugt und aus denen dann den kürzesten herausfiltert der diese Bedinung erfüllt. Wenn man den Algorithmus selber implementiert, könnte man gezielt bei jedem zweiten Schritt die einzige obligatorische Kante wählen die durch eine Linie in der Aufgabenstellung vorgegeben ist. Zumindest ”algorithmisch” sollte das effizienter sein.

[/me]

Stimmt. Vermutlich es es aufwändiger networkx zu dieser Aufgabe zu überreden als es gleich selber zu machen.

[elchico]

hi

danke zusammen ich schau mir mal networkx an, habe von nem kumpel jetzt auch was von quadtrees gehört...

[BlackJack]

Nahezu ungetestet und extrem unterdokumentiert:

Code: Alles auswählen

#!/usr/bin/env python
from collections import namedtuple
from math import sqrt


def is_odd(number):
    return bool(number & 1)


class Point(namedtuple('_Point', 'x y')):

    def __repr__(self):
        return '{0.__class__.__name__}({0.x!r}, {0.y!r})'.format(self)

    def distance(self, other):
        return sqrt((self.x - other.x)**2 + (self.y - other.y)**2)


Line = namedtuple('Line', 'point_a point_b')


class Node(object):
    
    def __init__(self, point, line=None):
        self.point = point
        self.line = line
        self.line_edge = None
        self.free_edges = dict()

    def __len__(self):
        return len(self.free_edges)

    def __iter__(self):
        return self.free_edges.iteritems()

    def connect_to(self, other):
        if self is not other:
            distance = self.point.distance(other.point)
            if self.line is other.line:
                self.line_edge = (other, distance)
            else:
                self.free_edges[other] = distance

    def connect_to_many(self, others):
        for other in others:
            self.connect_to(other)


class ShortestPathFinder(object):

    def __init__(self, graph):
        self.graph = graph
        self.current_node = None
        self.visited = None
        self.path = None
        self.weight = None
        self.result = None
        self.min_weight = None

    def __call__(self, start_point):
        self.current_node = Node(start_point)
        self.current_node.connect_to_many(self.graph)
        self.visited = set()
        self.path = list()
        self.weight = 0
        self.result = None
        self.min_weight = float('inf')
        self._find_path()
        return self.result

    def _find_path(self):
        if (
            len(self.path) == len(self.graph)
            and self.weight < self.min_weight
        ):
            self.min_weight = self.weight
            self.result = list(self.path)
        else:
            if is_odd(len(self.path)):
                edges = [self.current_node.line_edge]
            else:
                edges = self.current_node

            for target_node, weight in edges:
                if target_node not in self.visited:
                    self.weight += weight
                    if self.weight < self.min_weight:
                        self.current_node = target_node
                        self.visited.add(target_node)
                        self.path.append(target_node)
                        self._find_path()
                        self.visited.remove(target_node)
                        self.path.pop()
                    self.weight -= weight


class Graph(object):
    
    def __init__(self):
        self.nodes = list()

    def __len__(self):
        return len(self.nodes)

    def __iter__(self):
        return iter(self.nodes)

    def _connect_nodes(self):
        for node_a in self:
            node_a.connect_to_many(self)

    def add_node(self, node):
        self.nodes.append(node)

    def iter_shortest_path(self, start_point):
        return (n.point for n in ShortestPathFinder(self)(start_point))

    @classmethod
    def from_lines(cls, lines):
        result = cls()
        for line in lines:
            for point in line:
                result.add_node(Node(point, line))
        result._connect_nodes()
        return result


def iter_shortest_path(lines, start_point):
    return Graph.from_lines(lines).iter_shortest_path(start_point)


def main():
    point = Point(5, 5)
    lines = [
        Line(Point(*a), Point(*b))
        for a, b in [((0, 3), (0, 7)), ((2, 4), (7, 4))]
    ]
    print list(iter_shortest_path(lines, point))


if __name__ == '__main__':
    main()