How do we find the intersection of the interiors of n squares that have sides parallel to the x and y axes given their centers and side lengths?

The input is the number of squares followed by that many descriptions of squares. The description of each square is the x and y coordinates of its center and its side length. For example:

3
5 11 10 
7 9 10 
10 6 8

describes three squares, starting with one centered at (5, 11) with side length 10.

CodePudding user response：

An algorithm to find the intersection of the interiors of squares (with sides parallel to the x and y axes) given by their centers and lengths is:

• Convert the center (the point (x, y)) and length (l) of the first square to the x coordinates of the left edge (x−l/2) and the right edge (x l/2) and the y coordinates of the bottom edge (y−l/2), and the top edge (y l/2). Keep those as the left, right, bottom, and top.
• For each following square:
  • Convert its center and length to coordinates as above.
  • Figure out which x coordinate is greater, the old left or the new left edge, and keep that as the new left.
  • Figure out which x coordinate is lesser, the old right or the new right edge, and keep that as the new right.
  • Figure out which y coordinate is greater, the old bottom or the new bottom edge, and keep that as the new bottom.
  • Figure out which y coordinate is lesser, the old top or the new top edge, and keep that as the new top.

After processing all squares, left, right, bottom, and top are the coordinates of the rectangle bounding the area that is inside all of the squares. (If right < left or top < bottom, the intersection is empty. Otherwise, if right = left or top = bottom, the intersection is a line [if only one is true] or a point [if both are true].)

CodePudding user response：

Here is a simple function to calculate the intersection between two rectangles. A square is a rectangle, so it can be used for squares. I assume that the rectangles height and width are parallel to the y and x axis.

struct point { double x, y; };
struct rectangle { struct point a, b; };
double max(double a, double b) { return a>b ? a : b; }
double min(double a, double b) { return a<b ? a : b; }

// Calculate the intersection of r1 and r2 and store the result in output
// Assumes that a.x < b.x and a.y < b.y for r1 and r2
// Returns NULL if there is no intersection 
// Will always modify output. Do do NOT read output if this function returns NULL
struct rectangle *intersection(
    struct rectangle *output, 
    const struct rectangle *r1, 
    const struct rectangle *r2) 
{
    
    output->a.x = max(r1->a.x, r2->a.x);
    output->b.x = min(r1->b.x, r2->b.x);
    if(output->a.x > output->b.x) return NULL;

    output->a.y = max(r1->a.y, r2->a.y);
    output->b.y = min(r1->b.y, r2->b.y);
    if(output->a.y > output->b.y) return NULL;

    return output;
}