Working algorithm for testing two rectangles for overlapping in Earth GPS coordinates plain

Question

Here is a seemingly simple, but actually quite tricky problem:

I am trying to figure out the correct algorithm to test intersection/overlapping of two rectangles, which are plotted on the Earth's surface (have GPS coordinates). The rectangles represent geographical locations' bounds (i.e. Nort-most, South-most, East-most, West-most points). Some ilustration of the right algorithm on PHP, c++ or whatever comp. language will be greatly welcome.

Input data (refer to the diagram):

(1) GPS coords of two diagonal edges

• RECTANGLE I: D(D1,D2) and B(B1,B2)
• RECTANGLE II: I(I1,I2) and G(G1,G2)

This is sufficient to resolve the GPS coords of the other two edges: A(B1,D2) and C(D1,B2) . Same aplied for the other rectangle

(2) GPS coords of the diagonals intersection K(K1,K2) and E(E1,E2). This is sufficient to rule out which constitutes the rectangle (e.g. Greenland bounds OR everything BUT Greelnand )

(3) The rectangles are ploted out of bounds of geographical locations, so some 'perpendicularity' to the Equator/0-merridian is inherent

Issues:

(1) The test of edges of RECTANGE I against RECTANGLE II and vice-versa fails (as the rectangles may be situated cross-like (see the diagram)

(2) The switch from positive lon (+180) to negative lon (-180) of the Eartch GPS coord system kills all properly working in a rectangular coordinates plain algorithms (the issue here can be understood easily by viewing the same example ilustrated over the map)

(3) The location/size of the rectangles can be arbitrary, so assumptions for location/size (e.g. rectangle ploted over Europe) also kill some of the tested algorithms

Any ideas or suggestions how to properly do the test for intersection ?

Answer 1

I'd start with this north-most, south-most, west-most and east-most coordinates, since they will be eaiser to handle and seem to be the source of these “rectangles” in any case.

Take one “rectangle” defined by (n₁, s₁, w₁, e₁), and the other by (n₂, s₂, w₂, e₂). I assume coordinates to increase northwards and eastwards.

If s₂ > n₁ or s₁ > n₂, then the two rectangles are in different latitudes, and can not intersect. Otherwise they will share some latitude and need a second look. If w₂ < e₁ and w₁ < e₂, then the rectangles do overlap.

But so far I have avoided the problem of wrap-around. You might have to adjust some longitudes by some multiple of 360°. To deal with that, first make sure that w_i < e_i < w_i+360°, i.e. the “rectangle” does not go in the wrong direction or around the earth more than once. Also normalize “rectangles” by ensuring that 0 ≤ w_i < 360°. This still does not ensure that you will correctly detect an overlap. But you can test as above, then move one rectangle east by 360° and repeat the test, then move the first back an dinstead the other east and do a third test. All of this is only required if they have a non-empty range of latitudes in common.