En yakın komşuları aramak için benim kanaatimce en uygun olanı Locality sensitive hashing. Bu yöntemde dünya sisteminin eksi değerler alıp almadığına dikkat etmek gerekir!. Eğer eksi değer alıyorsa formülümüzden eksik değer çıkmaması için düzeltme yapmak lazım gelebilir.
Design A Location Based Service videosu da faydalı
1.1. Cell döndüren Hash Fonksiyon
Elimizdeki nesnelerin koordinat bilgisini bir hash fonksiyonuna sokup hangi hücreye yerleşeceğine karar veriyoruz. Arama için hızlı bir yöntem. hash fonksiyonunun birbirlerine yakın nesneleri komşu hücrelere yerleştirmesi gerekiyor.
1.2 GeoHash Fonksion
1.2 GeoHash Fonksion
String döndürür. Önce binary bir string üretir daha sonra bu Base32 olarak kodeklenir
2. Verinin Saklanması
2.1 Matrix Şeklinde Locality Hashing
Matrix'in en zor tarafı hücre bulunduktan sonra etrafındaki hücreleri de dolaşmak. Bu kod parçasında matrix'in dışına taşıp IndexOutOfBounds tipi bir exception alma ihtimaline karşı dikkatli kodlamak gerekiyor.
Örnek - Etraftaki Hücreleri Dolaşmak
Elimizde iki boyutlu bir dünya olsun
Cell[][] cells;Şöyle yaparız
Optional<Cell> getCell(int x, int y) {
if(x >= 0 && x < width && y >= 0 && y < height) {
return Optional.of(cells[y][x]);
}
return Optional.empty();
}
List<Cell> getCellNeighbours(Cell cell) {
List<Optional<Cell>> neighbours = new ArrayList<>();
neighbours.add(getCell(cell.x, cell.y+1)); // TOP
neighbours.add(getCell(cell.x, cell.y-1)); // BOTTOM
neighbours.add(getCell(cell.x-1, cell.y)); // LEFT
neighbours.add(getCell(cell.x+1, cell.y)); // RIGHT
return neighbours.stream()
.filter(Optional::isPresent)
.map(Optional::get)
.collect(Collectors.toList());
}Örnek - 3 boyutlu dünya
Eğer dünya koordinatımız eksi değerlere de sahip olsaydı (mesela -10,000 , 10,000 arasında) şöyle yaparız. Önce 1 satırında offset değerini ekleyerek eksi değerleri artı hale getiririz. Daha sonra 2 satırında ChunkSize'lara böleriz. Mesela X,Y ve Z için chunksize 100 kabul edilebilir. Bu durumda her chunk merkezi arasında 1000 birimlik mesafe olur
Chunk GetChunkForWorldPosition(Vector3 position) {
float offset = WorldWidth * 0.5; //1
int x = (int)Math.Floor((position.x + offset) / ChunkSizeX); //2
int y = (int)Math.Floor((position.y + offset) / ChunkSizeY);
int z = (int)Math.Floor((position.z + offset) / ChunkSizeZ);
return chunks[x][y][z];
}Örnek - İki Boyutlu Dünya
Açıklaması şöyle
Imagine a 2D example. You have a 2D world where each chunk contains 10 x 10 pixels. At the world level you want to access the pixel data for pixel (342,103). First you need to find the chunk that contains the data. You can easily find that because you know each chunk contains 10 x 10 pixels. To get chunk coordinates, just divide by the number of pixels per chunk, (int)342/10 = 34 and (int)103/10 = 10, giving you chunk (34,10).Now you just need to get the coordinates within the chunk. Those coordinates can easily be found by getting the remainder after the division, i.e. a modulo operation. 342%10 = 2 and 103%10 = 3, giving you pixel (2,3).That means world position (342,103) can be found in chunk (34,10) at position (2,3).
2.2. Tree Şeklinde Locality Hashing
Java'da TreeMap kullanarak hücreleri sıralı tutmak ve daha sonra xmin, xmax arasında kalan (örneğin 2 enlem arası) ve daha sonra ymin, ymax (iki boylam arası) değerleri dolaşmak mümkün.TreeMap<Integer, TreeMap<Integer, Integer>> values;
for (int x : values.subMap(xmin, xmax).keySet()) {
for (int y : values.get(x).subMap(ymin, ymax).values()) {
// y here, represents the values of points in range...
}
}3. Diğer
3.1 Zaman İçin HashingLocality zaman için de kullanılabilir. Örnekte birbirlerine yakın zamanlar aynı kümeye ekleniyor.
Örnek - Birbirlerine en yakın zamanları eşleştirmemodel.get_time_bucket(seconds) {returnfloor(self.timestamp / seconds); }
Eğer birbirlerine en yakın zamanları eşleştirmek istersek şöyle yapabiliriz.
//compute reasonably aligned pairsvarmax_tolerable_offset =500;//do not match more then 500 miliseconds distant onesDictionary<long,long> alignedPairs =newDictionary<long,long>();foreach(vars in s_timestamps) {//for every timestamp in first timeline find the nearest one from rvarnearest_r = r_timestamps.OrderBy(r =>Math.Abs(r - s)).First();//if that is closer than allowed offsetif((Math.Abs(nearest_r - s)) <= max_tolerable_offset *10000) {//so now I need to find nearest s mark for this r markvarclosest_s = s_timestamps.OrderBy(s=>Math.Abs(s- nearest_r )).First();//if they are mutually in love, marry themif(closest_s == s) alignedPairs.Add(s, nearest_r); } }
