spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi Leute,

ich sitze gerade an einem Problem, bei dem ich einfach nicht auf einen passenden Algorithmus komme.

Zur Ausgangslage:

ich habe zwei zweidimensionale Punktwolken. Meine "Soll-Punktwolke" mit fest definierten Punkten hat immer 6 Elemente. Meine "Objektpunktwolke", die ich überprüfen will, hat 6 oder weniger Elemente. Es ist also nicht unbedingt der performanteste Algorithmus gefragt.

Ich möchte am Ende für jeden Punkt aus der Objektpunktwolke den nächstgelegenen Punkt aus der Sollpunktwolke. Dafür berechne ich mir für jeden Punkt die Abstände zu allen Punkten der Sollpunktwolke. Soweit so gut.

Nun geht es aber darum die jeweils am besten passendsten Punktpaare zu finden, so dass kein Punkt aus der Sollpunktwolke mehr als einmal vor kommt. Wenn ich einfach immer den nächstgelegenen Punkt verwende, können Punkte mehrmals verwendet werden.

Irgendwie müsste man dann den zweibesten Punkt nehmen und falls der schon vergeben ist, wieder schauen, welcher der konkurrierenden Punkte näher liegt...das Spiel geht dann aber immer so weiter. Dafür will mir im Moment einfach keine ordentliche Implementierung einfallen. Ich konnte auch leider nichts dazu finden, wie das andere gemacht haben, denn der Beispielcode hat meist mit Klassifizierung zu tun, oder verwendet einfach nur einen Punkt und nicht zwei Punktwolken.

Würde mich freuen, wenn ihr mir da weiterhelfen könntet.

Gruß Sp3iky

Achja, das Ganze programmiere ich in C#. Das verhindert leider, dass ich die OpenCV-Funktion dafür verwende, da der C# Wrapper eine Access Violation auslöst (bestätigtes, ungelöstes Problem).

So wie es aussieht nicht das, was ich haben möchte. Dort können doppelte Zuordnungen auftreten.