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

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
elchico
User
Beiträge: 29
Registriert: Dienstag 10. März 2015, 00:06

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
User
Beiträge: 29
Registriert: Dienstag 10. März 2015, 00:06

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.
Benutzeravatar
/me
User
Beiträge: 3553
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

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.
Benutzeravatar
/me
User
Beiträge: 3553
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

Stimmt. Vermutlich es es aufwändiger networkx zu dieser Aufgabe zu überreden als es gleich selber zu machen.
elchico
User
Beiträge: 29
Registriert: Dienstag 10. März 2015, 00:06

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()
Antworten