Check if two rectangles overlap or the edges touch

Question

I get geo coords in lon and lat, like NorthWest and SouthEast lon/lat. So, when I got them I translating into metric system. So here I get my first rectangle with north_west and south_east coords, then I have bounding-rectangle in same metric system with north, south, west and east coords. And I needed check this two rect on intersection within edges touch, what I wrote:

bool filter(TilePosition const& tile_position) const noexcept override 
{
    MetricBoundingBox tile_bounds{tile_position};

    bool cond1 = (tile_bounds.north <= south_east_.lon);
    bool cond2 = (tile_bounds.south >= north_west_.lon);
    bool cond3 = (tile_bounds.west <= south_east_.lat);
    bool cond4 = (tile_bounds.east >= north_west_.lat);

    return cond1 && cond2 && cond3 && cond4;
}

And I'm not sure if I did it right? My requirement is if the borders of the second rect intersect with the borders of the first rect, then the second must be left. Else, filter.

Possible duplicate of [Determine if two rectangles overlap each other?](https://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other) — scohe001, Dec 28 '18 at 15:57
Also related (and language agnostic): [Two Rectangles intersection](https://stackoverflow.com/q/13390333/2602718) — scohe001, Dec 28 '18 at 15:58
@scohe001 I see that question but I'm needed to check is my solution is right? Realy hard to test it for me. — adziri, Dec 28 '18 at 16:01
You check if first rectangle is within bounding one, this maybe correct or not depends on requirement. Your condition will return false if two rectangles overlap partially — Slava, Dec 28 '18 at 16:01
Also, it's a nice habit to write some tests to ensure that your code is correct. It's the easiest way to determine this, besides proving analytically the correctness of your algorithm. Relatively to this problem, you can just check few edge cases and simple overlapping. — Kirill Korolev, Dec 28 '18 at 16:04
@Slava thx for a answer, can u tell me how to fix dat? My requirement is if the borders of the second rect intersect with the borders of the first rect, then the second must be left. Else, filter. — adziri, Dec 28 '18 at 16:05
@KirillKorolev yea, I'm trying but it's looks like my solution is wrong. But I'm not sure. — adziri, Dec 28 '18 at 16:08
I'm quite sure you did it wrong, unless you have intentionally reversed the meanings of latitude and longitude. — Ben Voigt, Dec 28 '18 at 16:11
@Slava I understand but I had another coords system and I actually not sure if I compare them right, is I rightly introduce x, y with south, north, east, west? — adziri, Dec 28 '18 at 16:13
@Azazel-San: You are comparing east-west of one rectangle with north-south of the other. This makes no sense. — Ben Voigt, Dec 28 '18 at 16:15
@scohe001: Not quite a duplicate, because this question is in cylindrical coordinates (and not actually rectangles at all...) — Ben Voigt, Dec 28 '18 at 16:18

score 1 · Answer 1 · answered Dec 28 '18 at 16:15

Your solution is not correct.

Besides confusing the meaning of latitude and longitude, you have a fundamental problem that algorithms designed for cartesian coordinate space do not work in cylindrical coordinates, because longitude is periodic. Things may look ok for rectangles near the meridian, but when you start testing near the wrap point (+/- 180 degrees longitude) this method will fail.

One simple fix is to break each rectangle that crosses the wrap point into two that do not cross.

Check if two rectangles overlap or the edges touch

1 Answers1