Punkte min. Abstandes zweier Mengen |
| 04.06.2011, 19:25 | diego2k | Auf diesen Beitrag antworten » |
| Punkte min. Abstandes zweier Mengen Hallo, da ich einfach nicht weiter komme, stell ich hier meine Frage. Geg. sind 2 Punktwolken(Rote, Blaue) beide mit n Punkten Ges. sind die 2 Punkte(ein Roter, ein Blauer) mit dem min Abstand. Meine Ideen: Aufteilen mithilfe von Voronoi, vielleich dann Triangulieren und mit Pointlocation aber keine Ahnung ... -.- Danke! |
||
| 05.06.2011, 23:35 | Abakus | Auf diesen Beitrag antworten » |
| RE: Punkte min. Abstandes zweier Mengen Hallo, im Prinzip suchst du das Minimum in einer Abstandsmatrix? Die einfachste Idee ist, die gesamte Matrix zu durchsuchen? Abakus 
|
||
| 07.06.2011, 18:02 | diego2k | Auf diesen Beitrag antworten » |
danke, das würd O(n^2) Zeit brauchen ... es darf aber max O(nlogn) sein. hätt ich vielleicht dazu schreiben sollen ^^ |
||
| 08.06.2011, 00:40 | Abakus | Auf diesen Beitrag antworten » |
Wieviele Dimensionen hast du oder spielt das keine Rolle? (Gerade, Ebene, Raum, oder was?) Was wäre dein Ansatz genau? Abakus
|
||
| 08.06.2011, 09:39 | diego2k | Auf diesen Beitrag antworten » |
huch noch was vergessen |R^2 ... also wie oben geschrieben, es geht irgendwie mit voronoi und point location ... aber damit komme ich auf keinen grünen Zweig ... die Punktwolken können ja kilometerweit auseinander liegen oder direkt übereinander ... |
||
| 08.06.2011, 18:26 | Abakus | Auf diesen Beitrag antworten » |
Wie wäre es, zu versuchen, die Delauney-Triangulation zu nehmen und etwas zu modifizieren? Oder du musst dir halt deinen eigenen "Teile-und-Herrsche"-Algorithmus zusammenbasteln. Abakus
|
||
| Anzeige | ||
|
|
||
| 09.06.2011, 21:18 | diego2k | Auf diesen Beitrag antworten » |
danke ... leider schon zu spät ... Lösung: Voronoi Diagramm der ersten Menge ... nun liegt die 2. Menge bereits in einzelnen Feldern des Voronoi Diagramms. D.h. man muss nun nicht mehr n*n Punkte durchsuchen sondern nur mehr die n Punkte der 2 Menge, mal den umliegenden Punkten des Voronoi Feldes. Eigentlich ganz einfach -.- |
||
| 11.06.2011, 13:45 | Abakus | Auf diesen Beitrag antworten » |
OK, ja. Es gibt allerdings sicher mehr als eine Lösung; und welche dann schneller ist, wäre auszuprobieren. Voronoi zuerst könnte zB ein Umweg sein. Abakus
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
|
