If the input rectangles are normalized, i.e. you already know that x1 < x2, y1 < y2 (and the same for the second rectangle), then all you need to do is calculate int x5 = max(x1, x3); int y5 = max(y1, y3); int x6 = min(x2, x4); int y6 = min(y2, y4); and it will … Read more
Despite the title to your question, I think you’re actually looking for the minimum dissection into rectangles of a rectilinear polygon. (Jason’s links are about minimum covers by rectangles, which is quite a different problem.) David Eppstein discusses this problem in section 3 of his 2010 survey article Graph-Theoretic Solutions to Computational Geometry Problems, and … Read more
Efficient Quadtrees All right, I’ll take a shot at this. First a teaser to show the results of what I’ll propose involving 20,000 agents (just something I whipped up real quick for this specific question): The GIF has extremely reduced frame rate and significantly lower res to fit the 2 MB maximum for this site. … Read more
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left && RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) or, using Cartesian coordinates (With X1 being left coord, X2 being right coord, increasing from left to right and Y1 being Top coord, and Y2 being Bottom coord, increasing from bottom to top — if this is not … Read more