Как определить, какие изображения земной поверхности перекрываются с произвольным заданным изображением?

Question

Предположим, вам дано изображение земной поверхности, и оно сохраняется в базе данных в виде многоугольника, определяемого парами широты / долготы ее углов.

Теперь предположим, что миллионы изображений, покрывающих поверхность Земли, также хранятся аналогичным образом. Какова хорошая стратегия, чтобы найти те изображения, которые пересекаются с вашим заданным изображением?

У меня есть работающий базовый алгоритм, основанный на "ограничивающем радиусе" изображений. Но это не является оптимальным и находит больше изображений, чем должно быть возвращено.

Я рассмотрел пространственные функции ГИС в MySQL, но все вычисления в этом, похоже, сделаны в евклидовой геометрии.

По сути, мне просто нужна функция, которая возвращает «истина» или «ложь» в зависимости от того, пересекаются ли два многоугольника (на сфере и определяются точками широты и долготы). Кажется простым, но я еще не нашел реализацию. И мысль об этом сама утомляет.

Answer 1

Используя PostGIS, вы можете запустить что-то вроде:

SELECT b.* 
FROM images AS a
 JOIN images AS b
 ON ST_Intersects(a.the_geom,b.the_geom)
WHERE a.name = "The image you are interested in"

Предполагается, что все границы изображений содержатся в одной и той же таблице PostGIS "images".

Answer 2

Я лично использую PostGIS и GEOS (через geodjango ) для решения этой проблемы.