Реализация выборки, кэширования и отрисовки фотографий на карте

    Дисклеймер. Оригинальная статья была написана в августе 2013 года, поэтому сейчас, в 2017 году, часть материала может быть не актуальна.


    В данной статье я решил описать как была реализована функциональность выборки и отображения фотографий на определенном участке карты в нашем фото-сервисе gfranq.com. Сейчас данный фото-сервис не работает.


    Title image


    Так как в нашем сервисе было очень много фотографий и посылать запросы к БД при каждом изменении окна просмотра слишком ресурсозатратно, логично было разбить карту на участки, в которых хранилась бы информация об уже извлеченных данных. Эти участки по вполне понятным причинам имеют прямоугольную форму (хотя вариант с гексагональной сеткой тоже рассматривался). Так как при больших масштабах участки становятся более сферообразными, то элементы сферическое геометрии и инструменты для работы с ней также были рассмотрены.


    В данной статье были затронуты следующие проблемы:


    • Хранение и выборка фотографий из БД и помещение их в серверный кэш (SQL, C#, ASP.NET).
    • Загрузка необходимых фотографий на стороне клиента и помещение их в клиентский кэш (JavaScript).
    • Перерасчет фотографий, которые нужно скрыть или отобразить при каждом изменении окна просмотра.
    • Элементы сферической геометрии.


    Содержание



    Серверная часть


    Были придуманы следующие способы выборки и хранения геоинформации в БД:


    • Встроенных географические типы SQL Server.
    • Обычная выборка с ограничениями.
    • Использование дополнительной таблицы.

    Далее эти способы будут рассмотрены подробно.


    Встроенные геотипы


    Как известно, в SQL Server 2008 появилась поддержка типов geography и geometry, которые позволяют задавать географическую (на сфере) и геометрическую (на плоскости) информацию, такие как точки, линии, многоугольники и т.д. Для того, чтобы получить все фотографии, заключенные прямоугольником с координатами (lngMin latMin) и (latMax lngMax), можно воспользоваться следующим запросом:


    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

    Обратите внимание, что полигон обходится против часовой стрелки и используется пространственный индекс IX_Photo_geoTag, построенный по координатам (кстати, пространственные индексы работают по принципу B-деревьев).


    Однако оказалось, что в Microsoft SQL Server 2008 пространственные индексы не работают в случае, если колонка с геотипами может принимать NULL значения, а также составной индекс не может содержать в себе колонку с типом geography, и этот вопрос был затронут на stackoverflow. Из-за этого производительность таких запросов (без индексов) становится очень низкой.


    В качестве решения такой проблемы можно предложить следующее:


    • Так как NULL значения использовать нельзя, то по-умолчанию в этой колонке находятся координаты (0 0), которую указывают на точку в Атлантическом океане недалеко от Африки (Оттуда начинается отсчет долготы и широты). Однако в этой точке, а также поблизости могут располагаться и реальные точки, а значит фотографии не на карте нужно как-то игнорировать. Если же изменить точку (0 0) на (0 90), то все будет гораздо лучше, потому что широта 90 указывает фактически на край карты, а значит при построении сетки исключать эту широту (т.е. строить до 89).
    • Изменение версии SQL Server до 110 посредством команды ALTER DATABASE database_name SET COMPATIBILITY_LEVEL = 110. В этой версии исправлена ошибка с индексацией NULL geography типов, а также добавлена поддержка многоугольников разной ориентации (в запросе выше полигон можно будет задавать и против и по часовой стрелке).

    Несмотря на широкие возможности географических типов (а они позволяют производить не только такую простую выборку, указанную в примере выше, но и использовать расстояния, различные многоугольники), они не были использованы у нас в проекте.


    Обычная выборка


    Выборку фотографий из области, ограниченной координатами (lngMin latMin) и (latMax lngMax), несложно реализовать с помощью следующего запроса:


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

    Стоит отметить, что для полей latitude и longitude в данном случае можно создавать любые индексы (в отличие от первого варианта), поскольку они являются обычными типами float. Однако в данной выборке присутствует 4 сравнения.


    Использование дополнительной таблицы с хешами


    Наиболее оптимальное решение проблемы выборки фотографий из определенных областей заключается в создании дополнительной таблицы Zooms, которая хранила бы в себе строки, содержащие в себе хеши областей для каждого зума, как это отображено на рисунке ниже.


    Table with hashes


    SQL запрос при этом приобретает следующий вид (zn — текущий уровень зума):


    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)

    Недостатком такого подхода является то, что дополнительная таблица занимает дополнительное место в памяти.


    Несмотря на достоинство последнего метода, на сервере был реализован второй вариант с обычной выборкой, так как и он показал вполне неплохую производительность.


    Кэширование фотографий при многопоточном доступе


    После того, как информация была извлечена из БД тем или иным образом, фотографии помещаются в серверный кэш следующим образом с использованием синхронизирующего объекта для поддержки многопоточности:


    private static object SyncObject = new object();
    ...
    List<Photo> photos = (List<Photo>)CachedAreas[hash];
    if (photos == null)
    {
        // Использование блокировки не того, чтобы не случилось ситуации извлечения и вставки в кэш более 1 раза.
        lock (SyncObject)
        {
            photos = (List<Photo>)CachedAreas[hash];
            if (photos == null)
            {
                photos = PhotoList.GetAllFromRect(latMin, lngMin, latMax, lngMax, count);
                // Добавление информации о фотографиях в кэш с временем хранения 2 минуты с высоким приоритетом хранения.
                CachedAreas.Add(hash, photos, null, DateTime.Now.AddSeconds(120), Cache.NoSlidingExpiration, CacheItemPriority.High, null);
            }
        }
    }
    // Дальнейшее использование CachedAreas[hash]

    В данном разделе была описана серверная функциональность для выборки фотографий из БД и их сохранения в кэш. В следующем разделе будет описано то, что происходит на стороне клиента в браузере.


    Клиентская часть


    Для визуализации карты и фотографий на ней использовался Google Maps API. Для начала карту у пользователя нужно переместить в определенное подходящее место, соответствующее их геолокации.


    Инициализация карты


    Существуют два способа определения местоположения при инициализации карты. Первый заключается в использовании возможностей HTML5, а второй — в использовании заранее расчитанных координат для всех регионов.


    Определение местоположения с помощью 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));
    }

    Недостатком такого подхода является то, что не все браузеры поддерживают данную функцию HTML5, к тому же пользователь может не разрешать доступ к геоинформации на своем устройстве.


    Определение местоположения с помощью информации с сервера


    Инициализация карты производится в следующем участке исходного кода, в котором bounds — координаты региона (насленного пункта, области или страны), возращенные сервером. Определение приблизительного уровня зума определяется по алгоритму, приведенному в функции getZoomFromBounds (позаимствовано из 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);
    }

    На сервере регионы вычисляются на основе IP пользователя. Для агрегации всех координат границ для каждого региона использовался google geocoding api, хотя и использование такой информации в оффлайне не является правомерным, кроме того там есть ограничение на 2500 запросов в день. Для каждого города, области и страны из нашей базы данных формировался запрос, который возвращал искомые границы viewport и bounds. Они различаются только для больших областей, которые не могут полностью поместиться в окно просмотра. При этом если возвращался ответ с ошибкой, то использовались другие запросы, в которых комбинировалось написание на родном для этого региона языке или английском, убиралась часть {Населенный пункт} и т. д. http://maps.googleapis.com/maps/api/geocode/xml?address={Страна},{Область/Штат},{Населенный пункт}&sensor=false


    Например для такого запроса: http://maps.googleapis.com/maps/api/geocode/xml?address=Россия, Ивановская%20область, Иваново&sensor=false


    Будут возвращаться следующие координаты (фрагмент)

    ```html

    56.9951313
    40.9796047

    <location_type>APPROXIMATE</location_type>
    56.9420231
    40.8765941

    57.0703221
    41.0876169


    56.9420231
    40.8765941

    57.0703221
    41.0876169



    ```


    Расчет частично видимых прямоугольных областей


    Расчет размера кэширующих областей


    Итак, как уже было отмечено ранее, все фотографии и на клиенте и на сервере кэшируются по прямоугольным областям, точкой отсчета которых является произвольная точка (в нашем случае точка с координатами (0, 0)), а размер вычисляется в зависимости от текущего уровня приближения (зума) следующим образом:


    // Первоначальное окошко, при котором вычислялось initMapSizeLat и initMapSizeLng
    var initDefaultDimX = 1000, var initDefaultDimY = 800;
    // Текущее окно просмотра по умолчанию, которое зависит на размер областей.
    var currentDefaultDimX = 1080, var currentDefaultDimY = 500;
    var initMapSizeLat = 0.0003019; var initMapSizeLng = 0.00067055;
    // Коэффициент уменьшения(увеличения) размера.
    var initRatio = 0.75;
    
    // Для вычисления этого размера наименьшей кэширующей области карта была приближена до максимального уровня зума
    // Т.е. initMapSizeLat и initMapSizeLng были вычислены эмпирически.
    var initZoomSize = new google.maps.Size(
    initMapSizeLat / initDefaultDimX * currentDefaultDimX * initRatio,
    initMapSizeLng / initDefaultDimY * currentDefaultDimY * initRatio);
    
    // Все последующие размеры областей можно вычислить, основываясь только на наименьшей (путем умножения каждого размера на 2, потому что при увеличении уровня зума на 1, линейные размеры увеличиваются в 2 раза, а квадратичные - в 4).
    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;
        }
    }

    Таким образом, на каждом уровне зума, размер прямоугольной области по площади составляет 0.75^2=0.5625 от текущего окна просмотра, если его ширина = 1080px и высота = 500px.


    Использование задержки при перерисовке


    Так как перерисовка всех фотографий на карте не очень быстрая операция (как будет показано позже), то решено было ее сделать с определенной задержкой после пользовательского ввода:


    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;
    });

    Расчет координат и хешей частично видимых областей


    Расчет координат и хешей всех прямоугольников, перекрывающих видимое окно с координатами (latMin, lngMin) и размерами, вычисленных по алгоритму, описанному ранее, производится следующим образом:


    Coordinates and hashes calculation


    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 и normalizeLng(lng) являются координатами перекрывающихся прямоугольников.
            // Нормализация долготы используется из-за того, что правая граница может быть больше чем 180 или левая меньше чем -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;
    }

    Затем для каждой области вызывается следующая функция, которая посылает запрос к серверу при необходимости. Формула расчета хеша возвращает уникальное значение для каждой области, потому что точка отсчета и размеры фиксированы.


    function loadIfNeeded(lat, lng) {
        var hash = calculateHash(lat, lng, zoom);
        if (!(hash in items)) {
            // Сделать запрос к БД и занести данную ячейку в клиентский кэш.
        } else {
            // Не производить никаких действий.
        }
    }
    
    function calculateHash(lat, lng, zoom) {
        // lat: [-90..90]
        // lng: [-180..180]
        return (lat + 90) + ((lng + 180) * 180) + (zoom * 64800);
    }

    Перерисовка отображаемых фотографий


    После того, как все фотографии загружены или извлечены из кэша, часть из них нужно перерисовать. При большом скоплении фотографий, а точнее маркеров, в одном месте, часть из них желательно нужно скрывать, однако становится непонятно, сколько именно фотографий располагается в данном месте. Для решения этой проблемы было решено сделать поддержку двух типов маркеров: маркеры, отображающие фотографии, и маркеры, отображающие, что в данном месте есть фотографии. Также если все маркеры скрывать при изменении границ, а потом заново их отображать, то будет заметно мерцание. Для решения вышеописанных проблем был разработан следующий алгоритм:


    1. Извлечение всех видимых фотографий из клиентского кэша в массив visMarks. Расчет данных областей с фотографиями был описаны выше.
    2. Сортировка полученных маркеров по популярности.
    3. Определение перекрывающихся маркеров с использованием markerSize, smallMarkerSize, minPhotoDistRatio и функции pixelDistance.
    4. Создание массивов из больших маркеров с количеством maxBigVisPhotosCount и маленьких с количеством maxSmlVisPhotosCount.
    5. Определение старых маркеров, которые нужно скрыть и занесение их в smlMarksToHide и bigMarksToHide c помощью refreshMarkerArrays.
    6. Обновление видимости и индекса глубины zIndex для новых маркеров, которые нужно отобразить с помощью updateMarkersVis.
    7. Добавление фотографий, которые стали видимыми в текущий момент времени, в ленту сверху с помощью addPhotoToRibbon.

    Алгоритм пересчета видимых маркеров

    ```JavaScript
    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;

    // Извлечение всех видимых маркеров.
    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;
    }

    // Сортировка маркеров по популярности.
    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;
    }
    });

    // Определение перекрывающихся маркеров и маркеров, превышающих определенное заданное количество.
    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++;
    }
    }
    }

    // Занесение маркеров, которые нужно скрыть в smlMarksToHide и bigMarksToHide соответственно.
    refreshMarkerArrays(visibleSmallMarkers, visSmlMarks2, smlMarksToHide);
    refreshMarkerArrays(visibleBigMarkers, visBigMarks2, bigMarksToHide);

    // Сокрытие невидимых и отображение видимых маркеров с изменение zIndex.
    var curZInd = maxBigVisPhotosCount + 1;
    curZInd = updateMarkersVis(visBigMarks2, bigMarksToHide, true, curZInd);
    curZInd = 0;
    curZInd = updateMarkersVis(visSmlMarks2, smlMarksToHide, false, curZInd);

    visibleBigMarkers = visBigMarks2;
    visibleSmallMarkers = visSmlMarks2;

    // Добавление видимых фотографий в ленту.
    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
    });
    }
    }
    }
    ```


    Расстояние на карте


    Для получения расстояния между двумя точками на карте в пикселях используется следующая функция:


    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);
    }

    Данная функция тоже была найдена на просторах stackoverflow.


    Для стилизации маркеров, чтобы они выглядели как кружки с фотографиями как вконтакте, использовался плагин RichMarker с добавление произвольного стиля элементу div.


    Заключение


    Как оказалось, для того, чтобы фотографии на карте отображались быстро и правильно, потребовалось решить довольно интереснех и нетривиальне задачи, связанные с кэшированием и сферической геометрией. Несмотря на то, что не все используемые методы реально использовались у нас в проекте, время не было потрачено зря, т.к. приобритенный опыт может пригодится в других проектах, а также может оказаться полезным для тех, кто прочитал и вник в эту статью.

    • +16
    • 9,2k
    • 6
    Поделиться публикацией
    Похожие публикации
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 6
    • 0
      По коду не совсем понял, сколько раз при запросе списка изображений выполняется обращение к БД? А то вижу циклы, вижу проверки на вхождение в список.
      И еще вопрос, имеет ли хэш функция какую-либо привязку к особенностям координатной сетки для ускорения выборки?
      • 0
        Сейчас сделано так, что сначала на клиенте определяются прямоугольные области, в которые нужно загрузить фотографии, затем эта информация склеивается в один запрос и отправляется на сервер. Т.е. при инициализации создается один запрос на 9 областей (если все происходит так, как на картинке в статье). Затем при пересечении других областей, запрос будет охватывать меньше областей (3 прямоугольника если двигать только влево, вправо или вверх, вниз).

        И еще вопрос, имеет ли хэш функция какую-либо привязку к особенностям координатной сетки для ускорения выборки?

        Не совсем понял вопрос. Вообще нет такой особенности. Вычисляется так, как было описано, в зависимости от размеров областей и точки отсчета. Хотя если вы про третий способ выборки из БД, то там наверное можно было обойтись целыми числами, правда не известно, повлияло бы это на производительность существенно.
        • +1
          Просто в плане хэша можно было бы реализовать довольно хитро, сам использую такое:
          — все координаты сводятся к XYZ, тоестьномер тайла на котом лежит картинка;
          — любую пару XY можно представить числом, которое собирается по следующему правилу: биты из Y чередуются с битами из X, младший бит идет из X;
          — получить индексы нижележащих уровней Z можно взять (XY) (XY+1) собрать в индекс и каждый сдвинуть на удвоенную разницу уровней влево.

          Данная схема работает, проверено в боевых условиях.

          В итоге, координата внутри хранится дополнительно как число для Z=18. При запросе передаются координаты левого-верхнего правого-нижнего и зум. Вычисляется граница индекса и в результате получаем простой запрос по интервалу. Если есть несколько зон, можно добавить в условие выборки, не думаю, что сильно просадит скорость.
      • +1
        А сервер работает на asp.net?
      • 0
        Почитал, пока лишь по диагонали. В избранное до лучших времен, может и пригодится.

        Спасибо!

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.