Ricerca in un database di dati associati a coordinate per un'area poligonale arbitraria

Question

Ho un database relazionale in cui ogni voce è contrassegnata come un punto con coordinate di latitudine / longitudine. Offro all'utente la possibilità di contrassegnare un poligono arbitrario su una mappa e desidero restituire tutte le voci all'interno della forma poligonale.

Quale sarebbe il modo migliore per raggiungere questo obiettivo?

Inoltre, potrebbe valere la pena sottolineare che piccoli errori vanno bene (es. se esiste un modo efficace per trasformare il poligono in un insieme di rettangoli, va bene).

Answer 1

Usa estensioni spaziali, la maggior parte dei database ha questo. In MySql puoi usarli solo con tabelle MyISAM che non sono transazionali.

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

Answer 2

Un modo per ridurre rapidamente il numero di punti da considerare è calcolare il rettangolo di delimitazione per il poligono (ovvero solo min-x, min-y, max-x, max-y dei punti nel poligono) , quindi seleziona per i punti all'interno del rettangolo di delimitazione (ovvero dove x è compreso tra min-x e max-x e lo stesso per y).

Ovviamente non tutti questi punti sono necessariamente all'interno del poligono, ma ora puoi perfezionarlo con il codice.

Answer 3

Un vecchio trucco:

Conta il numero di volte in cui una linea che collega <point far away> a <point in question> attraversa uno qualsiasi dei segmenti del poligono.

• I numeri pari indicano che il punto si trova all'esterno del poligono
• I numeri dispari indicano che si trova all'interno del poligono