SQlite Obtendo locais mais próximos (com latitude e longitude)

86

Tenho dados com latitude e longitude armazenados em meu banco de dados SQLite e desejo obter os locais mais próximos dos parâmetros que coloquei (por exemplo, minha localização atual - lat / lng etc.).

Eu sei que isso é possível no MySQL, e fiz algumas pesquisas que o SQLite precisa de uma função externa personalizada para a fórmula Haversine (calcular a distância em uma esfera), mas não encontrei nada que seja escrito em Java e funcione .

Além disso, se eu quiser adicionar funções personalizadas, preciso do org.sqlite.jar (para org.sqlite.Function) e isso adiciona um tamanho desnecessário ao aplicativo.

O outro lado disso é, eu preciso da função Order by do SQL, porque exibir a distância sozinha não é um grande problema - eu já fiz isso no meu SimpleCursorAdapter personalizado, mas não consigo classificar os dados, porque não tenho a coluna de distância em meu banco de dados. Isso significaria atualizar o banco de dados toda vez que o local mudar e isso seria um desperdício de bateria e desempenho. Portanto, se alguém tiver alguma ideia sobre como classificar o cursor com uma coluna que não está no banco de dados, eu também ficaria grato!

Eu sei que existem toneladas de aplicativos Android por aí que usam essa função, mas alguém pode explicar a mágica.

A propósito, encontrei esta alternativa: Consultar para obter registros com base no Radius no SQLite?

Ele está sugerindo fazer 4 novas colunas para os valores de cos e sin de lat e lng, mas existe alguma outra maneira não tão redundante?

Jure
fonte
Você verificou se org.sqlite.Function funciona para você (mesmo se a fórmula não estiver correta)?
Thomas Mueller
Não, eu encontrei uma alternativa (redundante) (publicação editada) que soa melhor do que adicionar 2,6 MB .jar no aplicativo. Mas ainda estou procurando uma solução melhor. Obrigado!
Jure
Qual é o tipo de unidade de distância de retorno?
Aqui está uma implementação completa para construir uma consulta SQlite no Android com base na distância entre a sua localização e a localização do objeto.
EricLarch

Respostas:

111

1) Primeiro filtre seus dados SQLite com uma boa aproximação e diminua a quantidade de dados que você precisa avaliar em seu código java. Use o seguinte procedimento para este propósito:

Para ter um limite determinístico e um filtro de dados mais preciso, é melhor calcular 4 locais que estão em radiusmetros a norte, oeste, leste e sul de seu ponto central em seu código Java e então verificar facilmente por menos de e mais de Operadores SQL (>, <) para determinar se seus pontos no banco de dados estão naquele retângulo ou não.

O método calculateDerivedPosition(...)calcula esses pontos para você (p1, p2, p3, p4 na imagem).

insira a descrição da imagem aqui

/**
* Calculates the end-point from a given source at a given range (meters)
* and bearing (degrees). This methods uses simple geometry equations to
* calculate the end-point.
* 
* @param point
*           Point of origin
* @param range
*           Range in meters
* @param bearing
*           Bearing in degrees
* @return End-point from the source given the desired range and bearing.
*/
public static PointF calculateDerivedPosition(PointF point,
            double range, double bearing)
    {
        double EarthRadius = 6371000; // m

        double latA = Math.toRadians(point.x);
        double lonA = Math.toRadians(point.y);
        double angularDistance = range / EarthRadius;
        double trueCourse = Math.toRadians(bearing);

        double lat = Math.asin(
                Math.sin(latA) * Math.cos(angularDistance) +
                        Math.cos(latA) * Math.sin(angularDistance)
                        * Math.cos(trueCourse));

        double dlon = Math.atan2(
                Math.sin(trueCourse) * Math.sin(angularDistance)
                        * Math.cos(latA),
                Math.cos(angularDistance) - Math.sin(latA) * Math.sin(lat));

        double lon = ((lonA + dlon + Math.PI) % (Math.PI * 2)) - Math.PI;

        lat = Math.toDegrees(lat);
        lon = Math.toDegrees(lon);

        PointF newPoint = new PointF((float) lat, (float) lon);

        return newPoint;

    }

E agora crie sua consulta:

PointF center = new PointF(x, y);
final double mult = 1; // mult = 1.1; is more reliable
PointF p1 = calculateDerivedPosition(center, mult * radius, 0);
PointF p2 = calculateDerivedPosition(center, mult * radius, 90);
PointF p3 = calculateDerivedPosition(center, mult * radius, 180);
PointF p4 = calculateDerivedPosition(center, mult * radius, 270);

