Pesquisando uma base de dados de dados de coordenadas ligado para uma área poligonal arbitrária

Question

Eu tenho um banco de dados relacional, onde cada entrada é marcado como um ponto com a latitude / longitude coordenadas. I dar ao usuário a capacidade de marcar um polígono arbitrário em um mapa, e querem voltar todas as entradas que estão dentro da forma poligonal.

Qual seria a melhor maneira de conseguir isso?

Além disso, pode valer a pena salientar que pequenos erros são ok (ie., Se há uma maneira eficaz para transformar o polígono em um conjunto de retângulos, então isso é bom).

Answer 1

Utilize extensões espaciais, a maioria dos bancos de dados têm isso. No MySQL você só pode usá-los com tabelas MyISAM que não são transacional.

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

Answer 2

Uma forma de rapidamente reduzir o número de pontos a considerar é calcular o rectângulo delimitadora para o polígono (ou seja, apenas MIN-X, min-y, max-X, max-Y dos pontos no polígono) , e então seleccionar os pontos dentro do rectângulo envolvente (isto é, onde x é entre os valores mínimo e máximo-x-x e y para o mesmo).

É claro que nem todos esses pontos são necessariamente dentro do polígono, mas agora você pode aprimorar isso com o código.

Answer 3

Um corte de idade:

Contar o número de vezes que uma linha que liga a <point far away> <point in question> atravessa qualquer um dos segmentos delimitadora do polígono.

• números pares significa que o ponto está fora do polígono
• Números ímpares significa que é dentro do polígono