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:

1. Bands: Rectangles are grouped into horizontal bands sharing the same Y coordinates (Y1, Y2)
2. Sorting: Within each band, rectangles are sorted by X coordinate
3. Non-overlapping: Rectangles within a band never overlap or touch
4. 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.

1. Fork the repository
2. Create your feature branch (git checkout -b feature/short-description)
3. Commit your changes (git commit -m 'Add feature')
4. Push to the branch (git push origin feature/short-description)
5. Open a Pull Request