Алгоритм поиска по географической сетке - PullRequest
Новая
       38

Алгоритм поиска по географической сетке

2 голосов
/ 01 июля 2010

Многие сервисы на основе определения местоположения предоставляют API для поиска мест / мест / мест вокруг данной пары широты и долготы.Я изучаю, как я могу искать эти места по всему городу.

Я могу построить сетку для города, получив его границы из геокодера Google Maps, а затем увеличивая широту / долготу, чтобы сложитьуказывает, чтобы сформировать сетку.Я прототипировал эту сетку (нажмите кнопку Fill Grid, чтобы увидеть все точки), чтобы визуализировать эту идею. 

// gather a collection of lat/long pairs that represents a grid of the city
    var latIncrement = .04;
    var lngIncrement = .04;
    var newLat = nw.lat();
    while(newLat >= sw.lat()) {
      var newLng = nw.lng();
      while(newLng <= ne.lng()) {
        // western and northern border as well as grid infill
        addMarker(new google.maps.LatLng(newLat, newLng));
        newLng += lngIncrement;
      }

      // eastern border
      addMarker(new google.maps.LatLng(newLat, ne.lng()));
      newLat -= latIncrement;
    }

    // southern border
    var newLng = sw.lng();
    while(newLng <= se.lng()) {
      addMarker(new google.maps.LatLng(sw.lat(), newLng));
      newLng += lngIncrement;
    }
    addMarker(se);

Затем я могу взять все эти точки и выполнить поискдля них против API LBS.

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

Ответы [ 2 ]

2 голосов
/ 01 июля 2010

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

Что касается плотности мест, у вас есть определенный API, с которым вы собираетесь его использовать? Если вы знаете «досягаемость» точек вашего API при обнаружении мест, вам когда-либо нужно иметь только точки сетки, максимально близкие к их радиусу.

Учитывая вышесказанное, возможно, вы рассматривали вопрос о том, поддерживает ли API непосредственно поиск мест в пределах границы ? Это может быть вашей лучшей и самой чистой ставкой.

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

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

Затем найдите выпуклую оболочку и повторите тот же процесс.

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

0 голосов
/ 27 октября 2016

Пока я столкнулся с той же проблемой.Я придумал решение, в котором вы будете выполнять поиск по сетке рекурсивным способом сверху вниз.Это будет работать, если этот API поддерживает поиск ограничивающего прямоугольника.Изначально примите ваш город как квадрат.Теперь извлекайте данные / места, используя API в этом квадрате (запрос ограничительной рамки).Теперь, если количество возвращенных мест превышает некоторый порог, тогда разделите городскую площадь на 4 равных квадрата и повторите процесс для каждого квадрата.Не разделяйте, если количество возвращаемых мест меньше.Это предотвратит поиск по сетке в нерабочих областях (квадратах), таких как леса, реки и т. Д. Вот прототип кода Python для этого:

Здесь fetch - это функция, которая извлекает результаты из API на основе ограничивающего прямоугольника с юго-западом swширота, логитический кортеж и ne как северо-восточная широта, логитический кортеж 

allresults = []

def grid_search(sw,ne):
    global results
    results = fetch(sw,ne)
    if len(results) <= 10:
        return
    allresults.append(results)
    swlat,swlon = sw
    nelat,nelon = ne
    grid_search( (swlat + delta, swlon), (nelat, sw + delta) )
    grid_search( (swlat + delta, swlon + delta), ne )
    grid_search( sw, (swlat + delta, swlon + delta) )
    grid_search( (swlat,swlon + delta), (swlat + delta, nelon) )
...