Note: If both rectangles share a common border from outside, then that is intersection.

Imagine x values on the screen as column lines that become more positive from left to right. Imagine y values on the screen as row lines that become more positive from top to bottom. The intersection of line x=0 and line y=0 has the coordinate, (0,0).

This is a teaching document. So in an actual interview, the candidate should summarize all what is given below.

17.1 Give an algorithm to solve this problem when rectangles are defined by their width, height, and (x, y) coordinates of their top-left corners.

There are two rectangles concerned. So there are two sets of values for {x, y, width, height}.

Do not forget that (x,y) are the coordinates for the left-top corner of either rectangles.

To solve the problem, use the logical principle of contradiction. In this case, the principle is: Two rectangles do not intersect if one is completely to the left or completely to the right, or completely to the top, or completely to the bottom of the other. If none of these four conditions are true, then they must intersect.

Completely to the left, does not only mean that the two rectangles are at the same horizontal level. The left one may be higher up or lower down, but still to the left.
Completely to the right, does not only mean that the two rectangles are at the same horizontal level. The right one may be higher up or lower down, but still to the right.
Completely to the top, does not only mean that the two rectangles are in the same column space. The top one may be leftwards or rightwards, but still high up.
Completely to the bottom, does not only mean that the two rectangles are in the same column space. The bottom one may be leftwards or rightwards, but still low down.

The Conditions

Let rect1 and rect2 be the two rectangles. Let rect2 be fixed (stationary) and rect1 can be to the left or right or top or bottom.

The condition for no intersection here, true, is:

    rect1.x + rect1.width < rect2.x

The condition for no intersection here, true, is:

    rect1.x > rect2.x + rect2.width

The condition for no intersection here, true, is:

    rect1.y + rect1.height < rect2.y

The condition for no intersection here, true, is:

    rect1.y > rect2.y + rect2.height

Do not forget that y values on the screen as row lines, become more positive from top to bottom.

The above four conditions are combined with OR operators and just NOTted (complemented) and put in the return statement of the program, as the principal solution; see below.

The Program

The combined conditions in the return statement is NOTted (complemented), for the contradiction principle. The program is (read the code and comments):

package main

import "fmt"

// Rectangle struct defines a rectangle
type Rectangle struct {
	x, y, width, height int
}

// NewRectangle is a constructor for the Rectangle struct
func NewRectangle(x, y, width, height int) Rectangle {
	return Rectangle{x: x, y: y, width: width, height: height}
}

// CheckIntersection function checks if two rectangles intersect
func CheckIntersection(rect1, rect2 Rectangle) bool {
	return !(rect1.x+rect1.width <= rect2.x ||
		rect1.x >= rect2.x+rect2.width ||
		rect1.y+rect1.height <= rect2.y ||
		rect1.y >= rect2.y+rect2.height)
}

func main() {
	// Example 1: Intersecting Rectangles
	r1 := NewRectangle(0, 0, 10, 10)
	r2 := NewRectangle(5, 5, 10, 10)
	fmt.Println("Example 1 (Intersection):", func() string {
		if CheckIntersection(r1, r2) {
			return "Yes"
		}
		return "No"
	}())

	// Example 2: Non-Intersecting Rectangles
	r3 := NewRectangle(0, 0, 5, 5)
	r4 := NewRectangle(10, 10, 5, 5)
	fmt.Println("Example 2 (Non-intersection):", func() string {
		if CheckIntersection(r3, r4) {
			return "Yes"
		}
		return "No"
	}())
}

The output is:

    Example 1 (Intersection): Yes
    Example 2 (Non-intersection): No

17.2 Give another algorithm where rectangles are defined by their width, height, and (x, y) coordinates of their centers.

There are two rectangles concerned. So there are two sets of values for {x, y, width, height}.

Do not forget that (x,y) are the coordinates for the x/y center point, of either rectangles, for this part of the problem.

To determine if two rectangles intersect using their centers, widths, and heights, the distance between their centers must be less than the sum of their half-dimensions along both axes.

To solve the problem, calculate the absolute distance in x and y between both centers and compare that to half of the sum of their widths and heights, respectively. To appreciate this solution, imagine that the two rectangles are almost touching at their borders.

Before presenting the program below, know that in mathematics:

    width1 / 2 + width2 / 2   =   (width1 + width2) / 2

also

    height1 / 2 + height2 / 2   =   (height1 + height2) / 2

As the principal solution, the condition (logical AND of two sub-conditions) of

    (difX < summedHalfWidths) && (difY < summedHalfHeights);

is put in the return statement; where

difX = absoluteValueOf(rect1.x – rect2.x) and difY = absoluteValueOf(rect1.y - rect2.y)

The Program

The ANDed sub-conditions is in the return statement as the principal solution. The program is (read the code and comments):

package main

import (
	"fmt"
	"math"
)

type Rectangle struct {
	x, y, width, height float64
}

func (r Rectangle) Intersects(other Rectangle) bool {
	difX := math.Abs(r.x - other.x)
	difY := math.Abs(r.y - other.y)
	summedHalfWidths := (r.width + other.width) / 2.0
	summedHalfHeights := (r.height + other.height) / 2.0
	return (difX < summedHalfWidths) && (difY < summedHalfHeights)
}

func main() {
	// Example 1: Intersecting Rectangles
	r1 := Rectangle{0, 0, 10, 10}
	r2 := Rectangle{8, 0, 10, 10}
	fmt.Printf("Example 1 (Intersection): %s\n", formatBool(r1.Intersects(r2)))

	// Example 2: Non-Intersecting Rectangles
	r3 := Rectangle{0, 0, 4, 4}
	r4 := Rectangle{10, 10, 4, 4}
	fmt.Printf("Example 2 (Non-intersection): %s\n", formatBool(r3.Intersects(r4)))
}

func formatBool(b bool) string {
	if b {
		return "Yes"
	}
	return "No"
}

The output is:

    Example 1 (Intersection): Yes
    Example 2 (Non-intersection): No

What are the behaviors of your algorithms for edge cases?

a) If both rectangles share a common border from outside, is that intersection?
b) If one of the rectangles is completely included inside the other one, is that intersection?

Solution a) The choice made by the author to question a) is No. That is handled by using ">" instead of ">=" or "<" instead of "<=" for either algorithm.
Solution b) The choice made by the author to question b) is Yes. That needs extra coding which the author has not provided. That is left as an exercise for the reader.