回答編集履歴

2

追記

2017/02/10 02:43

投稿

Lhankor_Mhy
Lhankor_Mhy

スコア35860

test CHANGED
@@ -27,3 +27,457 @@
27
27
 
28
28
 
29
29
  いずれにせよ、V2の時代よりもGoogleマップAPIは高速化しているので、100程度のマーカーであればそのままAPIに投げた方がよきにはからってもらえると思います。
30
+
31
+
32
+
33
+
34
+
35
+ ##### 追記
36
+
37
+ すっかり忘れてましたが、はるか昔にgeohash管理ライブラリを作ったことがありました。緯度経度を渡すとその範囲のgeohashの組み合わせを返します。読み込み済みの範囲も管理していて、内部でパズルみたいに組み合わせをしたりしてます。プロトタイプ汚染とかしててお行儀の悪いレガシーコードですが、せっかくなので貼っておきますね。
38
+
39
+ ```javascript
40
+
41
+ function GeostringStack(max, min){
42
+
43
+ //定数
44
+
45
+ var GEOSTRING_LIMIT = max; //探索最小限度
46
+
47
+ var SLICE_MARGIN = 0.00001; //スライスマージン
48
+
49
+ var SLICE_LIMIT = Math.floor(min/2); //スライスグリッド
50
+
51
+ var DY = 1.0/(Math.pow(2,SLICE_LIMIT));
52
+
53
+ var DX = 1.0/(Math.pow(2,SLICE_LIMIT));
54
+
55
+ var MAP_SIZE = {y:180, x:360}; //世界地図座標の範囲
56
+
57
+
58
+
59
+ //Geohashモジュール
60
+
61
+ function Geostring (data, bound, depth){
62
+
63
+ var to_bits = function(f,depth){
64
+
65
+ re = [];
66
+
67
+ for (var i=1; i<depth+1; i++){
68
+
69
+ re.push( Math.floor(f*2).toString() )
70
+
71
+ f = (f*2)-Math.floor(f*2)
72
+
73
+ }
74
+
75
+ return re
76
+
77
+ }
78
+
79
+
80
+
81
+ var bitstring = function(data,bound,depth){
82
+
83
+ var y = data[0];
84
+
85
+ var x = data[1];
86
+
87
+ y = to_bits((y-bound[0])/(bound[2]-bound[0]),depth)
88
+
89
+ x = to_bits((x-bound[1])/(bound[3]-bound[1]),depth)
90
+
91
+ bits =''
92
+
93
+ for (var i=0; i<x.length; i++){
94
+
95
+ bits += x[i] + y[i]
96
+
97
+ }
98
+
99
+ return bits
100
+
101
+ }
102
+
103
+
104
+
105
+ this.toString = function(){
106
+
107
+ return this.hash;
108
+
109
+ }
110
+
111
+
112
+
113
+ this.union = function(yourHash){
114
+
115
+ var myHash = this.hash;
116
+
117
+ var yourHash = yourHash.toString();
118
+
119
+ var returnHash = '';
120
+
121
+ for ( var i=0; i<Math.min(myHash.length, yourHash.length); i++){
122
+
123
+ if (myHash.charAt(i) == yourHash.charAt(i)){
124
+
125
+ returnHash += myHash.charAt(i);
126
+
127
+ }else{
128
+
129
+ break;
130
+
131
+ }
132
+
133
+ }
134
+
135
+ return new this.myConstructor(returnHash, bound, depth)
136
+
137
+ }
138
+
139
+
140
+
141
+ this.bbox = function(){
142
+
143
+ var bits= this.hash;
144
+
145
+ var depth = Math.floor(bits.length/2);
146
+
147
+ var minx = 0.0;
148
+
149
+ var miny = 0.0;
150
+
151
+ var maxx = 1.0;
152
+
153
+ var maxy = 1.0;
154
+
155
+ for (var i=0; i<depth+1; i++){
156
+
157
+ if (bits.charAt(i*2)) minx += parseInt(bits.charAt(i*2))/(Math.pow(2,i+1));
158
+
159
+ if (bits.charAt(i*2+1)) miny += parseInt(bits.charAt(i*2+1))/(Math.pow(2,i+1));
160
+
161
+ }
162
+
163
+ if (depth){
164
+
165
+ maxx = minx + 1.0/(Math.pow(2,depth+bits.length%2));
166
+
167
+ maxy = miny + 1.0/(Math.pow(2,depth));
168
+
169
+ }else if (bits.length == 1){
170
+
171
+ // degenerate case
172
+
173
+ maxx = Math.min(minx + .5, 1.0);
174
+
175
+ }
176
+
177
+ minx = origin[1]+minx*size[1];
178
+
179
+ maxx = origin[1]+maxx*size[1];
180
+
181
+ miny = origin[0]+miny*size[0];
182
+
183
+ maxy = origin[0]+maxy*size[0];
184
+
185
+ return [miny, minx, maxy, maxx];
186
+
187
+ }
188
+
189
+
190
+
191
+ this.myConstructor = arguments.callee
192
+
193
+
194
+
195
+ var bound = bound ? bound : [-90,-180,90,180];
196
+
197
+ var depth = depth ? depth : 32;
198
+
199
+ var origin = bound.slice(0,2);
200
+
201
+ var size = [bound[2]-bound[0], bound[3]-bound[1]];
202
+
203
+ if (data instanceof Array){
204
+
205
+ this.hash = bitstring(data,bound,depth);
206
+
207
+ }else{
208
+
209
+ this.hash = data;
210
+
211
+ }
212
+
213
+ }
214
+
215
+
216
+
217
+ //配列関数の拡張
218
+
219
+ if (!Array.prototype.map){
220
+
221
+ Array.prototype.map = function(f){
222
+
223
+ var re = []
224
+
225
+ for ( var i=0; i<this.length; i++){
226
+
227
+ re.push( f(this[i]) )
228
+
229
+ }
230
+
231
+ return re;
232
+
233
+ }
234
+
235
+ }
236
+
237
+ if (!Array.prototype.max){
238
+
239
+ Array.prototype.max = function(){
240
+
241
+ return this.slice(0).sort().reverse()[0];
242
+
243
+ }
244
+
245
+ }
246
+
247
+ if (!Array.prototype.min){
248
+
249
+ Array.prototype.min = function(){
250
+
251
+ return this.slice(0).sort()[0];
252
+
253
+ }
254
+
255
+ }
256
+
257
+ if (!Array.prototype.contains){
258
+
259
+ Array.prototype.contains = function (v){
260
+
261
+ for( var i=0; i<this.length; i++){
262
+
263
+ if (this[i] == v) {return true; break;}
264
+
265
+ }
266
+
267
+ }
268
+
269
+ }
270
+
271
+ //定数
272
+
273
+ var IS_FOUND = 1;
274
+
275
+ var IS_EMPTY = 2;
276
+
277
+ var IS_PARTIAL = 3;
278
+
279
+
280
+
281
+ this.index = function(boxArray){
282
+
283
+ var slicedBox = this.slice(boxArray);
284
+
285
+ var boundsGeostring;
286
+
287
+ var boundsGeostrings = [];
288
+
289
+ for (var i=0; i<slicedBox.length; i++){
290
+
291
+ boundsGeostring =
292
+
293
+ new Geostring([slicedBox[i].sw.lat+SLICE_MARGIN, slicedBox[i].sw.lng+SLICE_MARGIN])
294
+
295
+ .union( new Geostring([slicedBox[i].ne.lat-SLICE_MARGIN, slicedBox[i].ne.lng-SLICE_MARGIN]) );
296
+
297
+ boundsGeostrings = boundsGeostrings.concat( this.search( boundsGeostring.toString().substring(0,GEOSTRING_LIMIT) ) );
298
+
299
+ }
300
+
301
+ return boundsGeostrings
302
+
303
+ }
304
+
305
+ this.slice = function(bbox){//SLICE_LIMITで切り分け
306
+
307
+ if (bbox instanceof Array) {
308
+
309
+ box = { sw:{lat:bbox[0]/MAP_SIZE.y, lng:bbox[1]/MAP_SIZE.x}, ne:{lat:bbox[2]/MAP_SIZE.y, lng:bbox[3]/MAP_SIZE.x} };
310
+
311
+ }else{
312
+
313
+ box = bbox;
314
+
315
+ }
316
+
317
+ return subSlice(box).map(function(b){
318
+
319
+ return { sw:{lat:b.sw.lat*MAP_SIZE.y, lng:b.sw.lng*MAP_SIZE.x}, ne:{lat:b.ne.lat*MAP_SIZE.y, lng:b.ne.lng*MAP_SIZE.x} }
320
+
321
+ });
322
+
323
+
324
+
325
+ function subSlice(box){//再帰関数
326
+
327
+ var yCutoff = box.sw.lat-box.sw.lat%DY+DY;
328
+
329
+ var xCutoff = box.sw.lng-box.sw.lng%DX+DX;
330
+
331
+ var f = ( ( yCutoff < box.ne.lat )<<1 ) + ( xCutoff < box.ne.lng )
332
+
333
+ switch (f){
334
+
335
+ case 0:
336
+
337
+ return [box];
338
+
339
+ break;
340
+
341
+ case 1:
342
+
343
+ return [{ sw:{lat:box.sw.lat, lng:box.sw.lng}, ne:{lat:box.ne.lat, lng:xCutoff} }].concat(
344
+
345
+ subSlice({ sw:{lat:box.sw.lat, lng:xCutoff}, ne:{lat:box.ne.lat, lng:box.ne.lng} }))
346
+
347
+ break;
348
+
349
+ case 2:
350
+
351
+ return [{ sw:{lat:box.sw.lat, lng:box.sw.lng}, ne:{lat:yCutoff, lng:box.ne.lng} }].concat(
352
+
353
+ subSlice({ sw:{lat:yCutoff, lng:box.sw.lng}, ne:{lat:box.ne.lat, lng:box.ne.lng} }))
354
+
355
+ break;
356
+
357
+ case 3:
358
+
359
+ return [{ sw:{lat:box.sw.lat, lng:box.sw.lng}, ne:{lat:yCutoff, lng:xCutoff} }].concat(
360
+
361
+ subSlice({ sw:{lat:box.sw.lat, lng:xCutoff}, ne:{lat:yCutoff, lng:box.ne.lng} })).concat(
362
+
363
+ subSlice({ sw:{lat:yCutoff, lng:box.sw.lng}, ne:{lat:box.ne.lat, lng:xCutoff} })).concat(
364
+
365
+ subSlice({ sw:{lat:yCutoff, lng:xCutoff}, ne:{lat:box.ne.lat, lng:box.ne.lng} }))
366
+
367
+ break;
368
+
369
+ }
370
+
371
+ }
372
+
373
+ }
374
+
375
+ this.search = function(geostr){//読み込むGeostringを探索
376
+
377
+ var isContain = false;
378
+
379
+ for ( var i=1; i<=geostr.length; i++){
380
+
381
+ if ( this.stack[i].contains( geostr.substring(0,i) ) ) {isContain = true; break;}
382
+
383
+ }
384
+
385
+ if (isContain) {
386
+
387
+ return []
388
+
389
+ }else{
390
+
391
+ var list = this.subSearch(geostr)
392
+
393
+ if (list.state == IS_FOUND){
394
+
395
+ return false;
396
+
397
+ }else{
398
+
399
+ this.stack[geostr.length].push(geostr);
400
+
401
+ return list.list;
402
+
403
+ }
404
+
405
+ }
406
+
407
+ }
408
+
409
+ this.subSearch = function(substr){//searchで使用する再帰関数
410
+
411
+ if ( this.stack[substr.length].contains( substr ) ){
412
+
413
+ return {'state': IS_FOUND, 'list': []};
414
+
415
+ }else{
416
+
417
+ if (substr.length>=GEOSTRING_LIMIT){
418
+
419
+ return {'state': IS_EMPTY, 'list': [substr]};
420
+
421
+ }else{
422
+
423
+ var add0 = this.subSearch(substr+'0');
424
+
425
+ var add1 = this.subSearch(substr+'1');
426
+
427
+ var state = add0.state | add1.state; //IS_FOUND同志の時IS_FOUND、IS_EMPTY同志の時IS_EMPTY
428
+
429
+ var list = (state == IS_EMPTY) ? [substr] : add0.list.concat(add1.list); //IS_EMPTY同志の時、リスト作り直し
430
+
431
+ return {'state': state, 'list': list}
432
+
433
+ }
434
+
435
+ }
436
+
437
+ }
438
+
439
+ this.clearStack = function(){
440
+
441
+ this.stack = new Array(GEOSTRING_LIMIT);
442
+
443
+ for (var i=0; i<=GEOSTRING_LIMIT; i++) this.stack[i] = [];
444
+
445
+ }
446
+
447
+
448
+
449
+ //イニシャライズ
450
+
451
+ this.clearStack();
452
+
453
+ }
454
+
455
+ ```
456
+
457
+
458
+
459
+ 動作例
460
+
461
+ ```javascript
462
+
463
+ var a = new GeostringStack(29,22);
464
+
465
+ a.index([35.8,139.8,35.9,139.9]);
466
+
467
+ //["1110110100001110011111", "1110110100001111001010"]
468
+
469
+ a.index([35.8,139.8,35.9,139.9]);
470
+
471
+ //[]
472
+
473
+ a.index([35.85,139.85,35.95,139.95]);
474
+
475
+ //["11101101000011101101010101", "111011010000111100101110", "11101101000011111000000", "11101101000011111000010000"]
476
+
477
+ a.index([35.85,139.85,35.95,139.95]);
478
+
479
+ //[]
480
+
481
+ ```
482
+
483
+

1

参考URL補足

2017/02/10 02:43

投稿

Lhankor_Mhy
Lhankor_Mhy

スコア35860

test CHANGED
@@ -14,7 +14,7 @@
14
14
 
15
15
 
16
16
 
17
- サーバで管理する場合、実装によっては地図を移動させるたびに読み込みが発生し、結果として遅くなる可能性があります。地図をいくつかの範囲に分割し、表示エリアから読み込むべき範囲を取得し、再読み込みが必要であるかどうか制御する必要があるでしょう。位置情報DBに範囲IDフィールドを設けておくと応答が改善する可能性があるので、検討してみてください。
17
+ サーバで管理する場合、実装によっては地図を移動させるたびに読み込みが発生し、結果として遅くなる可能性があります。地図をいくつかの範囲に分割し、表示エリアから読み込むべき範囲を取得し、再読み込みが必要であるかどうか制御する必要があるでしょう。位置情報DBに範囲IDフィールドを設けておくと応答が改善する可能性があるので、検討してみてください。参考:[一次元ハッシュコードによる空間半径検索 - Qiita](http://qiita.com/kochizufan/items/2fe5f4c9f74636d22ddb)
18
18
 
19
19
 
20
20