geometrisch/geographische Zuordnungssuche

[NoPy]

Das ganze ist ein Teilproblem, dass ich in python lösen muss, da der entsprechende Code (temporär) in ein Softwaresystem integriert werden muss, dass nur eine python- Schnittstelle hat.
Ich hoffe, ich kann es einigermaßen herüberbringen.

Gegeben ist eine Liste von Koordinaten, die (durch ihre Reihenfolge) eine Linie abbildet. Diese Linie bildet typischerweise eine Straßenachse zu einem bestimmten Zeitpunkt. (Fragliche Achse)
Der gegenwärtige Verlauf der Straße liegt typischerweise "in der Nähe", könnte aber natürlich auch durch komplett andere Stützstellen repräsentiert werden. Dabei ist es so, dass die Straße in einzelne Elemente zerfallen kann (Abschnitte und Äste genannt), die teilweise auch dicht nebeneinander her verlaufen können. (Ist- Achse, bzw. Ist- Achsen) Entlang dieser Achse kann die Position als sogenannte Station als Entfernung entlang der Achse vom Anfang aus ermittelt werden.

Ein Web- Service sagt mir zu einem beliebigen Punkt, von welchen Ist- Achsen der geographische Punkt wie weit entfernt ist und welche Station der korrespondierende Punkt auf dieser Achse hätte.
Eine jede Abfrage dauert ca. 1 s, die Gesamtdatenmenge besteht aus ca. 20 000 Achsen mit 20-500 Einzelpunkten, eine solche Abfrage für JEDEN Einzelpunkt durchzuführen, würde mehrere Tage dauern und ist im Moment nicht möglich, der Webservice ist als gegeben zu betrachten.

Jetzt wird es in der Berschreibung richtig kompliziert:
Gesucht ist die "richtige" Zuordnung potentiell mehrerer Ist- Achsen zu einer fraglichen Achse, wobei jedes Teilstück der fraglichen Achse nur zu einer Ist- Achse gehören darf.
Die Definition "richtig" ist hierbei nicht trivial. Der aktuelle Ansatz sieht vor, auf jeder fraglichen Achse "Stützstellen" zu berechnen, die dann eine Menge von potentiellen Kandidaten für Ist- Achsen liefern.
Die Stützstellen werden einmal alle X m gewählt (initial) und dann sollen (rekursiv) soviele Zwischenpunkte "abgefragt" werden, bis das je 2 benachbarte Stützstellen mindestens eine gemeinsame Ist- Achse haben oder die Punkte direkt nebeneinander liegen (worst case).

Ist dieser Zustand erreicht, dann werden die geeignetste Ist- Achsen gewählt, indem
1. die potentiellen Gesamtlängen der einzelnen möglichen Ist- Achsen (wenn also 2 benachbarte Punkte über die gleiche Achse verbunden sind) ermittelt werden
2. die größte Länge (mit dem kleinsten Abstand zur Ist- Achse) ausgewählt wird
3. die Achsenteile, die dadurch beschrieben werden können, entsprechend markiert werden
Diese 3 Schritte werden weiter durchgeführt, wobei in Schritt 1 nur noch die Teilbereiche ausgewertet werden, die noch nicht "versorgt" worden sind

Auch das Abbruchkriterium ist nicht ganz trivial, da es ja durchaus sein kann, dass teile der fraglichen Achse soweit von allen Ist- Achsen wegführen, dass sie de facto NICHT auf einer Ist- Achse verlaufen.
Sie könnten sogar auf einer völlig anderen Ist- Achse verlaufen, die sie quasi strückweise kreuzen.

Am Ende soll dann etwas rauskommen a la
Fragliche Achse 1)
P1 - P20: IstAchse: 12345, Stationen: 100-1700, symbolischer Abstand: 2m
P20 - P30: IstAchse: 23456, Stationen: 0-200, symbolischer Abstand: 3m
P30 - P40: keine Achse
P40 - P42: IstAchse: 98765, Stationen: 500-510, symbolischer Abstand: 3m
P42 - P80: keine Achse
P80 - P100: IstAchse: 23456, Stationen: 700-1200, symbolischer Abstand: 4m

wobei es immer noch sein kann, dass P40-P42 quasi ein Artefakt darstellt, das muss ich an anderer Stelle prüfen, letztlich über einen Datenbankabgleich.