strWhere =  " WHERE "
        + COL_X + " > " + String.valueOf(p3.x) + " AND "
        + COL_X + " < " + String.valueOf(p1.x) + " AND "
        + COL_Y + " < " + String.valueOf(p2.y) + " AND "
        + COL_Y + " > " + String.valueOf(p4.y);

COL_Xé o nome da coluna no banco de dados que armazena os valores de latitude e COL_Yserve para longitude.

Portanto, você tem alguns dados próximos ao seu ponto central com uma boa aproximação.

2) Agora você pode fazer um loop nesses dados filtrados e determinar se eles estão realmente próximos do seu ponto (no círculo) ou não usando os seguintes métodos:

public static boolean pointIsInCircle(PointF pointForCheck, PointF center,
            double radius) {
        if (getDistanceBetweenTwoPoints(pointForCheck, center) <= radius)
            return true;
        else
            return false;
    }

public static double getDistanceBetweenTwoPoints(PointF p1, PointF p2) {
        double R = 6371000; // m
        double dLat = Math.toRadians(p2.x - p1.x);
        double dLon = Math.toRadians(p2.y - p1.y);
        double lat1 = Math.toRadians(p1.x);
        double lat2 = Math.toRadians(p2.x);

        double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.sin(dLon / 2)
                * Math.sin(dLon / 2) * Math.cos(lat1) * Math.cos(lat2);
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
        double d = R * c;

        return d;
    }

Aproveitar!

Usei e customizei esta referência e concluí.

Bobs
fonte
Confira a ótima página da web de Chris Veness se você estiver procurando por uma implementação Javascript desse conceito acima. movable-type.co.uk/scripts/latlong.html
barneymc
@Menma x é latitude ey é longitude. raio: o raio do círculo mostrado na imagem.
Bobs de
a solução dada acima está correta e funciona. Experimente ... :)
YS
1
Esta é uma solução aproximada! Ele fornece resultados altamente aproximados por meio de uma consulta SQL rápida e compatível com o índice. Ele dará um resultado errado em algumas circunstâncias extremas. Depois de obter um pequeno número de resultados aproximados em uma área de vários quilômetros, use métodos mais lentos e precisos para filtrar esses resultados . Não o use para filtrar com raios muito grandes ou se seu aplicativo vai ser usado com frequência no equador!
user1643723
1
Mas eu não entendo. CalculateDerivedPosition está transformando a coordenada lat, lng em uma cartesiana e, em seguida, na consulta SQL, você está comparando esses valores cartesianos com os valores lat, long. Duas coordenadas geométricas diferentes? Como é que isso funciona? Obrigado.
Misgevolution
70

A resposta de Chris é realmente útil (obrigado!), Mas só funcionará se você estiver usando coordenadas retilíneas (por exemplo, referências de grade UTM ou OS). Se estiver usando graus para lat / lng (por exemplo, WGS84), o acima só funciona no equador. Em outras latitudes, você precisa diminuir o impacto da longitude na ordem de classificação. (Imagine que você está perto do pólo norte ... um grau de latitude ainda é o mesmo que em qualquer lugar, mas um grau de longitude pode ser de apenas alguns pés. Isso significa que a ordem de classificação está incorreta).

Se você não estiver no equador, pré-calcule o fator de correção, com base em sua latitude atual:

<fudge> = Math.pow(Math.cos(Math.toRadians(<lat>)),2);

Em seguida, peça por:

((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) + (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN) * <fudge>)

Ainda é apenas uma aproximação, mas muito melhor do que o primeiro, portanto, imprecisões na ordem de classificação serão muito mais raras.

Carda
fonte
3
Esse é um ponto realmente interessante sobre as linhas longitudinais convergindo nos pólos e distorcendo os resultados quanto mais perto você chega. Boa correção.
Chris Simpson,
1
isto parece funcionar cursor = db.getReadableDatabase (). rawQuery ("Selecione o nome, id como _id," + "(" + latitude + "- lat) * (" + latitude + "- lat) + (" + longitude + "- lon) * (" + longitude + "- lon) *" + fudge + "as distanza" + "do cliente" + "pedido por distanza asc", null);
max4ever
deve ((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) + (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN) * <fudge>)ser menor que distanceou distance^2?
Bobs
Não é o fator de correção em radianos e as colunas em graus? Eles não deveriam ser convertidos para a mesma unidade?
Rangel Reale
1
Não, o fator de correção é um fator de escala que é 0 nos pólos e 1 no equador. Não está em graus nem em radianos, é apenas um número sem unidade. A função Java Math.cos requer um argumento em radianos e presumi que <lat> estava em graus, daí a função Math.toRadians. Mas o cosseno resultante não tem unidades.
Teasel de
68

