Calcular la distancia entre códigos postales ... y usuarios.
https://stackoverflow.com/questions/3983325
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Esto es más de una pregunta de seguridad de algo que necesita con urgencia, por lo que no me paso todo el día en él chicos.
I construyó un sitio de citas (tiempo pasado) en el año 2000 más o menos, y uno de los desafíos que estaba calculando la distancia entre los usuarios para que pudiéramos presentar sus "coincidencias" dentro de un radio de X millas. Para el estado sólo el problema, teniendo en cuenta el siguiente esquema de base de datos (más o menos):
TABLA DE USUARIO UserId Nombre de usuario ZipCode
TABLA CÓDIGO POSTAL Código postal Latitud Longitud
Con el usuario y ZIPCODE ser unidos en USER.ZipCode = ZIPCODE.ZipCode.
¿Qué enfoque le tomaría para responder a la siguiente pregunta: ¿Qué otros usuarios viven en los códigos postales que están dentro de X miles de Código postal de un usuario determinado
. Se utilizó la href="http://www.census.gov/geo/www/gazetteer/places2k.html" rel="nofollow noreferrer"> datos del censo 2000 También se utiliza la Haversine Fórmula para calcular distancias entre dos puntos cualesquiera de una esfera. .. matemáticas bastante simple en realidad. La cuestión, al menos para nosotros, siendo los estudiantes universitarios de 19 años que estuvimos, en realidad se convirtió en la forma de calcular de manera eficiente y / registrar distancias de todos los miembros a todos los demás miembros. Uno de los enfoques (la que usamos) sería para importar todos los datos y calcular la distancia desde cada código postal a todos los demás código postal. Entonces será almacenar e indexar los resultados. Algo así como: El problema, por supuesto, es que la tabla ZipDistance va a tener una gran cantidad de filas en ella. No es del todo inviable, pero es muy grande. También se requiere pre-obra completa en todo el conjunto de datos, que tampoco es difícil de manejar, pero no necesariamente deseable. De todos modos, me preguntaba qué enfoque Algunos de ustedes gurús podría tomar en algo como esto. Además, creo que este es un problema común para hacer frente a los programadores tienen de vez en cuando, sobre todo si se tiene en cuenta los problemas que son igual de algoritmos similares. Estoy interesado en una solución completa que incluye al menos pistas sobre todas las piezas para hacer esto realmente terminan rápidamente de manera eficiente. Gracias! SELECT User.UserId
FROM ZipCode AS MyZipCode
INNER JOIN ZipDistance ON MyZipCode.ZipCode = ZipDistance.MyZipCode
INNER JOIN ZipCode AS TheirZipCode ON ZipDistance.OtherZipCode = TheirZipCode.ZipCode
INNER JOIN User AS User ON TheirZipCode.ZipCode = User.ZipCode
WHERE ( MyZipCode.ZipCode = 75044 )
AND ( ZipDistance.Distance < 50 )
Solución
Bueno, para empezar, que realmente no necesita utilizar la fórmula Haversine aquí. Para grandes distancias, donde una fórmula menos preciso produce un error grande, los usuarios no les importa si el partido es más o menos un par de millas, y para distancias más cortas, el error es muy pequeño. Hay más fácil (para calcular) las fórmulas que figuran en el distancia geográfica artículo de Wikipedia.
Dado que los códigos postales no son nada como espaciados uniformemente, cualquier proceso que las particiones de manera uniforme va a sufrir poderosamente en las zonas donde son muy próximas (costa este, cerca de la CC es un ejemplo bueno). Si quieres una comparación visual, echa un vistazo a http://benfry.com/zipdecode y comparar el prefijo de código postal con 89 07.
Una forma mucho mejor para hacer frente a la indexación de este espacio es el uso de una estructura de datos como un Quadtree árbol R . Esta estructura le permite hacer búsquedas espaciales y distancia sobre datos que no se espacian uniformemente.
Esto es lo que un Quadtree se ve así:
Para realizar búsquedas sobre ella, que no se profundiza a través de cada célula más grande utilizando el índice de células más pequeñas que están dentro de ella. Wikipedia lo explica más a fondo.
Por supuesto, ya que esto es una cosa bastante común de hacerlo, otra persona lo ha hecho la parte más difícil para usted. Ya que no han especificado qué base de datos que está utilizando, la extensión PostgreSQL PostGIS servirá como una ejemplo. PostGIS incluye la capacidad de hacer índices espaciales de árbol R, que le permiten hacer consultas espaciales eficiente.
Una vez que haya importado sus datos y construyó el índice espacial, las consultas a distancia es una consulta como:
SELECT zip
FROM zipcode
WHERE
geom && expand(transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661), 16093)
AND
distance(
transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661),
geom) < 16093
Voy a dejar de trabajar por el resto del tutorial usted mismo.
Aquí están algunas otras referencias para ayudarle a empezar.
Otros consejos
Me simplemente crear una mesa zip_code_distances y pre-Calcular las distancias entre todos los 42K códigos postales en los EE.UU. que se encuentran dentro de un radio de 20-25 millas el uno del otro.
create table zip_code_distances
(
from_zip_code mediumint not null,
to_zip_code mediumint not null,
distance decimal(6,2) default 0.0,
primary key (from_zip_code, to_zip_code),
key (to_zip_code)
)
engine=innodb;
Sólo incluyendo códigos postales dentro de un radio de 20-25 millas el uno del otro reduce el número de filas que necesita para almacenar en la tabla de distancias desde su máximo de 1,7 mil millones (42K ^ 2) - 42K a una mucho más manejable 4 millones o de modo.
He descargado un archivo de datos código postal desde la web que contenía las longitudes y latitudes de todos los códigos postales oficiales de Estados Unidos en formato csv:
"00601","Adjuntas","Adjuntas","Puerto Rico","PR","787","Atlantic", 18.166, -66.7236
"00602","Aguada","Aguada","Puerto Rico","PR","787","Atlantic", 18.383, -67.1866
...
"91210","Glendale","Los Angeles","California","CA","818","Pacific", 34.1419, -118.261
"91214","La Crescenta","Los Angeles","California","CA","818","Pacific", 34.2325, -118.246
"91221","Glendale","Los Angeles","California","CA","818","Pacific", 34.1653, -118.289
...
Me escribió un programa rápido y sucio C # para leer el archivo y calcular las distancias entre cada código postal códigos postales, pero solamente de salida que caen dentro de un radio de 25 millas:
sw = new StreamWriter(path);
foreach (ZipCode fromZip in zips){
foreach (ZipCode toZip in zips)
{
if (toZip.ZipArea == fromZip.ZipArea) continue;
double dist = ZipCode.GetDistance(fromZip, toZip);
if (dist > 25) continue;
string s = string.Format("{0}|{1}|{2}", fromZip.ZipArea, toZip.ZipArea, dist);
sw.WriteLine(s);
}
}
Las miradas resultantes de archivo de salida de la siguiente manera:
from_zip_code|to_zip_code|distance
...
00601|00606|16.7042215574185
00601|00611|9.70353520976393
00601|00612|21.0815707704904
00601|00613|21.1780461311929
00601|00614|20.101431539283
...
91210|90001|11.6815708119899
91210|90002|13.3915723402714
91210|90003|12.371251171873
91210|90004|5.26634939906721
91210|90005|6.56649623829871
...
Me entonces simplemente cargar estos datos de distancia en mi mesa zip_code_distances utilizando LOAD DATA INFILE y luego utilizarlo para limitar el espacio de búsqueda de mi solicitud.
Por ejemplo, si tiene un usuario cuyo código postal es 91210 y que quiere encontrar personas que están dentro de un radio de 10 millas de ellos, entonces ahora se puede simplemente hacer lo siguiente:
select
p.*
from
people p
inner join
(
select
to_zip_code
from
zip_code_distances
where
from_zip_code = 91210 and distance <= 10
) search
on p.zip_code = search.to_zip_code
where
p.gender = 'F'....
Espero que esto ayude
EDIT:. Extendida radio de 100 millas que aumentó el número de código postal distancias a 32,5 millones de filas
control de funcionamiento rápido para código postal 91210 tiempo de ejecución 0.009 segundos.
select count(*) from zip_code_distances
count(*)
========
32589820
select
to_zip_code
from
zip_code_distances
where
from_zip_code = 91210 and distance <= 10;
0:00:00.009: Query OK
Se podría acortar el cálculo con sólo asumiendo una caja en lugar de un radio circular. A continuación, en la búsqueda sólo tiene que calcular la parte inferior / límite superior de latitud / longitud de un punto + "radio" dado, y todo el tiempo que tiene un índice en las columnas lat / lon que podría tirar de todos los registros que se encuentran dentro del cuadro con bastante facilidad .
Se podría dividir el espacio en regiones de aproximadamente el mismo tamaño - por ejemplo, se aproxima a la Tierra como una bola hueca o icosaedro. Las regiones podrían incluso se superponen un poco, si eso es más fácil (por ejemplo hacerlos circular). Record qué región (s) cada código postal está en. A continuación, puede precalcular la distancia máxima posible entre cada par región, que tiene la misma O (n ^ 2) problema, ya que el cálculo de todos los pares de código postal , pero para más pequeño n .
Ahora, para cualquier código postal dado, se puede obtener una lista de las regiones que son definitivamente dentro de su rango dado, y una lista de las regiones que cruzan la frontera. En el primer caso, sólo tienes que tomar todos los códigos postales. Para este último, profundizar en cada región fronteriza y calcular contra códigos postales individuales.
Es ciertamente más compleja matemáticamente, y en particular el número de regiones tendría que ser elegido para un buen equilibrio entre el tamaño de la tabla contra el tiempo para calcular sobre la marcha, pero se reduce el tamaño de la tabla precalculada por un buen margen.
Yo usaría latitud y longitud. Por ejemplo, si usted tiene una latitud de 45 y una longitud de 45 y se le pidió que encontrar coincidencias dentro de 50 millas, entonces usted podría hacerlo moviendo 50/69 THS hasta en latitud y 50/69 THS en la latitud (1 grado latitud ~ 69 millas). Seleccionar los códigos postales con latitudes en este rango. Las longitudes son un poco diferentes, ya que se hacen más pequeños a medida que nos acercamos a los polos.
Pero a los 45 grados, 1 ~ 49 millas de longitud, por lo que podría pasar 50 / 49ths que quedan en latitud y 50 / 49ths derecha en latitud, y seleccione todos los códigos postales del conjunto latitud con esta longitud. Esto le da todos los códigos postales dentro de un cuadrado con una longitud de cien millas. Si quería ser muy precisa, se puede entonces utilizar la bruja fórmula Haversine usted ha mencionado a eliminar a las cremalleras en las esquinas de la caja, para darle una esfera.
No todos los pares posibles de los códigos postales se va a utilizar. Me gustaría construir zipdistance como una tabla 'caché'. Para cada solicitud calcular la distancia para ese par y lo guarda en la memoria caché. Cuando una solicitud de un par distancia viene, primer vistazo en la memoria caché, a continuación, calcular si no está disponible.
No sé las complejidades de los cálculos de distancia, por lo que también verificará si la computación sobre la marcha es más barato que mirando hacia arriba (teniendo también en cuenta la frecuencia con que tiene que compute).
Sé que este post es demasiado viejo, pero haciendo un poco de investigación para un cliente que he encontrado algunas funciones de utilidad de la API de Google Maps y es tan fácil de implementar, sólo tiene que pasar a la URL del origen y destino postal códigos, y se calcula la distancia incluso con el tráfico, se puede utilizar con cualquier idioma:
origins = 90210
destinations = 93030
mode = driving
siguiendo el enlace se puede ver que devuelve un JSON. Recuerde que necesita una clave de API para utilizar esto en su propio alojamiento.
tengo el problema de funcionamiento grande, y bastante acostumbré respuesta mucho de todos. Estaba pensando en esto en términos de la solución de edad en lugar de sólo "empezar de nuevo". Babtek recibe el visto bueno para afirmar en términos más simples en.
Me voy a saltar el código porque voy a ofrecer referencias para derivar las fórmulas necesarias, y no hay demasiado que después limpiamente aquí.
1) Considere Point A en una esfera, representada por la latitud y la longitud. Figura cabo bordes de un cuadro de Norte, Sur, Este y Oeste 2X millas de diámetro con el punto A en el centro .
2) Seleccionar todo punto dentro de la caja de la tabla de código postal. Esto incluye un simple cláusula WHERE con dos entre los estados que limitan por Lat y Long.
3) Use la fórmula haversine para determinar la distancia esférica entre el punto A y cada punto B devuelto en el paso 2.
4) Eliminar todos los puntos B donde la distancia A -.> B> X
5) Seleccionar usuarios donde ZipCode está en el conjunto restante de los puntos B.
Esto es bastante rápido para> 100 millas. resultado más largo fue de ~ 0,014 segundos para calcular el partido, y trivial para ejecutar la instrucción de selección.
Además, como nota al margen, fue necesario aplicar las matemáticas en un par de funciones y llamarlos en SQL. Una vez que llegué más allá de una cierta distancia el número correspondiente de códigos postales era demasiado grande para pasar de nuevo a SQL y su uso como una declaración en, así que tuve que utilizar una tabla temporal y unirse a los códigos postales resultantes de usuario en la columna de código postal.
Sospecho que el uso de una mesa ZipDistance no proporcionará una ganancia de rendimiento a largo plazo. El número de filas sólo se pone muy grande. Si se calcula la distancia de cada postal que a cualquier otro código postal (con el tiempo), entonces el número de filas resultante de 40.000 códigos postal sería ~ 1.6B. Whoah!
Como alternativa, estoy interesado en el uso de SQL incorporado en el tipo de geografía para ver si eso hará que esto, pero buenos tipos int / flotador de edad más fáciles bien servido para esta muestra.
Así que ... la lista final de los recursos en línea que he usado, para su fácil referencia:
1) diferencia máxima, latitud y longitud .
2) El Haversine Fórmula .
3) discusión largo, pero completa de todo el proceso , que I encontrado de googlear cosas en sus respuestas.