Das ganze ist immer noch deutlich simplifiziert, denn es ist natürlich auch denkbar, dass man iterativ den Suchradius für Punkte erweitert, wenn man erst mal eine gut passende Ist- Achse gefunden hat und dann lediglich die Punkte als "weit weg" klassifiziert. Ebenso könnte man den geographischen Abstand der Punkte in Beziehung setzen zu der Differenz der ermittelten Stationen. Derartige Erweiterungen können in Zukunft nötig und sinnvoll sein, können aber keinesfalls schon jetzt eingearbeitet werden.

Der von mir bislang erzeugte Code geht in etwa so vor. Es gibt Objektklassen für GeoLinien, GeoPunkte und PunktZuordnungen. Ebenso gibt es diverse Hilfsklassen, die bemüht werden, um die Längenermittlung zu kapseln. Natürlich ist einiges, was ich hier "einfach" beschrieben habe, komplizierter implementiert und teilweise auch umgekehrt.

Was mich interessieren würde, wäre, wie ihr das ganze angehen würdet.

Wer sich die Mühe gemacht hat, bis hierher zu lesen: Herzlichen Dank

[BlackJack]

@NoPy: Ich würde mir als erstes jemanden mit Domänenwissen suchen der mir erklärt was Achsen und Stationen etc. sind. Am besten für Dumme, mit vielen Zeichnungen.

Von der Natur der Daten her würde ich schauen ob es da nicht schon was gibt was Arbeit abnimmt, zum Beispiel im `osgeo`- oder im `shapely`-Package.

[EyDu]

@NoPy: Ich würde mir als erstes jemanden mit Domänenwissen suchen der mir erklärt was Achsen und Stationen etc. sind.

So ging es mir beim Lesen des Texts auch. Für mich hört sich das nach einem SLAM-Problem an, aber wenn man zu viel damit arbeitet, dann ist SLAM irgendwann immer die Lösung Beschreibe doch mal ganz konkret was du machst, dann kann man sich etwas mehr vorstellen. Was sind die Achsen, was sind die Stationen, woher kommen die Koordinaten und welches Problem willst du eigentlich genau lösen. Momentan ist die Beschreibung viel zu abstrakt.

[pillmuncher]

Für mich liest es sich so, als wollte man ein Problem lösen ähnlich dem, das zB. bei Google Maps manchmal auftritt, wenn man die Satellitenbild-Ansicht anschaltet. Da kann es passieren, dass die angezeigte Route nicht auf der angezeigten Straße verläuft, sondern durch die neben der Straße stehenden Häuser geht. Wenn meine Interpretation richtig ist, dann sollen zu einer Route die "wahrscheinlichsten" Straßen gefunden werden.

Ich habe momentan keine Ahnung, wie man sowas effizient implementiert. Meine Vorgehensweise wäre, eine entsprechende Bibliothek im Cheese Shop zu suchen, und wenn ich dort nichts finde, die Suchmaschine meiner Wahl zu bemühen, und falls das kein brauchbares Ergebnis liefert, würde ich versuchen, das Problem mathematisch darzustellen. Mit "mathematisch" meine ich hier nicht algorithmisch, sondern analytisch. Also nicht als Antwort auf die Frage: Wie löse ich das Problem, sondern Worin besteht das Problem. Erst dann würde ich mir Gedanken über Klassen etc. machen.

[Sirius3]

Ich stelle mir die Aufgabe so vor: An einem schönen Sonntagnachmittag mache ich eine Radtour; zu Hause möchte ich wissen, durch welche Straßen ich eigentlich gefahren bin, nehme mein GPS und lege die Positionspunkte über eine Karte.
Wenn ich das richtig verstanden habe, gibt es einen Web-Server, dem ich einen Punkt schicke und der antwortet mir mit einer Liste an Straßen, die in der Nähe liegen. Weil Code mehr sagt als tausend Worte, habe ich mal kurz einen einfachen Algorithmus implementiert:

Code: Alles auswählen

import itertools

def get_axes_for_point(point, max_distance=20):
    """ Gets all axes for one point within the given distance
    Input:
    - point: the coordinate
    - max_distance: the maximum distance in m
    Output:
    - Dictionary: keys are the axis, values are tuples
        of (station, distance), where distance is the distance
        of the point to the station in m.
    """
    # here comes some web request
    
