Ich habe leider kein Beispiel dafür. Es muss aber auch kein K-d-Baum sein, es gibt ja noch andere mehrdimensionale Indexstrukturen.
Die einfachste wäre hier denke ich die Hashmap-Lösung. Im Grunde ist die Idee, dass man ein grobes Raster über die Punkte legt, und pro Kästchen abspeichert, welche Punkte darin liegen:
Code:
|-----|-----|-----|---
|x | | |
| | | |
|-----|-----|-----|---
| | xx | |
| | | |
|-----|-----|-----|---
| | | x|
| x|x | |
|-----|-----|-----|---
(Sorry, die DP zerstört mal wieder das Layout, aber ich denke es ist klar, wie es gemeint ist.)
Dann muss man, um „identische“ Punkte zu finden, nur noch die Punkte aus dem gleichen Kästchen und aus den 8 Nachbarkästchen überprüfen.
Im Grunde braucht man nicht mal eine Hashmap, sondern ein einfaches 2D-Array tut es auch, ist nur u.U. weniger speichereffizient, wenn es größere, Bereiche gibt, die leer stehen.
Ein genereller Nachteil dieser Lösung ist, dass man die Kästchengröße irgendwie von Hand tunen muss.