Obtener polígonos cercanos a un lat, largo en MySQL

Question

¿Alguien sabe de una manera de obtener todos los polígonos en una base de datos MySQL dentro de una distancia dada desde un punto? La distancia real no es tan importante ya que se calcula para cada polígono encontrado más tarde, pero sería una gran optimización hacer ese cálculo para los polígonos que están "cerca".

He visto el MBR y contiene funciones, pero el problema es que algunos de los polígonos no están contenidos dentro de un cuadro delimitador dibujado alrededor del punto, ya que son muy grandes, pero algunos de sus vértices aún están cerca.

¿Alguna sugerencia?

Answer 1

Una versión lenta (sin índices espaciales):

SELECT * 
FROM mytable 
WHERE MBRIntersects(mypolygon, LineString(Point(@X - @distance, @Y - @distance), Point(@X + @distance, @Y + @distance)) 

para hacer uso de los índices espaciales, es necesario eliminar la normalización de la mesa para que cada vértice del polígono se almacena en su propio registro.

continuación, crear el SPATIAL INDEX en el campo que contiene las coordenadas de los vértices y simplemente emitir esta consulta:

SELECT DISTINCT polygon_id 
FROM vertices 
WHERE MBRContains(vertex, LineString(Point(@X - @distance, @Y - @distance), Point(@X + @distance, @Y + @distance)) 

Las cosas van a ser mucho más fácil si almacena UTM coordenadas en su base de datos en lugar de latitud y longitud.

Answer 2

No creo que haya una sola respuesta a esto. En general, se trata de cómo organizar sus datos para que hagan uso de la localidad espacial inherente a su problema.

La primera idea que me viene a la cabeza es utilizar una cuadrícula, asignar cada punto a un cuadrado y marcar el cuadrado en el que se encuentra el punto y los que lo rodean. Si estamos hablando de cuadrículas infinitas, entonces use un valor de hash del cuadrado, esto le daría más puntos de los necesarios (donde tenga colisiones), pero aún reducirá la cantidad por un grupo. Por supuesto, esto no es inmediatamente aplicable a los polígonos, es solo una lluvia de ideas. Un posible enfoque que podría producir demasiadas colisiones sería para O todos los valores hash juntos y seleccionar todas las entradas donde el valor hash ANDed con ese valor es distinto de cero (no estoy seguro de si esto es posible en MySQL), es posible que desee utilizar un gran cantidad de bits sin embargo.

El problema con este enfoque es, asumiendo que estamos hablando de coordenadas esféricas (lat, long generalmente lo hace) son las singularidades, a medida que los 'cuadrados' de la cuadrícula se hacen más estrechos a medida que nos acercamos a los polos. El enfoque fácil para esto es ... no coloque ningún punto cerca de los polos ... :)

Answer 3

Cree un cuadro delimitador para todos los polígonos y (opcionalmente, almacenar estos resultados en la base de datos hará que esto sea mucho más rápido para polígonos complejos). A continuación, puede comparar el cuadro delimitador de cada polígono con el que rodea el punto con el tamaño deseado. Seleccione todos los polígonos que tienen recuadros delimitadores que se cruzan.