Detect if rectangle intersects with other rectangle in geographic coordinate

Question

I have two rectangles and want to detect if rectangle intersects with other rectangle in geographic coordinate. My actual code working only with positive geographic coordinate values

if (rect1.MaxLongitude < rect2.MinLongitude || rect2.MaxLongitude < rect1.MinLongitude || rect1.MaxLatitude < rect2.MinLatitude || rect2.MaxLatitude < rect1.MinLatitude)
{
    return false;
}
else
{
    return true;
}

How can i achieve detecting in geographic coordinate with negative and positive values (even in one coordinate)?

.NET reference source might help out? [System.Drawing.RectangleF.IntersectsWith(RectangleF rect)](https://referencesource.microsoft.com/System.Drawing/R/74d4076547fe3661.html) — Fixation, Jan 21 '20 at 15:51
You could maybe just add a number greater than 180 to each value? — stuartd, Jan 21 '20 at 15:54
Doesn't matter if long/lat is used or just X/Y. The code is still the same. Thus closing as dup. — jgauffin, Jan 21 '20 at 20:47

amalgamate · Answer 1 · 2020-01-21T20:40:08.083

Do the rectangles freely rotate, or are lines strictly horizontal and vertical? The former is a slightly higher level of difficulty. The latter is implied by your code.

Assuming the latter, I would expect your code to work even for negative numbers...

                0
                |   
 LON(-)/LAT(+)  |  LON(+)/LAT(+) 
                |   
 ---------------+-----------------0
                |   
 LON(-)/LAT(-)  |  LON(+)/LAT(-) 
                |

Except that the order is important. If any of these 2 comparisons are true then your algorithm breaks under certain conditions:

rect1.minLon > rect2.minLon
rect1.maxLon > rect2.maxLon

Lets take some sample rectangles through your algorithm:

Two Positive rectangles that intersect: rect1{(1,1)-(4,4)} rect2 {(2,2)-(6,6)}

Gives us the return false because we just need one true value

rect1.MaxLongitude(4) < rect2.MinLongitude(2) false
rect2.MaxLongitude(6) < rect1.MinLongitude(1) false
rect1.MaxLatitude(4) < rect2.MinLatitude(2)   **true**
rect2.MaxLatitude(6) < rect1.MinLatitude(1)   false

What happens if they do not intersect but rect2 is lower on the map than rect1: rect1{(10,10)-(40,40)} rectangle {(2,2)-(6-6)}

This gives us a return of false too, but the triangles do not intersect:

rect1.MaxLongitude(40) < rect2.MinLongitude(2) false
rect2.MaxLongitude(6) < rect1.MinLongitude(10) **true**
rect1.MaxLatitude(40) < rect2.MinLatitude(2)   false
rect2.MaxLatitude(6) < rect1.MinLatitude(20)   **true**

This is an edge case problem for your algorithm where: (rect1.minLon > rect2.minLon && rect1.minLat > rect2.minLat). One way to ensure your algorithm works in these two cases is to be certain you are comparing where rect1 is always lower and to the left(west) of rect2. There is still a problem however, because you are still not allowing for the following: (rect1.minLon > rect2.minLon && rect1.minLat < rect2.minLat)|| (rect1.minLon < rect2.minLon && rect1.minLat < rect2.minLat). It is not the negative numbers that are the problem. It is that you are not anticipating all cases where the rectangles do not intersect.

I have run out of steam and will not actually solve the problem for you, however you could deal with the problem by dividing the problem into the 4 scenarios:

scenario 1 : (rect1.minLon > rect2.minLon && rect1.maxLon > rect2.maxLon) 
scenario 2 : (rect1.minLon < rect2.minLon && rect1.maxLon < rect2.maxLon) 
scenario 3 : (rect1.minLon < rect2.minLon && rect1.maxLon > rect2.maxLon)
scenario 4 : (rect1.minLon > rect2.minLon && rect1.maxLon< rect2.maxLon)

A separate method for each, where each would have a solution as simple as your current algorithm but they would actually not be the same. Your algorithm solves scenario 2 I think. Probably should have made that the first one.

Detect if rectangle intersects with other rectangle in geographic coordinate

1 Answers1