Каков наилучший подход для поиска всех адресов, находящихся на определенном расстоянии до выбранной точки

Ответ 1

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

• radiansLongitude (Math.toRadians(longitude))
• sinRadiansLatitude (Math.sin(Math.toRadians(latitude))
• cosRadiansLatitude (Math.cos(Math.toRadians(latitude))

Затем, когда я ищу места, которые находятся внутри единиц X latitude/longitude, мой подготовленный оператор выглядит следующим образом:

from Location l where
    acos(
        sin(:latitude) * sinRadiansLatitude + 
        cos(:latitude) * cosRadiansLatitude * 
        cos(radiansLongitude - :longitude) 
        ) * YYYY < :distance
    and l.latitude>:minimumSearchLatitude
    and l.latitude<:maximumSearchLatitude 
    and l.longitude>:minimumSearchLongitude 
    and l.longitude<:maximumSearchLongitude 
    order by acos(
                sin(:latitude) * sinRadiansLatitude + 
                cos(:latitude) * cosRadiansLatitude * 
                cos(radiansLongitude - :longitude)  
        ) * YYYY asc

Где YYYY= 3965 дает расстояние в милях или YYYY= 6367 можно использовать для расстояний в км.

Наконец, я использовал параметры maximumSearchLatitude/maximumSearchLongitude/minimumSearchLongitude/maximumSearchLongitude, чтобы исключить большинство точек из набора результатов до того, как база данных выполнит какие-либо вычисления. Вы можете или не нуждаться в этом. Если вы будете использовать это, вам понадобятся, какие значения вы выберете для этих параметров, так как это будет зависеть от того, что вы ищете.

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

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

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

Отказ от ответственности: я долго смотрел на это, и я не специалист по ГИС!

Ответ 2

Вы можете выполнять расчетную серверную часть в самом запросе, а не на стороне клиента, получая при этом только результаты расчета. Здесь (ссылка на архив для потомков) является примером Haversine- (извините, статья просто слишком длинна для меня, чтобы скопировать + вставить или суммировать здесь, хотя это отличная статья и простое чтение).

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

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

Ответ 3

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

@Transactional
public List<Double> getAllPoisAroundUser(double longitude, double latitude, int page) {

Query query = getSessionFactory().getCurrentSession().createSQLQ uery("SELECT (6371 * 2 * ASIN(SQRT(POWER(SIN((:ulatitude - abs(latitude)) * pi()/180 / 2),2) +" +
"COS(:ulatitude * pi()/180 ) * COS(abs(latitude) * pi()/180) *" +
"POWER(SIN((:ulongitude - longitude) * pi()/180 / 2), 2))))*1000 as distance " +
"FROM poi HAVING distance < 5000 ORDER BY distance");

query.setParameter("ulongitude", longitude);
query.setParameter("ulatitude", latitude);
query.setFirstResult((page-1)*10);
query.setMaxResults(10);

return (List<Double>) query.list();
}

Ответ 4

Я использую спящий режим и делаю это следующим образом:

public List<Tour> searchTours(double lat, double lon, double distance) {

    Session session = getSession();

    Criteria criteria = session.createCriteria(Tour.class, "tour");

    //
    // 1 Grad lat = 111 km
    // 1 grad lon = cos(lat) * 111
    //
    final double KM_IN_ONE_LAT = 111.0;

    double t1 = distance / Math.abs(Math.cos(Math.toRadians(lat)) * KM_IN_ONE_LAT);
    double t2 = distance / KM_IN_ONE_LAT;

    double lonA = lon - t1;
    double lonB = lon + t1;

    double latA = lat - t2;
    double latB = lat + t2;

    Criterion c1 = Restrictions.between("longitude", lonA, lonB);
    Criterion c2 = Restrictions.between("latitude", latA, latB);

    criteria.add(c1);
    criteria.add(c2);

    criteria.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY);

    return criteria.list();
}

Проверьте эту статью для получения дополнительной информации: Geo (proximity) Поиск с MySQL

Ответ 5

Насколько вы точны. Использование индекса gg postgres или индекса r-дерева может быть полезным в качестве отправной точки. Затем выполните запрос ограничивающей рамки. Затем выполните радиальное расстояние на клиенте. Таким образом, математика FP не выполняется центральным сервером (затухающая масштабируемость). Моя проблема заключается в том, что ГИС и rtrees являются самыми медленными типами индексов (ориентированы только на индексы FTS). Поэтому я обычно выбирал 1D-индексы, такие как geohash. Если у вас есть данные о точках, просто сохраните все в общем GSD (Ground Sample Distance), например, 10 метров или 1 метр или что-вы-вы.. Вы строите ' string '(обычно с кодировкой base-64), который является lat-long (каждый бит чередует lat и long). Точки хранятся в виде простого индекса строки в БД (очень эффективны для индексирования и хранения). Затем для запросов вы должны создать ограничительную рамку из точки поиска по всему интересующему вас гео-хэшу... Если у вас очень большие радиусы, это должно сузить результаты поиска... Сделайте окончательная фильтрация в клиенте (или использование одного из методов, перечисленных другим для предварительно рассчитанных значений триггера).

Проблема, однако, в том, что просеивание через 1М точек происходит быстро. Сделать 1000 случайных дисков доступ непригодным. Так что даже если у вас хороший гео-хэш, если у него много случайных точек; это не сработает.

То, что я обычно делал, это bin на диске все соответствующие блоки данных. Таким образом, гео-поиск дает вам конечный набор дисковых расположений... Затем вы загружаете ВСЕ данные (несколько десятков МБ) до 4 дисковых нагрузок. Затем просеиваем всю геометрию. Это может быть на 1000 раз быстрее в лучшем случае (vs .s.000 rand access). Но, очевидно, имеет серьезные ограничения на то, как вы сначала сохранили эти данные в сетках (полностью переписывая или фиксируя размер ваших ящиков).

Очевидно, если у вас достаточно ОЗУ для кэширования всей БД, тогда запустите его. Алгоритм не будет иметь большого значения. Сначала подумайте о шаблонах доступа к диску. Затем шаблоны доступа к процессору (вы можете масштабировать процессоры, но трудно поддерживать дубликаты данных вашего диска).

Ответ 6

План A: Поскольку у вас есть 300K строк, INDEX (lat) является не стартером, с точки зрения производительности, даже с ограничением на полосу: AND lat BETWEEN 65 AND 69. INDEX(lat, lng) не лучше, потому что оптимизатор не будет использовать оба столбца, даже с AND lng BETWEEN...

План B: Следующий выбор будет включать lat и lng, плюс подзапрос. И версия 5.6 была бы полезна. Это что-то вроде этого (после включения INDEX(lat, lng, id)):

SELECT ... FROM (
    SELECT id FROM tbl
        WHERE lat BETWEEN... 
          AND lng BETWEEN... ) x
    JOIN tbl USING (id)
    WHERE ...;

По разным причинам Plan B немного лучше, чем Plan A.

План C: если вам понадобятся миллионы строк, вам понадобится мой алгоритм pizza-салона. Это включает в себя хранимую процедуру для многократного зондирования, ища достаточно строк. Он также включает PARTITION ing для получения грубого 2D-индекса.

Планы A и B O(sqrt(N)); План C - O(1). То есть для планов A и B, если вы в четыре раза увеличиваете количество строк, вы удваиваете время. План C не замедляется по мере увеличения N.

Ответ 7

Вы можете использовать необработанный запрос для выбора списка идентификаторов формы таблицы адресов в спящем режиме.

public List<Long> getNearByLocations(float latitude, float longitude,
            float distance) {
        Session sess = getSession();
        String queryString = "SELECT id, (6371 * acos (cos(radians("
                + latitude
                + ")) * cos(radians(latitude)) * cos(radians(longitude) - radians("
                + longitude
                + "))  + sin(radians("
                + latitude
                + ")) * sin(radians(latitude)))) AS distance FROM Address HAVING distance < "
                + distance + " ORDER BY distance";
        Query qry = sess.createSQLQuery(queryString);

        List<Object[]> list = null;
        list = qry.list();
        List<Long> idList = new ArrayList<>();
        for (Object[] obj : list) {
            Long id = (Long) obj[0];
            idList.add(id);
        }
        return idList;
    }

Ответ 8

Он не эффективен и не масштабируется для запроса всей таблицы базы данных. Рассмотрите возможность использования R-tree для повышения производительности.