Búsqueda en una base de datos de datos enlazados por coordenadas para un área poligonal arbitraria

Question

Tengo una base de datos relacional donde cada entrada está marcada como un punto con coordenadas de latitud / longitud. Le doy al usuario la capacidad de marcar un polígono arbitrario en un mapa, y quiero devolver todas las entradas que estén dentro de la forma poligonal.

¿Cuál sería la mejor manera de lograr esto?

Además, podría valer la pena señalar que pequeños errores están bien (es decir, si hay una manera efectiva de convertir el polígono en un conjunto de rectángulos, entonces está bien).

Answer 1

Use extensiones espaciales, la mayoría de las bases de datos tienen esto. En MySql solo puede usarlos con tablas MyISAM que no son transaccionales.

http://dev.mysql.com/doc /refman/5.0/en/spatial-extensions.html

Answer 2

Una forma de reducir rápidamente el número de puntos a considerar es calcular el rectángulo delimitador para el polígono (es decir, solo min-x, min-y, max-x, max-y de los puntos en el polígono) , y luego seleccione los puntos dentro del rectángulo delimitador (es decir, donde x está entre min-x y max-x y lo mismo para y).

Por supuesto, no todos estos puntos están necesariamente dentro del polígono, pero ahora puede perfeccionarlo con código.

Answer 3

Un viejo truco:

Cuente el número de veces que una línea que conecta <point far away> a <point in question> cruza cualquiera de los segmentos delimitadores del polígono.

• Los números pares significan que el punto está fuera del polígono
• Los números impares significan que está dentro del polígono