Consigue polígonos cerca de un lat, mucho en mysql

Question

¿Alguien sabe de una forma de buscar todos los polígonos en un DB MySQL a una distancia dada de 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 una caja delimitadora dibujada 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 utilizar los índices espaciales, debe desnormalizar su tabla para que cada vértice de polígono se almacene en su propio registro.

Luego crea el SPATIAL INDEX En el campo que contiene las coordenadas de los vértices y simplemente emite esta consulta:

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

Las cosas serán mucho más fáciles si almacenas 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, es una cuestión de cómo organizar sus datos para que haga uso de la localidad espacial inherente a su problema.

La primera idea que aparece en mi cabeza sería usar una cuadrícula, asignar cada punto a un cuadrado y verificar seleccionar el cuadrado que el punto está adentro y los que lo rodean. Si estamos hablando de cuadrículas infinitas, use un valor hash del cuadrado, esto le daría más puntos de los necesarios (donde tiene colisiones), pero aún así reducirá la cantidad por un grupo. Por supuesto, esto no es aplicable de inmediato a los polígonos, es solo una lluvia de ideas. Un posible enfoque que podría producir demasiadas colisiones sería o todos los valores de hash juntos y seleccionar todas las entradas donde los hashes andados con ese valor no son cero (no estoy seguro si esto es posible en mysql), es posible que desee usar un gran Sin embargo, cantidad de bits.

El problema con este enfoque es, suponiendo que estamos hablando de coordenadas esféricas (Lat, Long Generalmente lo hace) son las singularidades, a medida que la cuadrícula se vuelve más estrecha a medida que aborda los polos. El enfoque fácil de esto es ... No pongas ningún punto cerca de los polacos ... :)

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 los polígonos complejos). Luego puede comparar el cuadro delimitador para cada polígono con uno alrededor del punto en el tamaño deseado. Seleccione todos los polígonos que tienen cajas limitantes de intersección.