box.go

// Package region provides efficient 2D region operations using Y-X banded rectangles.
//
// A Region is simply a set of disjoint (non-overlapping) rectangles, plus an
// "extent" rectangle which is the smallest single rectangle that contains all
// the non-overlapping rectangles.
//
// A Region is implemented as a "y-x-banded" array of rectangles. This array
// imposes two degrees of order. First, all rectangles are sorted by top side
// y coordinate first (y1), and then by left side x coordinate (x1).
//
// Furthermore, the rectangles are grouped into "bands". Each rectangle in a
// band has the same top y coordinate (y1), and each has the same bottom y
// coordinate (y2). Thus all rectangles in a band differ only in their left
// and right side (x1 and x2). Bands are implicit in the array of rectangles:
// there is no separate list of band start pointers.
//
// An added constraint on the rectangles is that they must cover as much
// horizontal area as possible: no two rectangles within a band are allowed
// to touch.
//
// Whenever possible, bands will be merged together to cover a greater vertical
// distance (and thus reduce the number of rectangles). Two bands can be merged
// only if the bottom of one touches the top of the other and they have
// rectangles in the same places (of the same width, of course).

package region

import "math"

// Box represents a rectangle using inclusive-exclusive semantics: [X1, X2) x [Y1, Y2).
// A valid box requires X1 < X2 and Y1 < Y2.
type Box struct {
	X1, Y1, X2, Y2 int32
}

// IsValid returns true if the box has positive width and height.
func (b Box) IsValid() bool {
	return b.X1 < b.X2 && b.Y1 < b.Y2
}

// Width returns the width of the box (X2 - X1).
func (b Box) Width() int32 {
	return b.X2 - b.X1
}

// Height returns the height of the box (Y2 - Y1).
func (b Box) Height() int32 {
	return b.Y2 - b.Y1
}

// Area returns the area of the box.
func (b Box) Area() int64 {
	return int64(b.Width()) * int64(b.Height())
}

// Contains returns true if point (x, y) is inside the box.
// Uses inclusive-exclusive: x1 <= x < x2, y1 <= y < y2.
func (b Box) Contains(x, y int32) bool {
	return x >= b.X1 && x < b.X2 && y >= b.Y1 && y < b.Y2
}

// Intersects returns true if this box overlaps with other.
func (b Box) Intersects(other Box) bool {
	return b.X1 < other.X2 && b.X2 > other.X1 &&
		b.Y1 < other.Y2 && b.Y2 > other.Y1
}

// Subsumes returns true if this box completely contains other.
func (b Box) Subsumes(other Box) bool {
	return b.X1 <= other.X1 && b.X2 >= other.X2 &&
		b.Y1 <= other.Y1 && b.Y2 >= other.Y2
}

// Equal returns true if two boxes have the same coordinates.
func (b Box) Equal(other Box) bool {
	return b.X1 == other.X1 && b.Y1 == other.Y1 &&
		b.X2 == other.X2 && b.Y2 == other.Y2
}

// Intersection returns the intersection of two boxes.
// Returns an invalid box if they don't overlap.
func (b Box) Intersection(other Box) Box {
	return Box{
		X1: max32(b.X1, other.X1),
		Y1: max32(b.Y1, other.Y1),
		X2: min32(b.X2, other.X2),
		Y2: min32(b.Y2, other.Y2),
	}
}

// Union returns the smallest box containing both boxes.
func (b Box) Union(other Box) Box {
	return Box{
		X1: min32(b.X1, other.X1),
		Y1: min32(b.Y1, other.Y1),
		X2: max32(b.X2, other.X2),
		Y2: max32(b.Y2, other.Y2),
	}
}

// Translate returns a new box shifted by (dx, dy).
// Returns the original box if the translation would cause overflow.
func (b Box) Translate(dx, dy int32) Box {
	// Check for overflow using 64-bit arithmetic
	x1 := int64(b.X1) + int64(dx)
	y1 := int64(b.Y1) + int64(dy)
	x2 := int64(b.X2) + int64(dx)
	y2 := int64(b.Y2) + int64(dy)

	if x1 < math.MinInt32 || x1 > math.MaxInt32 ||
		y1 < math.MinInt32 || y1 > math.MaxInt32 ||
		x2 < math.MinInt32 || x2 > math.MaxInt32 ||
		y2 < math.MinInt32 || y2 > math.MaxInt32 {
		return b // Return original on overflow
	}

	return Box{
		X1: int32(x1),
		Y1: int32(y1),
		X2: int32(x2),
		Y2: int32(y2),
	}
}

// min32 returns the minimum of two int32 values.
func min32(a, b int32) int32 {
	if a < b {
		return a
	}
	return b
}

// max32 returns the maximum of two int32 values.
func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}

// emptyBox returns an empty (invalid) box.
func emptyBox() Box {
	return Box{X1: 0, Y1: 0, X2: 0, Y2: 0}
}