def find_matching_route(points):
    """ Matches points to axes
    Input:
    - points: list of points
    Output:
    - List: for each point a tuple of (axis, station, distance)
    """
    result = []
    current_axis = None
    # map points to axes an append empty list
    # to process last point, also
    axes_mapper = itertools.chain(
        itertools.imap(get_axes_for_point, points),[[]])
    axes = next(axes_mapper)
    for next_axes in axes_mapper:
        if not axes:
            result.append(None)
        elif current_axis in next_axes:
            # easy case: we stay on the same axis
            best_match = current_axis
        else:
            # best match is the axis, for which the distance of
            # the two points to their stations is minimal
            best_match = min(axes,
                lambda axis: axes[axis][1]**2 +
                    next_axes.get(axis, (None, float('inf')))[1]**2)
            if best_match in next_axes:
                # to points lie on a new axis
                current_axis = best_match
            else:
                # no matching found, take the nearest point
                best_match = min(axes, lambda axis: axes[axis][1])
        result.append((best_match,) + axes[best_match])
        axes = next_axes
    return result

[NoPy]

Das Problem ist eines aus dem wirklichen Leben. Wenn ihr mal an einer Bundes (oder auch Kreis oder Landes/Staats- Straße) darauf achtet, dann werdet ihr alle 200 m entweder ein Schild an einem Leitpfosten oder an einem extra Prismenkörper entdecken. Auf dem stehen beispielsweise B 7 (für die Straße) und dann noch je nach Bundesland eine 7- Stellige Anzeige für Netzknoten oder Abschnitte sowie eine Angabe in km, die den Abstand zum letzten "Netzknoten" darstellt.

Wer sich das wirklich antun möchte, der darf http://www.bast.de/cln_033/nn_795118/DE ... zdaten.pdf gern nachlesen.

Unser Straßennetz ist als Knoten- Kanten- Modell organisiert und hinsichtlich der Unterhaltung sind alle Dinge (Leitpfosten, Verkehrsschilder oder Aufbaudaten) entlang dieses Knoten- Kanten- Modells stationiert. (Das System ist zig Jahre alt und damit per se "toll")

Da das Straßennetz durch Baumaßnahmen, Nutzungsänderungen etc. sich permanent verändert, ist es natürlich nicht stabil. In meinem Fall hatte ich ein Netz, dass jemand für das Jahr 2025 "prognostiziert" hat, auf die aktuelle Netzsituation "umzurechnen", damit diese Prognosezahlen mit derzeit vorhandenen Informationen auf Attributebene verschnitten werden können.
Es ist nicht so leicht, wie es sich anhört, u.a. deshalb, weil auch einige Besonderheiten/Ausnahmen bedacht werden müssen. Und es gibt dafür meines Wissens keine Lösung (und ich stehe in Kontakt mit einigen, die es wissen würden), höchstens eine aus einem ganz anderen Kontext.

@sirius: Den Code schau ich mir bei Gelegenheit an. Erst mal habe ich meine Module (zwei Hände voll Spezialklassen, die eng verzahnt sind, ca. 300 Zeilen Code) zusammengestöpselt, das Ergebnis wird in eine Oracle- DB gepustet und es scheint wundersamer Weise zu funktionieren. Morgen sehe ich mal nach, ob er schon fertig ist. Ich hoffe, ich muss den Code nie wieder warten ...

Wenn ich mit dem Gesamtprojekt fertig bin und etwas Luft habe, werde ich Euch mal hinsichtlich Dokumentationsmöglichkeiten, Aufräumarbeiten und Ähnlichem löchern.
Ich danke Euch allen für Eure Geduld mit mir.

[Hyperion]

@NoPy: Eines ist aber doch auch bei dieser Problemstellung deutlich: Man kann seinen Code sicherlich einfach durch Unit-Tests absichern! Damit sollten sich zumindest Deine Probleme mit ``None``-Werten in den Griff bekommen lassen. Hunderte bzw. Tausende Datensätze hat man zwar im "real life", auf die Testbarkeit hat das aber ja keinen Einfluss.

Das nur als Anmerkung, weil Du in einem anderen Thread etwas von problematischer Testbarkeit erzählt hattest... ich kann aus der Beschreibung heraus nichts problematisches erkennen.

