Sélection, mise en cache et affichage de photos sur la carte

Dans cet article, j'ai décidé de décrire comment la fonctionnalité de sélection et d'affichage de photos sur un endroit spécifique sur la carte a été implémentée dans notre service photo gfranq.com . Le service photo ne fonctionne pas maintenant.

Étant donné que nous avions beaucoup de photos dans notre service et que nous envoyions des demandes à la base de données chaque fois que les modifications de la fenêtre étaient trop gourmandes en ressources, il était logique de diviser la carte en plusieurs zones contenant des informations sur les données récupérées. Pour des raisons évidentes, ces zones ont une forme rectangulaire (bien que la grille hexagonale ait également été considérée). Comme les zones deviennent plus sphériques à grande échelle, des éléments de géométrie sphérique et des outils pour celle-ci ont également été pris en compte.

Dans cet article, les problèmes suivants ont été soulevés:

• Stocker et récupérer des photos de la base de données et les mettre en cache sur le serveur (SQL, C #, ASP.NET).
• Télécharger les photos nécessaires du côté client et les enregistrer dans le cache client (JavaScript).
• Recalcul des photos qui doivent être masquées ou affichées lorsque la fenêtre change.
• Éléments de géométrie sphérique.

Table des matières

• Partie serveur
  
  • Géotypes intégrés
  • Sélection normale
  • Utilisation d'une table de hachage supplémentaire
  • Mise en cache des photos pour un accès multi-thread
• Côté client
  
  • Initialisation de la carte
  • Déterminer la géolocalisation à l'aide de HTML5
  • Déterminer la géolocalisation à l'aide des informations du serveur
  • Calcul de zones rectangulaires partiellement visibles
  • Calcul de la taille des zones de mise en cache
  • Utilisation du délai lors du redessin
  • Calcul des coordonnées et des hachages des zones partiellement visibles
  • Redessiner les photos affichées
  • Distance sur la carte
• Conclusion

Partie serveur

Les méthodes suivantes de sélection et de stockage de la géoinformation dans la base de données ont été conçues:

• Type de données géographiques intégrées à SQL Server.
• Sélection normale avec restrictions.
• Utilisation de tableaux supplémentaires.

De plus, ces méthodes seront décrites en détail.

Géotypes intégrés

Comme on le sait, SQL Server 2008 prend en charge les types de données géographiques et géométriques, qui permettent de spécifier des informations géographiques (sur la sphère) et géométriques (sur le plan), telles que des points, des lignes, des polygones, etc. . Afin de récupérer toutes les photos entourées d'un rectangle avec les coordonnées ( lngMin latMin ) et ( latMax lngMax ), vous pouvez utiliser la requête suivante:

 DECLARE @h geography; DECLARE @p geography; SET @rect = geography::STGeomFromText('POLYGON((lngMin latMin, lngMax latMin, lngMax latMax, lngMin latMax, lngMin latMin))', 4326); SELECT TOP @cound id, image75Path, geoTag.Lat as Lat, geoTag.Long as Lng, popularity, width, height FROM Photo WITH (INDEX(IX_Photo_geoTag)) WHERE @rect.STContains(geoTag) = 1 ORDER BY popularity DESC 

Notez que le polygone est orienté dans le sens antihoraire et que l'index spatial IX_Photo_geoTag défini par les coordonnées est utilisé (en outre, les index spatiaux sont construits à l'aide d' arbres B ).

Cependant, il s'est avéré que dans Microsoft SQL Server 2008, les index spatiaux ne fonctionnent pas si la colonne avec des géotypes peut accepter des valeurs NULL et qu'un index composite ne peut pas contenir une colonne avec un type de données géographiques, et cette question a été discutée sur Stackoverflow . C'est pourquoi les performances de ces requêtes (sans index) deviennent très faibles.

Les approches suivantes peuvent résoudre ce problème:

• Étant donné que les valeurs NULL ne peuvent pas être utilisées, les valeurs par défaut pour cette colonne sont des coordonnées (0, 0) qui pointent vers un emplacement dans l'océan Atlantique près de l'Afrique (le point de départ pour mesurer la latitude et la longitude). Cependant, à cet endroit ainsi qu'à proximité, les vrais points peuvent être localisés, et les photos ne provenant pas de la carte doivent être ignorées. Si vous changez le point zéro (0, 0) en point extrême nord (0, 90), alors tout ira beaucoup mieux, car la latitude 90 pointe vers le bord de la carte, et vous devez ignorer cette valeur lors de la construction de la grille (c.-à-d. construire jusqu'à la latitude 89).
• Utilisation de SQL Server 2012 ou supérieur et modification du niveau de compatibilité de la base de données à 110 ou supérieur en exécutant ALTER DATABASE database_name SET COMPATIBILITY_LEVEL = 110 . Dans cette version de SQL Server, le bogue avec les valeurs NULL des géotypes a été corrigé et la prise en charge de polygones d'orientations différentes (sens antihoraire et horaire) a été ajoutée.

