README
¶
Region
Efficient 2D region operations using Y-X banded rectangles
Region is a pure Go library for boolean operations on 2D regions. It represents complex, non-rectangular areas as Y-X banded rectangles for compact storage and fast unions, intersections, subtractions, and spatial queries.
Features
- Pure Go - No CGO or external dependencies
- Compact representation - Y-X banding minimizes rectangle count
- Boolean ops - Union, Intersect, Subtract, Inverse, Translate
- Queries - Point and rectangle containment on the banded structure
- Tested - Unit tests and benchmarks
- Portable - Linux, macOS, and Windows
Installation
go get github.com/PekingSpades/region
Requires Go 1.18+.
Documentation
API reference: https://pkg.go.dev/github.com/PekingSpades/region
Quick Start
package main
import (
"fmt"
"github.com/PekingSpades/region"
)
func main() {
// Create a region from a rectangle (x, y, width, height)
r := region.NewRect(0, 0, 100, 100)
// Add another rectangle
r.UnionRect(region.Box{X1: 50, Y1: 50, X2: 150, Y2: 150})
// Check point containment
fmt.Println(r.ContainsPoint(75, 75)) // true
fmt.Println(r.ContainsPoint(200, 200)) // false
// Get the bounding box
fmt.Println(r.Extents()) // {0 0 150 150}
}
API Examples
Creating Regions
// Empty region
r1 := region.New()
// Single rectangle (x, y, width, height)
r2 := region.NewRect(10, 20, 100, 50)
// From bounding box (x1, y1, x2, y2)
r3 := region.NewWithExtents(region.Box{X1: 0, Y1: 0, X2: 100, Y2: 100})
// From multiple rectangles (automatically merged)
boxes := []region.Box{
{X1: 0, Y1: 0, X2: 50, Y2: 50},
{X1: 30, Y1: 30, X2: 80, Y2: 80},
}
r4 := region.NewRects(boxes)
Set Operations
r1 := region.NewRect(0, 0, 100, 100)
r2 := region.NewRect(50, 50, 100, 100)
// Union: r1 = r1 union r2
r1.Union(r2)
// Intersection: r1 = r1 intersect r2
r1 = region.NewRect(0, 0, 100, 100)
r2 = region.NewRect(50, 50, 100, 100)
r1.Intersect(r2)
// Subtraction: r1 = r1 - r2
r1 = region.NewRect(0, 0, 100, 100)
r2 = region.NewRect(50, 50, 100, 100)
r1.Subtract(r2)
// Inverse within bounds: r1 = bounds - r1
r1 = region.NewRect(0, 0, 100, 100)
r1.Inverse(region.Box{X1: 0, Y1: 0, X2: 200, Y2: 200})
Queries
r := region.NewRect(0, 0, 100, 100)
r.UnionRect(region.Box{X1: 200, Y1: 0, X2: 300, Y2: 100})
// Point containment
r.ContainsPoint(50, 50) // true
// Point containment with the containing box
ok, box := r.ContainsPointBox(50, 50)
// ok=true, box={0, 0, 100, 100}
// Rectangle containment
r.ContainsRectangle(region.Box{X1: 10, Y1: 10, X2: 90, Y2: 90})
// Returns: OverlapIn, OverlapOut, or OverlapPart
// Properties
r.IsEmpty() // false
r.NumRects() // 2
r.Extents() // {0 0 300 100}
r.Rectangles() // []Box{{0,0,100,100}, {200,0,300,100}}
Transformation
r := region.NewRect(0, 0, 100, 100)
// Translate by (dx, dy)
r.Translate(50, 50)
// Now: {50 50 150 150}
// Clone (deep copy)
r2 := r.Clone()
// Copy from another region
r.Copy(otherRegion)
// Reset to single rectangle
r.Reset(region.Box{X1: 0, Y1: 0, X2: 100, Y2: 100})
// Clear to empty
r.Clear()
How It Works
Region uses the Y-X banded representation for regions:
- Bands: Rectangles are grouped into horizontal bands sharing the same Y coordinates (Y1, Y2)
- Sorting: Within each band, rectangles are sorted by X coordinate
- Non-overlapping: Rectangles within a band never overlap or touch
- Coalescing: Adjacent bands with identical X structure are automatically merged
This representation enables efficient set operations and fast point queries using binary search.
Example: An L-shaped region
+-------+ Band 1: Y=[0,50) -> [{0,0,100,50}]
| |
| |
+-------+
| |
+---+ Band 2: Y=[50,100) -> [{0,50,50,100}]
Stored as 2 rectangles in 2 bands
Operations Visualized
Union (r1 union r2)
r1 r2 Union Result
0 50 50 150 0 50 150
0 +----+ 0 +----------+ 0 +-------------------+
| | | | | | Band 1: Y=[0,50)
| | | | | | → [{0,0,150,50}]
50+----+ 50 | | 50 +---------+---------+
| | | |
| | | | Band 2: Y=[50,100)
100 +----------+ 100 +---------+ → [{50,50,150,100}]
r1 := region.NewRect(0, 0, 50, 50) // {0,0,50,50}
r2 := region.NewRect(50, 0, 100, 100) // {50,0,150,100}
r1.Union(r2)
// Result: 2 rectangles in 2 bands
// rects=[{0,0,150,50}, {50,50,150,100}]
Intersect (r1 intersect r2)
r1 r2 Intersect Result
0 100 25 75 25 75
0 +------------+ 0 0
| |
| | 25 +------+ 25 +------+
| | |XXXXXX| |XXXXXX|
| | 75 +------+ 75 +------+
| |
100+------------+ 1 rectangle: {25,25,75,75}
r1 := region.NewRect(0, 0, 100, 100) // {0,0,100,100}
r2 := region.NewRect(25, 25, 50, 50) // {25,25,75,75}
r1.Intersect(r2)
// Result: {25,25,75,75} (the overlapping area)
Subtract (r1 - r2)
r1 r2 Subtract Result
0 100 25 75 0 25 75 100
0 +------------+ 0 +------------+
| | | | Band 1: [{0,0,100,25}]
| | 25 +----+ 25 +--+ +--+
| | |XXXX| | | | | Band 2: [{0,25,25,75},
| | 75 +----+ 75 +--+ +--+ {75,25,100,75}]
| | | |
100+------------+ 100 +------------+ Band 3: [{0,75,100,100}]
r1 := region.NewRect(0, 0, 100, 100) // {0,0,100,100}
r2 := region.NewRect(25, 25, 50, 50) // {25,25,75,75}
r1.Subtract(r2)
// Result: Frame with hole - 4 rectangles in 3 bands
// rects=[{0,0,100,25}, {0,25,25,75}, {75,25,100,75}, {0,75,100,100}]
Inverse (bounds - r)
Region r Bounds Inverse Result
25 75 0 100 0 25 75 100
0 0 +------------+ 0 +------------+
| | | | Band 1: [{0,0,100,25}]
25 +------+ 25 | | 25 +--+ +--+
|XXXXXX| | | | | | | Band 2: [{0,25,25,75},
75 +------+ 75 | | 75 +--+ +--+ {75,25,100,75}]
| | | |
100+------------+ 100 +------------+ Band 3: [{0,75,100,100}]
r := region.NewRect(25, 25, 50, 50) // {25,25,75,75}
r.Inverse(region.Box{X1: 0, Y1: 0, X2: 100, Y2: 100})
// Result: bounds minus original region - 4 rectangles in 3 bands
// rects=[{0,0,100,25}, {0,25,25,75}, {75,25,100,75}, {0,75,100,100}]
Translate
Before After (dx=30, dy=20)
0 50 30 80
0 +----+ 0
| |
| | 20 +----+
50+----+ | |
| |
70 +----+
r := region.NewRect(0, 0, 50, 50)
r.Translate(30, 20)
// Result: {30,20,80,70}
ContainsPoint
Region with 2 rectangles:
0 50 100 150
0 +-----+ +-----+
| | | |
| A ● | ○ | B ● | ● = test point (25, 25), (125, 25)
| | | | ○ = test point (75, 25)
50+-----+ +-----+
r := region.NewRect(0, 0, 50, 50)
r.UnionRect(region.Box{X1: 100, Y1: 0, X2: 150, Y2: 50})
r.ContainsPoint(25, 25) // true (inside rect A)
r.ContainsPoint(75, 25) // false (between rects)
r.ContainsPoint(125, 25) // true (inside rect B)
ContainsRectangle
Region R (0,0,100,100):
0 100
0 +---------------+
| |
| OverlapIn | Test box {10,10,40,40}: completely inside
| +-----+ | → Returns: OverlapIn
| | | |
| +-----+ |
| |
100+---------------+
0 50 100 150
0 +---------------+
| | Test box {50,50,150,150}: extends outside
50 | +-------+------+ → Returns: OverlapPart
| |XXXXXXX|XXXXXX|
100+-------|-------+XXXXXX|
|XXXXXXXXXXXXXX|
150 +--------------+
0 100 150 200
0 +-------+ +--------+
| R | | Test | Test box {150,0,200,50}: completely outside
| | | box | → Returns: OverlapOut
| | 50 +--------+
| |
100+-------+
r := region.NewRect(0, 0, 100, 100)
r.ContainsRectangle(region.Box{X1: 10, Y1: 10, X2: 40, Y2: 40})
// Returns: OverlapIn (completely inside)
r.ContainsRectangle(region.Box{X1: 50, Y1: 50, X2: 150, Y2: 150})
// Returns: OverlapPart (partially overlapping)
r.ContainsRectangle(region.Box{X1: 150, Y1: 0, X2: 200, Y2: 50})
// Returns: OverlapOut (completely outside)
Y-X Banding in Action
Input: 3 overlapping rectangles
0 20 50 70 100
0 +------------------+ A: {0,0,70,50}
| A |
| |
30 | +------+------+--------+ B: {20,30,50,70}
| | B | | | C: {50,30,100,100}
50 +----+------+------+ |
| | |
70 +------+ C |
| |
100 +---------------+
After NewRects (Y-X banded): Result rectangles:
0 20 50 70 100
0 +--------------------+ Band 1 (Y=0-30):
| | → [{0,0,70,30}]
30 +--------------------+-------+ Band 2 (Y=30-50):
| | → [{0,30,100,50}]
50 +-----+----------------------+ Band 3 (Y=50-70):
| | → [{20,50,100,70}]
70 +------+---------------+ Band 4 (Y=70-100):
| | → [{50,70,100,100}]
100 +---------------+
boxes := []region.Box{
{X1: 0, Y1: 0, X2: 70, Y2: 50}, // A
{X1: 20, Y1: 30, X2: 50, Y2: 70}, // B
{X1: 50, Y1: 30, X2: 100, Y2: 100}, // C
}
r := region.NewRects(boxes)
// Result: 4 rectangles in 4 bands
// rects=[{0,0,70,30}, {0,30,100,50}, {20,50,100,70}, {50,70,100,100}]
Performance
Benchmarks on Intel Core i9-10900K @ 3.70GHz (Windows, amd64):
| Operation | Simple (1 rect) | Complex (32 rects) |
|---|---|---|
| NewRect | 26 ns | - |
| Union | 227 ns | 54.5 us |
| Intersect | 54 ns | 56.8 us |
| Subtract | 190 ns | 58.5 us |
| ContainsPoint | 2.7 ns | 8 ns |
| ContainsRectangle | 3.5 ns | 50 ns |
| Translate | 6.5 ns | 231 ns |
| Clone | 0.4 ns | 350 ns |
NewRects vs repeated UnionRect for batch initialization:
| Rectangles | NewRects | UnionRect | Speedup |
|---|---|---|---|
| 10 | 471 ns | 1.4 us | 3x |
| 100 | 2.9 us | 53 us | 18x |
| 1000 | 32 us | 3.8 ms | 120x |
Run benchmarks yourself:
go test -bench=. -benchmem
License
MIT License. See LICENSE for details.
Contributing
Contributions are welcome! Please feel free to submit a Pull Request.
- Fork the repository
- Create your feature branch (
git checkout -b feature/short-description) - Commit your changes (
git commit -m 'Add feature') - Push to the branch (
git push origin feature/short-description) - Open a Pull Request
Documentation
¶
Overview ¶
Package region provides efficient 2D region operations using Y-X banded rectangles.
A Region is a set of disjoint rectangles, plus an extent rectangle that bounds them. It supports union, intersection, subtraction, inversion, translation, and spatial queries such as point and rectangle containment.
Internally, rectangles are stored in a Y-X banded array: sorted by top side Y1, then by left side X1. Rectangles are grouped into horizontal bands that share the same Y1 and Y2. Rectangles within a band never overlap or touch. Adjacent bands with identical X spans are coalesced to reduce rectangle count.
Coordinates use inclusive-exclusive semantics: [X1, X2) x [Y1, Y2) with int32 values. Boxes with non-positive width or height are invalid.
Index ¶
- type Box
- func (b Box) Area() int64
- func (b Box) Contains(x, y int32) bool
- func (b Box) Equal(other Box) bool
- func (b Box) Height() int32
- func (b Box) Intersection(other Box) Box
- func (b Box) Intersects(other Box) bool
- func (b Box) IsValid() bool
- func (b Box) Subsumes(other Box) bool
- func (b Box) Translate(dx, dy int32) Box
- func (b Box) Union(other Box) Box
- func (b Box) Width() int32
- type OverlapType
- type Region
- func (r *Region) Clear()
- func (r *Region) Clone() *Region
- func (r *Region) ContainsPoint(x, y int32) bool
- func (r *Region) ContainsPointBox(x, y int32) (bool, Box)
- func (r *Region) ContainsRectangle(box Box) OverlapType
- func (r *Region) Copy(other *Region)
- func (r *Region) Equal(other *Region) bool
- func (r *Region) Extents() Box
- func (r *Region) Intersect(other *Region)
- func (r *Region) IntersectRect(box Box)
- func (r *Region) Inverse(bounds Box)
- func (r *Region) IsEmpty() bool
- func (r *Region) NotEmpty() bool
- func (r *Region) NumRects() int
- func (r *Region) Rectangles() []Box
- func (r *Region) Reset(box Box)
- func (r *Region) SelfCheck() bool
- func (r *Region) Subtract(other *Region)
- func (r *Region) Translate(dx, dy int32)
- func (r *Region) Union(other *Region)
- func (r *Region) UnionRect(box Box)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Box ¶
type Box struct {
X1, Y1, X2, Y2 int32
}
Box represents a rectangle using inclusive-exclusive semantics: [X1, X2) x [Y1, Y2). A valid box requires X1 < X2 and Y1 < Y2.
func (Box) Contains ¶
Contains returns true if point (x, y) is inside the box. Uses inclusive-exclusive: x1 <= x < x2, y1 <= y < y2.
func (Box) Intersection ¶
Intersection returns the intersection of two boxes. Returns an invalid box if they don't overlap.
func (Box) Intersects ¶
Intersects returns true if this box overlaps with other.
func (Box) Translate ¶
Translate returns a new box shifted by (dx, dy). Returns the original box if the translation would cause overflow.
type OverlapType ¶
type OverlapType int
OverlapType represents the relationship between a rectangle and a region.
const ( // OverlapOut means the rectangle is completely outside the region. OverlapOut OverlapType = iota // OverlapIn means the rectangle is completely inside the region. OverlapIn // OverlapPart means the rectangle partially overlaps the region. OverlapPart )
type Region ¶
type Region struct {
// contains filtered or unexported fields
}
Region represents a set of non-overlapping rectangles. Internally, rectangles are stored in Y-X banded format for efficient operations.
The region is stored as follows:
- extents: bounding box of the entire region
- rects: slice of rectangles in Y-X banded order
For an empty region, rects is nil and extents is invalid. For a single rectangle region, rects may be nil and extents represents the rectangle.
func NewRect ¶
NewRect creates a new region containing a single rectangle. The rectangle is specified by its top-left corner (x, y) and dimensions (width, height). If width or height is <= 0, returns an empty region.
func NewRects ¶
NewRects creates a new region from a slice of rectangles. The rectangles will be validated, sorted, and merged into Y-X banded format. Invalid rectangles (with width <= 0 or height <= 0) are ignored.
func NewWithExtents ¶
NewWithExtents creates a new region from a bounding box. If the box is invalid, returns an empty region.
func (*Region) ContainsPoint ¶
ContainsPoint returns true if the point (x, y) is inside the region.
func (*Region) ContainsPointBox ¶
ContainsPointBox returns true if the point (x, y) is inside the region, along with the box that contains the point (if found).
func (*Region) ContainsRectangle ¶
func (r *Region) ContainsRectangle(box Box) OverlapType
ContainsRectangle returns the overlap relationship between the region and a box. Returns:
- OverlapOut if the box is completely outside the region
- OverlapIn if the box is completely inside the region
- OverlapPart if the box partially overlaps the region
Boxes are not validated here; invalid boxes may return any OverlapType depending on their coordinates. The algorithm walks the banded rectangles to cover the box, tracking whether any part is covered (partIn) and any part is uncovered (partOut). It stops once the box is fully covered, partially covered, or disjoint.
func (*Region) Extents ¶
Extents returns the bounding box of the entire region. Returns an invalid box if the region is empty.
func (*Region) IntersectRect ¶
IntersectRect sets r to the intersection of r and the rectangle.
func (*Region) Inverse ¶
Inverse sets r to the inverse of r within the given bounds. This is equivalent to bounds - r.
func (*Region) Rectangles ¶
Rectangles returns a copy of all rectangles in the region. The rectangles are in Y-X banded order.
func (*Region) SelfCheck ¶
SelfCheck validates the internal consistency of the region. Returns true if the region is valid, false otherwise. This is primarily useful for debugging.
func (*Region) Translate ¶
Translate moves the region by (dx, dy). Translates in place.
- If completely in range after translation: translate all boxes
- If completely out of range: clear the region
- If partially out of range: clip to valid range and filter out-of-range boxes
Source Files