How to determine which images of the earth's surface overlap with an arbitrary given image?

Question

Suppose you are given an image of the earth's surface and that it is stored in the database as a polygon defined by the latitude/longitude pairs of its corners.

Now suppose there are millions of images covering the earth's surface that are also stored similarly. What is a good strategy to find those images which intersect with your given image?

I have a working basic algorithm that is based on the "bounding radius" of the images. But it is not optimal and finds more images than ought to be returned.

I have looked at the GIS spacial functions of MySQL but all of the calculations in that appear to be done in Euclidean geometry.

Essentially, I just need a function that returns "true" or "false" depending on if two polygons (on the sphere and defined by lat/long points) intersect. Seems simple but I have not found an implementation yet. And the thought of figuring this out myself is tiring.

underdark underdark · Accepted Answer · 2010-09-16T14:47:50

Using PostGIS, you could run something like:

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"

This assumes that all image boundaries are contained in the same PostGIS table "images".

How to determine which images of the earth's surface overlap with an arbitrary given image?

2 Answers