[NoPy]

Nicht unbedingt.

Je nachdem, wie tatsächlich die fragliche Linie verläuft, welche tatsächlichen Achsen sie in welchem Abstand passiert usw. liefert der Webservice unterschiedliche Ergebnisse.
Und abhängig von den vorigen Ergebnissen weichen die inneren Zustände der zu testenden Klassen stark voneinander ab.
Es ist leicht nicht überschaubar, welche Konstellationen alles auftreten können.

Ich müsste entweder einen WebService- Dummy schreiben, der alle möglichen Fälle liefert (zu komplex für das Problem und im Einzelnen weiß ich auch nicht ganz genau, ob ich damit alle Fälle erschlage)
oder künstlich eine Linie suchen, bei denen der Web- Service die erwarteten Grenzfälle passiert (ebenfalls sehr komplex und wahrscheinlich nicht abschließend möglich)

Soweit ich das Problem mit Unittests verstanden habe - zumindest habe ich das in der Vergangenheit immer so gehandhabt - schickt eine Testklasse eine Sequenz von Methoden ab,
a) deren theoretisches Ergebnis sie kennt
b) die alle erreichbaren Zustände der zu testenden Klasse abbildet

beides ist ein Problem und nicht ohne intensive Gestaltung eines Testszenarios (das so in den Daten ja gar nicht vorkommen muss und selbst wenn, noch nicht einmal der tatsächliche Grenzfall zu sein braucht) nicht möglich.

Stell Dir vor, Du müsstest eine komplizierte m:n- Zuordnung testen, die auch noch vom inneren Zustand (wobei die Zahl der inneren Zustände beliebig groß ist) der Objektklasse abhängt (oder anders: Schreibe eine Testklasse für Enigma )
Es ist möglich, aber wahrscheinlich komplexer als das Problem, das eigentlich zu lösen ist.

Ich bin ein Freund von Testklassen, aber in diesem Fall habe ich keine Vorstellung, was ich alles testen soll.
Sicher, ich könnte alle beteiligten Klassen einzeln testen und dabei auf die mit dem WS verzichten, aber das bringt mich, fürchte ich, nicht weiter.

Glücklicherweise kann ich sagen, dass das System nach 18 Stunden fertig ist, ca. 88,3% der Datensätze waren zuzuordnen, 11,1% nicht und 0,6% der Datensätze verursachten Probleme.
Das werden meine Testszenarien

[Hyperion]

Du sollst ja nicht den Webservice testen, sondern *Deinen* Code bzw. genauer die "Units of Work", die Du modellierst. Und diese musst Du doch kennen bzw. wissen, wie sie funktionieren und ggf. welche Grenzfälle es durch Parameterübergabe gibt.

An den Stellen, an denen der WS zum Tragen kommt, musst Du ihn natürlich faken und ein Stub-Objekt generieren, welches wohl definierte Werte für einen Test liefert. Selbst wenn man damit nicht alle Fälle erschlagen kann, ist aber das doch genau die Nahtstelle im Code, an der Du problematische Werte "abfangen" kannst bzw. testest, *wie* Dein Code damit umgehen sollte. Die "positiven" Fälle sollte Deine Logik bearbeiten können, bei allen anderen sinnvoller Weise mit einer definierten Ausnahme "aussteigen".

Ich sehe da immer noch kein Problem, denn ein WS ist ja reine Datenzugriffsschicht - und die kann man per se nicht durch Unit-Tests abdecken; will man auch nicht, denn das sind Integrationstests

[Sirius3]

@NoPy: Bei Unit-Tests werden einzelne Funktionen getestet, und die sollten im besten Fall nicht so komplex sein, das sie nicht testbar sind. Dazu werden Testdaten verwendet und nicht reale Daten. Die Webservice-Klasse wird dann unabhängig von den anderen Klassen getestet. Und für diese brauchst es dann eine Dummy-Webservice-Klasse. Aber da die Schnittstelle idealerweise nur aus sehr wenigen Methoden besteht, ist das erstellen einer Dummy-Klasse kein großer Aufwand.

[BlackJack]

Zumal es diverse „Mock”-Module gibt, mit denen man sich recht leicht den Webservice ersetzen kann. Duck Typing sei Dank.