Sei que isso foi respondido e aceito, mas pensei em acrescentar minhas experiências e soluções.

Embora eu estivesse feliz em fazer uma função de haversine no dispositivo para calcular a distância precisa entre a posição atual do usuário e qualquer local de destino específico, havia a necessidade de classificar e limitar os resultados da consulta em ordem de distância.

A solução menos do que satisfatória é retornar o lote e classificar e filtrar após o fato, mas isso resultaria em um segundo cursor e muitos resultados desnecessários sendo retornados e descartados.

Minha solução preferida era passar em uma ordem de classificação dos valores delta quadrados de long e lats:

((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) +
 (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN))

Não há necessidade de fazer o haversine completo apenas para uma ordem de classificação e não há necessidade de raiz quadrada dos resultados, portanto, o SQLite pode lidar com o cálculo.

EDITAR:

Essa resposta ainda está recebendo amor. Funciona bem na maioria dos casos, mas se você precisar de um pouco mais de precisão, verifique a resposta de @Teasel abaixo, que adiciona um fator "fudge" que corrige imprecisões que aumentam conforme a latitude se aproxima de 90.

Chris Simpson
fonte
Ótima resposta. Você poderia explicar como funcionou e como é chamado esse algoritmo?
iMatoria
3
@iMatoria - Esta é apenas uma versão reduzida do famoso teorema de Pitágoras. Dados dois conjuntos de coordenadas, a diferença entre os dois valores X representa um lado de um triângulo retângulo e a diferença entre os valores Y é o outro. Para obter a hipotenusa (e, portanto, a distância entre os pontos), você soma os quadrados desses dois valores e, a seguir, elabora a raiz quadrada do resultado. No nosso caso, não fazemos a última parte (o enraizamento do quadrado) porque não podemos. Felizmente, isso não é necessário para uma ordem de classificação.
Chris Simpson,
6
No meu aplicativo BostonBusMap, usei essa solução para mostrar as paradas mais próximas do local atual. No entanto, você precisa dimensionar a distância da longitude cos(latitude)para que a latitude e a longitude sejam aproximadamente iguais. Consulte en.wikipedia.org/wiki/…
noisecapella de
0

A fim de aumentar o desempenho tanto quanto possível, sugiro melhorar a ideia de @Chris Simpson com a seguinte ORDER BYcláusula:

ORDER BY (<L> - <A> * LAT_COL - <B> * LON_COL + LAT_LON_SQ_SUM)

Nesse caso, você deve passar os seguintes valores do código:

<L> = center_lat^2 + center_lon^2
<A> = 2 * center_lat
<B> = 2 * center_lon

E você também deve armazenar LAT_LON_SQ_SUM = LAT_COL^2 + LON_COL^2como coluna adicional no banco de dados. Preencha-o inserindo suas entidades no banco de dados. Isso melhora um pouco o desempenho ao extrair uma grande quantidade de dados.

Sergey Metlov
fonte
-3

Experimente algo assim:

    //locations to calculate difference with 
    Location me   = new Location(""); 
    Location dest = new Location(""); 

    //set lat and long of comparison obj 
    me.setLatitude(_mLat); 
    me.setLongitude(_mLong); 

    //init to circumference of the Earth 
    float smallest = 40008000.0f; //m 

    //var to hold id of db element we want 
    Integer id = 0; 

    //step through results 
    while(_myCursor.moveToNext()){ 

        //set lat and long of destination obj 
        dest.setLatitude(_myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LATITUDE))); 
        dest.setLongitude(_myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LONGITUDE))); 

        //grab distance between me and the destination 
        float dist = me.distanceTo(dest); 

        //if this is the smallest dist so far 
        if(dist < smallest){ 
            //store it 
            smallest = dist; 

            //grab it's id 
            id = _myCursor.getInt(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_ID)); 
        } 
    } 

Depois disso, id contém o item que você deseja do banco de dados para que você possa buscá-lo:

    //now we have traversed all the data, fetch the id of the closest event to us 
    _myCursor = _myDBHelper.fetchID(id); 
    _myCursor.moveToFirst(); 

    //get lat and long of nearest location to user, used to push out to map view 
    _mLatNearest  = _myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LATITUDE)); 
    _mLongNearest = _myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LONGITUDE)); 

Espero que ajude!

Scott Helme
fonte