Malgré les vastes possibilités des géotypes (ils vous permettent de faire non seulement une simple sélection comme illustré ci-dessus, mais aussi d'utiliser des distances et différents polygones), nous ne les avons pas utilisés dans notre projet.

Sélection normale

Pour sélectionner des photos dans la zone délimitée par les coordonnées ( lngMin latMin ) et ( latMax lngMax ), utilisez la requête suivante:

 SELECT TOP @Count id, url, ... FROM Photo WHERE latitude > @latMin AND longitude > @lngMin AND latitude < @latMax AND longitude < @lngMax ORDER BY popularity DESC 

Notez que dans ce cas, vous pouvez créer des index pour les champs de latitude et de longitude (contrairement à la première méthode), car un type de données float ordinaire est utilisé. Cependant, il y a 4 opérations de comparaison dans cette sélection.

Utilisation d'une table de hachage supplémentaire

La solution la plus optimale au problème de sélection de photos dans certaines zones consiste à créer des Zooms table Zooms qui stockent des chaînes contenant des hachages de zones pour chaque zoom, comme indiqué ci-dessous.

La requête SQL suivante peut être utilisée ( zn - niveau de zoom actuel):

 DECLARE @hash float; SET @hash = (@latMin + 90) + (@lngMin + 180) * 180 + (@latMax + 90) * 64800 + (@lngMax + 180) * 11664000; SELECT TOP @Count id, url, ... FROM Photo WHERE id = (SELECT id FROM Zooms WHERE zn = @hash) 

L'inconvénient de cette approche est que la table supplémentaire occupe un espace mémoire supplémentaire.

Malgré les avantages de cette dernière méthode, nous avons utilisé la deuxième méthode ( sélection normale ) sur le serveur, car elle montrait de bonnes performances.

Mise en cache des photos pour un accès multi-thread

Après avoir extrait les informations de la base de données d'une manière ou d'une autre, les photos sont placées dans le cache du serveur à l'aide de l'objet de synchronisation pour prendre en charge le multithreading comme suit:

 private static object SyncObject = new object(); ... List<Photo> photos = (List<Photo>)CachedAreas[hash]; if (photos == null) { // Use lock to avoid extracting from and adding to the cache more than once. lock (SyncObject) { photos = (List<Photo>)CachedAreas[hash]; if (photos == null) { photos = PhotoList.GetAllFromRect(latMin, lngMin, latMax, lngMax, count); // Adding information about photos to the cache with a storage time of 2 minutes with a high storage priority. CachedAreas.Add(hash, photos, null, DateTime.Now.AddSeconds(120), Cache.NoSlidingExpiration, CacheItemPriority.High, null); } } } // Further usage of CachedAreas[hash] 

Cette section décrit la fonctionnalité du serveur pour récupérer des photos de la base de données et les enregistrer dans le cache. La section suivante décrira ce qui se passe du côté client dans le navigateur.

Côté client

Pour visualiser la carte et les photos qu'elle contient, l'API Google Maps a été utilisée. Tout d'abord, la carte utilisateur doit être déplacée à un certain endroit, correspondant à la géolocalisation des photos.

Initialisation de la carte

Il existe deux façons de déterminer la géolocalisation lors de l'initialisation de la carte: utiliser les capacités de HTML5 ou utiliser des coordonnées pré-calculées pour les régions.

Déterminer la géolocalisation à l'aide de HTML5

 function detectRegion() { if (navigator.geolocation) { navigator.geolocation.getCurrentPosition(success); } else { map.setZoom(defaultZoom); map.setCenter(defaultPoint); } } function success(position) { ... map.setZoom(defaultZoom); map.setCenter(new google.maps.LatLng(position.coords.latitude, position.coords.longitude)); } 

L'inconvénient de cette approche est que tous les navigateurs ne prennent pas en charge cette fonctionnalité de HTML5 et l'utilisateur peut ne pas autoriser l'accès à la géoinformation sur son appareil.

Déterminer la géolocalisation à l'aide des informations du serveur

La carte est initialisée dans la section du code source ci-dessous, où les bounds sont les coordonnées de la région (zone peuplée, région ou pays) renvoyées par le serveur. Le niveau de zoom approximatif est calculé dans la fonction getZoomFromBounds (prise à partir de stackoverflow ).

 var northEast = bounds.getNorthEast(); var southWest = bounds.getSouthWest(); var myOptions = { zoom: getZoomFromBounds(northEast, southWest), center: new google.maps.LatLng((northEast.lat() + southWest.lat()) / 2, (northEast.lng() + southWest.lng()) / 2), mapTypeId: google.maps.MapTypeId.ROADMAP, minZoom: 3, maxZoom: 19 } map = new google.maps.Map(document.getElementById("map_canvas"), myOptions); 

 function getZoomFromBounds(ne, sw) { var GLOBE_WIDTH = 256; // a constant in Google's map projection var west = sw.lng(); var east = ne.lng(); var angle = east - west; if (angle < 0) { angle += 360; } return Math.round(Math.log($('#map_canvas').width() * 360 / angle / GLOBE_WIDTH) / Math.LN2); } 

Sur le serveur, les régions sont calculées en fonction de l'adresse IP de l'utilisateur. Pour agréger toutes les coordonnées des limites de chaque région, l' API de géocodage Google a été utilisée, bien qu'il ne soit pas légitime d'utiliser ces informations hors ligne; en outre, il y a une limite de 2500 demandes par jour. Pour chaque ville, région et pays de notre base de données, une requête a été générée qui a renvoyé les limites requises de la viewport et des bounds . Ils ne diffèrent que pour les grandes zones qui ne peuvent pas entrer complètement dans la fenêtre Si le serveur a renvoyé une erreur, d'autres requêtes ont été utilisées dans lesquelles la langue maternelle de cette région ou l'anglais a été utilisée, la partie {Zone peuplée} a été supprimée, etc. http://maps.googleapis.com/maps/api/geocode/xml?address={Country},{Region},{Populated area}&sensor=false

Par exemple, pour la requête suivante: http://maps.googleapis.com/maps/api/geocode/xml?address=Russia, zone Ivanovo% 20, Ivanovo & sensor = false

 ... <location> <lat>56.9951313</lat> <lng>40.9796047</lng> </location> <location_type>APPROXIMATE</location_type> <viewport> <southwest> <lat>56.9420231</lat> <lng>40.8765941</lng> </southwest> <northeast> <lat>57.0703221</lat> <lng>41.0876169</lng> </northeast> </viewport> <bounds> <southwest> <lat>56.9420231</lat> <lng>40.8765941</lng> </southwest> <northeast> <lat>57.0703221</lat> <lng>41.0876169</lng> </northeast> </bounds> ... 

Calcul de zones rectangulaires partiellement visibles

Calcul de la taille des zones de mise en cache

Ainsi, comme mentionné précédemment, toutes les photos côté client et côté serveur sont mises en cache par des zones rectangulaires, dont le point de départ est un point arbitraire (dans notre cas, le point avec les coordonnées (0, 0)), et la taille est calculée en fonction sur le niveau de zoom actuel comme suit:

 // The initial window at which initMapSizeLat and initMapSizeLng were calculated var initDefaultDimX = 1000, var initDefaultDimY = 800; // The current default viewport which depends on the size of the areas. var currentDefaultDimX = 1080, var currentDefaultDimY = 500; var initMapSizeLat = 0.0003019; var initMapSizeLng = 0.00067055; // The coefficient of size reduction (increase). var initRatio = 0.75; // To calculate the size of the smallest caching area, the map was zoomed in to the maximum zoom level // Ie initMapSizeLat and initMapSizeLng were calculated empirically. var initZoomSize = new google.maps.Size( initMapSizeLat / initDefaultDimX * currentDefaultDimX * initRatio, initMapSizeLng / initDefaultDimY * currentDefaultDimY * initRatio); // All subsequent sizes of areas can be calculated based only on the smallest area (by multiplying each size by 2, because with increasing the zoom level by 1, the linear dimensions increase by 2 times, and the quadratic dimensions increase by 4 times). function initZoomSizes() { zoomSizes = []; var coef = 1; for (var i = 21; i >= 0; i--) { zoomSizes[i] = new google.maps.Size(initZoomSize.width * coef, initZoomSize.height * coef); coef *= 2; } } 

Ainsi, à chaque niveau de zoom, la taille de la zone rectangulaire est de 0.75^2=0.5625 rapport à la taille de la fenêtre courante, si elle a une largeur de 1080px et une hauteur de 500px.

Utilisation du délai lors du redessin

Étant donné que le redessin de toutes les photos sur la carte n'est pas une opération rapide (comme cela sera montré plus loin), nous avons décidé de le faire avec un certain retard après l'entrée de l'utilisateur:

 google.maps.event.addListener(map, 'bounds_changed', function () { if (boundsChangedInverval != undefined) clearInterval(boundsChangedInverval); var zoom = map.getZoom(); boundsChangedInverval = setTimeout(function () { boundsChanged(); }, prevZoom === zoom ? moveUpdateDelay : zoomUpdateDelay); prevZoom = zoom; }); 

Calcul des coordonnées et des hachages des zones partiellement visibles

Le calcul des coordonnées et des hachages de tous les rectangles qui chevauchent la fenêtre visible avec des coordonnées ( latMin , lngMin ) et des dimensions calculées en utilisant l'algorithme décrit précédemment se fait comme suit:

 var s = zoomSizes[zoom]; var beginLat = Math.floor((latMin - initPoint.x) / s.width) * s.width + initPoint.x; var beginLng = Math.floor((lngMin - initPoint.y) / s.height) * s.height + initPoint.y; var lat = beginLat; var lng = beginLng; if (lngMax <= beginLng) beginLng = beginLng - 360; while (lat <= maxlat) { lng = beginLng; while (lng <= maxLng) { // lat and normalizeLng(lng) coordinates are the coordinates of the overlapping rectangles. // Longitude normalization is used because the right boundary can be greater than 180 or the left boundary can be less than -180. loadIfNeeded(lat, normalizeLng(lng)); lng += s.height; } lat += s.width; } function normalizeLng(lng) { var rtn = lng % 360; if (rtn <= 0) rtn += 360; if (rtn > 180) rtn -= 360; return rtn; } 

Après cela, pour chaque zone, la fonction suivante est appelée, qui envoie la demande au serveur, si nécessaire. La formule de calcul du hachage renvoie une valeur unique pour chaque zone, car le point de départ et les dimensions sont fixes.

 function loadIfNeeded(lat, lng) { var hash = calculateHash(lat, lng, zoom); if (!(hash in items)) { // Send a query to the database and put this cell in the client cache. } else { // Do nothing. } } function calculateHash(lat, lng, zoom) { // lat: [-90..90] // lng: [-180..180] return (lat + 90) + ((lng + 180) * 180) + (zoom * 64800); } 

Redessiner les photos affichées

Une fois toutes les photos téléchargées ou extraites du cache, certaines doivent être redessinées. Avec un grand nombre de photos ou de marqueurs au même endroit, certaines doivent être masquées, mais il devient alors difficile de savoir combien de photos se trouvent à cet endroit. Pour résoudre ce problème, nous avons décidé de prendre en charge deux types de marqueurs: les marqueurs affichant des photos et les marqueurs indiquant qu'il y a des photos à cet endroit. En outre, si tous les marqueurs sont masqués lorsque les limites sont modifiées, puis sont réaffichés, l'utilisateur peut remarquer un scintillement. Pour résoudre ces problèmes, l'algorithme suivant a été développé:

1. Extraction de toutes les photos visibles du cache client vers le tableau visMarks . Le calcul de ces zones avec des photos a été décrit ci-dessus.
2. Tri des marqueurs reçus par popularité.
3. Recherche de marqueurs superposés à l'aide de markerSize , SmallMarkerSize , minPhotoDistRatio et pixelDistance .
4. Création de tableaux de grands marqueurs avec maxBigVisPhotosCount et de petits marqueurs avec maxSmlVisPhotosCount .
5. Définir les anciens marqueurs qui doivent être masqués et les ajouter à smlMarksToHide et bigMarksToHide aide de refreshMarkerArrays .
6. Mise à jour de l'index de visibilité et de zoom zIndex pour les nouveaux marqueurs qui devraient être affichés à l'aide de updateMarkersVis .
7. Ajout de photos, qui sont devenues visibles à l'heure actuelle, au flux à l'aide d' addPhotoToRibbon .

 function redraw() { isRedrawing = true; var visMarker; var visMarks = []; var visBigMarks2; var visSmlMarks2; var bigMarksToHide = []; var smlMarksToHide = []; var photo; var i, j; var bounds = map.getBounds(); var northEast = bounds.getNorthEast(); var southWest = bounds.getSouthWest(); var latMin = southWest.lat(); var lngMin = southWest.lng(); var latMax = northEast.lat(); var lngMax = northEast.lng(); var ratio = (latMax - latMin) / $("#map_canvas").height(); var zoom = map.getZoom(); visMarks = []; var k = 0; var s = zoomSizes[zoom]; var beginLat = Math.floor((latMin - initPoint.x) / s.width) * s.width + initPoint.x; var beginLng = Math.floor((lngMin - initPoint.y) / s.height) * s.height + initPoint.y; var lat = beginLat; var lng = beginLng; i = 0; if (lngMax <= beginLng) beginLng = beginLng - 360; // Extracting all visible markers. while (lat <= latMax) { lng = beginLng; while (lng <= lngMax) { var hash = calcHash(lat, normLng(lng), zoom); if (!(hash in curItems)) { } else { var item = curItems[hash]; for (photo in item.photos) { if (bounds.contains(item.photos[photo].latLng)) { visMarks[i] = item.photos[photo]; visMarks[i].overlapCount = 0; i++; } } } k++; lng += s.height; } lat += s.width; } // Sorting markers by popularity. visMarks.sort(function (a, b) { if (b.priority !== a.priority) { return b.priority - a.priority; } else if (b.popularity !== a.popularity) { return b.popularity - a.popularity; } else { return b.id - a.id; } }); // Finding overlapping markers and markers that exceed a certain specified number. var curInd; var contains; var contains2; var dist; visBigMarks2 = []; visSmlMarks2 = []; for (i = 0; i < visMarks.length; i++) { contains = false; contains2 = false; visMarker = visMarks[i]; for (j = 0; j < visBigMarks2.length; j++) { dist = pixelDistance(visMarker.latLng, visBigMarks2[j].latLng, zoom); if (dist <= markerSize * minPhotoDistRatio) { contains = true; if (contains && contains2) break; } if (dist <= (markerSize + smallMarkerSize) / 2) { contains2 = true; if (contains && contains2) break; } } if (!contains) { if (visBigMarks2.length < maxBigVisPhotosCount) { smlMarksToHide[smlMarksToHide.length] = visMarker; visBigMarks2[visBigMarks2.length] = visMarker; } } else { bigMarksToHide[bigMarksToHide.length] = visMarker; if (!contains2 && visSmlMarks2.length < maxSmlVisPhotosCount) { visSmlMarks2[visSmlMarks2.length] = visMarker; } else { visBigMarks2[j].overlapCount++; } } } // Adding markers that should be hidden to smlMarksToHide and bigMarksToHide. refreshMarkerArrays(visibleSmallMarkers, visSmlMarks2, smlMarksToHide); refreshMarkerArrays(visibleBigMarkers, visBigMarks2, bigMarksToHide); // Hiding invisible markers and displaying visible markers when zIndex changes. var curZInd = maxBigVisPhotosCount + 1; curZInd = updateMarkersVis(visBigMarks2, bigMarksToHide, true, curZInd); curZInd = 0; curZInd = updateMarkersVis(visSmlMarks2, smlMarksToHide, false, curZInd); visibleBigMarkers = visBigMarks2; visibleSmallMarkers = visSmlMarks2; // Adding visible photos to the feed. trPhotosOnMap.innerHTML = ''; for (var marker in visBigMarks2) { addPhotoToRibbon(visBigMarks2[marker]); } isRedrawing = false; } function refreshMarkerArrays(oldArr, newArr, toHide) { for (var j = 0; j < oldArr.length; j++) { contains = false; var visMarker = oldArr[j]; for (i = 0; i < newArr.length; i++) { if (newArr[i].id === visMarker.id) { contains = true; break; } } if (!contains) { toHide[toHide.length] = visMarker; } } } function updateMarkersVis(showArr, hideArr, big, curZInd) { var marker; var bounds = map.getBounds(); for (var i = 0; i < showArr.length; i++) { var photo = showArr[i]; if (big) { marker = photo.bigMarker; $('#divOvlpCount' + photo.id).html(photo.overlapCount); } else { marker = photo.smlMarker; } marker.setZIndex(++curZInd); if (marker.getMap() === null) { marker.setMap(map); } } for (i = 0; i < hideArr.length; i++) { marker = big ? hideArr[i].bigMarker : hideArr[i].smlMarker; if (marker.getMap() !== null) { marker.setMap(null); marker.setZIndex(0); if (!bounds.contains(hideArr[i].latLng)) hideArr[i].priority = 0; } } return curZInd; } function addPhotoToRibbon(marker) { var td = createColumn(marker); if (isLatLngValid(marker.latLng)) { trPhotosOnMap.appendChild(td); } else { trPhotosNotOnMap.appendChild(td); if (photoViewMode == 'user') { var img = $("#photo" + marker.id).children()[0]; $('#photo' + marker.id).draggable({ helper: 'clone', appendTo: $('#map_canvas'), stop: function (e) { var mapBoundingRect = document.getElementById("map_canvas").getBoundingClientRect(); var point = new google.maps.Point(e.pageX - mapBoundingRect.left, e.pageY - mapBoundingRect.top); var latLng = overlay.getProjection().fromContainerPixelToLatLng(point); marker.latLng = latLng; marker.priority = ++curPriority; placeMarker(marker); }, containment: 'parent', distance: 5 }); } } } 

Distance sur la carte

Pour calculer la distance entre deux points de la carte en pixels, la fonction suivante est utilisée:

 var Offset = 268435456; var Radius = 85445659.4471; function pixelDistance(latLng1, latLng2, zoom) { var x1 = lonToX(latLng1.lng()); var y1 = latToY(latLng1.lat()); var x2 = lonToX(latLng2.lng()); var y2 = latToY(latLng2.lat()); return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) >> (21 - zoom); } function lonToX(lng) { return Math.round(Offset + Radius * lng * Math.PI / 180); } function latToY(lat) { return Math.round(Offset - Radius * Math.log((1 + Math.sin(lat * Math.PI / 180)) / (1 - Math.sin(lat * Math.PI / 180))) / 2); } 

Cette fonction a également été trouvée sur stackoverflow.

Pour que les marqueurs ressemblent à des cercles avec des photos (comme vkontakte), le plugin RichMarker a été utilisé avec l'ajout d'un style arbitraire à l'élément div.

Conclusion

Il s'est avéré que pour afficher les photos sur la carte rapidement et correctement, nous devions résoudre des problèmes assez intéressants et non triviaux liés à la mise en cache et à la géométrie sphérique. Malgré le fait que toutes les méthodes décrites n'ont pas été réellement utilisées dans notre projet, le temps n'a pas été perdu, car l'expérience que nous acquérons pourrait être utile dans d'autres projets, et elle pourrait également être utile pour ceux qui ont lu et compris cet article.