Die erkennen erstmal keine Kollisionen, sondern beschleunigen (grob gesagt) nur die Suche nach einem Punkt, der einem gegebenen Punkt am nächsten liegt - und genau das war ja der Ansatz, den ich beschrieben habe. Wenn du jetzt aber sagst, dass die
Orientierung anders sein kann, ist der Ansatz für die Socken. (Sorry - ursprünglich hatte ich die Aussage "Der Abstand darf einwenig abweichen." so (falsch!) interpretiert, dass die Positionen der zu suchenden Punkte von den Originalpunkten abwichen können, aber offenbar meinst du wirklich nur die
Abstände der (durch Kanten verbundenen) Punkte untereinander (!?!))
Welche Anforderungen nun jetzt genau erfüllt sein müssen, ist mir nicht ganz klar. Wenn es nur die Abtände wären, könnte z.B. der linke Knoten aus Bild 1 ja (ohne den Rest des Graphen zu verändern) nach rechts "umgeklappt" werden - d.h. es würden sich keine der (eingezeichneten!)
Abstände verändern, aber die räumliche Lage der Knoten zueinander ändert sich dramatisch...
Geht es also NUR um die Topologie, oder (oder auch) um die räumliche Lage der Knoten?
Allgemein klingt das jetzt so, als ob man den "Graphen" aus Bild 2 als vollständig vernetzt ansehen müßte, und dann den Teilgraphen finden müßte, der die gleiche Topologie hat, wie der Graph aus Bild 1, und bei den die Längenunterschiede zwischen den "korrespondierenden" Kanten möglichst gering ist?
Wenn man da von einer "Menge aller Teilgraphen" redet, dann "fühlt sich das an, als wäre es NP-vollständig" ... aber vielleicht gibt es irgendwelche geschickten Ansätze, mit denen das (bei kleinen Graphen) trotzdem noch praktikabel ist. Falls das Problem nicht sogar APX-hart ist, kann man ja auch vielleicht eine gute Lösung approximieren?
Hm. Der Hinweis auf Websuch-Stichworte wie "Graph matching" oder so ist vmtl. überflüssig? Vielleicht liefert sowas wie der dritte Link von
http://www.google.de/search?hl=de&q=graph+matching&btnG=Suche&meta= ja mögliche Anätze?
