src/image/geom.go

   1 // Copyright 2010 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package image
   6
   7 import (
   8         "image/color"
   9         "math/bits"
  10         "strconv"
  11 )
  12
  13 // A Point is an X, Y coordinate pair. The axes increase right and down.
  14 type Point struct {
  15         X, Y int
  16 }
  17
  18 // String returns a string representation of p like "(3,4)".
  19 func (p Point) String() string {
  20         return "(" + strconv.Itoa(p.X) + "," + strconv.Itoa(p.Y) + ")"
  21 }
  22
  23 // Add returns the vector p+q.
  24 func (p Point) Add(q Point) Point {
  25         return Point{p.X + q.X, p.Y + q.Y}
  26 }
  27
  28 // Sub returns the vector p-q.
  29 func (p Point) Sub(q Point) Point {
  30         return Point{p.X - q.X, p.Y - q.Y}
  31 }
  32
  33 // Mul returns the vector p*k.
  34 func (p Point) Mul(k int) Point {
  35         return Point{p.X * k, p.Y * k}
  36 }
  37
  38 // Div returns the vector p/k.
  39 func (p Point) Div(k int) Point {
  40         return Point{p.X / k, p.Y / k}
  41 }
  42
  43 // In reports whether p is in r.
  44 func (p Point) In(r Rectangle) bool {
  45         return r.Min.X <= p.X && p.X < r.Max.X &&
  46                 r.Min.Y <= p.Y && p.Y < r.Max.Y
  47 }
  48
  49 // Mod returns the point q in r such that p.X-q.X is a multiple of r's width
  50 // and p.Y-q.Y is a multiple of r's height.
  51 func (p Point) Mod(r Rectangle) Point {
  52         w, h := r.Dx(), r.Dy()
  53         p = p.Sub(r.Min)
  54         p.X = p.X % w
  55         if p.X < 0 {
  56                 p.X += w
  57         }
  58         p.Y = p.Y % h
  59         if p.Y < 0 {
  60                 p.Y += h
  61         }
  62         return p.Add(r.Min)
  63 }
  64
  65 // Eq reports whether p and q are equal.
  66 func (p Point) Eq(q Point) bool {
  67         return p == q
  68 }
  69
  70 // ZP is the zero [Point].
  71 //
  72 // Deprecated: Use a literal [image.Point] instead.
  73 var ZP Point
  74
  75 // Pt is shorthand for [Point]{X, Y}.
  76 func Pt(X, Y int) Point {
  77         return Point{X, Y}
  78 }
  79
  80 // A Rectangle contains the points with Min.X <= X < Max.X, Min.Y <= Y < Max.Y.
  81 // It is well-formed if Min.X <= Max.X and likewise for Y. Points are always
  82 // well-formed. A rectangle's methods always return well-formed outputs for
  83 // well-formed inputs.
  84 //
  85 // A Rectangle is also an [Image] whose bounds are the rectangle itself. At
  86 // returns color.Opaque for points in the rectangle and color.Transparent
  87 // otherwise.
  88 type Rectangle struct {
  89         Min, Max Point
  90 }
  91
  92 // String returns a string representation of r like "(3,4)-(6,5)".
  93 func (r Rectangle) String() string {
  94         return r.Min.String() + "-" + r.Max.String()
  95 }
  96
  97 // Dx returns r's width.
  98 func (r Rectangle) Dx() int {
  99         return r.Max.X - r.Min.X
 100 }
 101
 102 // Dy returns r's height.
 103 func (r Rectangle) Dy() int {
 104         return r.Max.Y - r.Min.Y
 105 }
 106
 107 // Size returns r's width and height.
 108 func (r Rectangle) Size() Point {
 109         return Point{
 110                 r.Max.X - r.Min.X,
 111                 r.Max.Y - r.Min.Y,
 112         }
 113 }
 114
 115 // Add returns the rectangle r translated by p.
 116 func (r Rectangle) Add(p Point) Rectangle {
 117         return Rectangle{
 118                 Point{r.Min.X + p.X, r.Min.Y + p.Y},
 119                 Point{r.Max.X + p.X, r.Max.Y + p.Y},
 120         }
 121 }
 122
 123 // Sub returns the rectangle r translated by -p.
 124 func (r Rectangle) Sub(p Point) Rectangle {
 125         return Rectangle{
 126                 Point{r.Min.X - p.X, r.Min.Y - p.Y},
 127                 Point{r.Max.X - p.X, r.Max.Y - p.Y},
 128         }
 129 }
 130
 131 // Inset returns the rectangle r inset by n, which may be negative. If either
 132 // of r's dimensions is less than 2*n then an empty rectangle near the center
 133 // of r will be returned.
 134 func (r Rectangle) Inset(n int) Rectangle {
 135         if r.Dx() < 2*n {
 136                 r.Min.X = (r.Min.X + r.Max.X) / 2
 137                 r.Max.X = r.Min.X
 138         } else {
 139                 r.Min.X += n
 140                 r.Max.X -= n
 141         }
 142         if r.Dy() < 2*n {
 143                 r.Min.Y = (r.Min.Y + r.Max.Y) / 2
 144                 r.Max.Y = r.Min.Y
 145         } else {
 146                 r.Min.Y += n
 147                 r.Max.Y -= n
 148         }
 149         return r
 150 }
 151
 152 // Intersect returns the largest rectangle contained by both r and s. If the
 153 // two rectangles do not overlap then the zero rectangle will be returned.
 154 func (r Rectangle) Intersect(s Rectangle) Rectangle {
 155         if r.Min.X < s.Min.X {
 156                 r.Min.X = s.Min.X
 157         }
 158         if r.Min.Y < s.Min.Y {
 159                 r.Min.Y = s.Min.Y
 160         }
 161         if r.Max.X > s.Max.X {
 162                 r.Max.X = s.Max.X
 163         }
 164         if r.Max.Y > s.Max.Y {
 165                 r.Max.Y = s.Max.Y
 166         }
 167         // Letting r0 and s0 be the values of r and s at the time that the method
 168         // is called, this next line is equivalent to:
 169         //
 170         // if max(r0.Min.X, s0.Min.X) >= min(r0.Max.X, s0.Max.X) || likewiseForY { etc }
 171         if r.Empty() {
 172                 return ZR
 173         }
 174         return r
 175 }
 176
 177 // Union returns the smallest rectangle that contains both r and s.
 178 func (r Rectangle) Union(s Rectangle) Rectangle {
 179         if r.Empty() {
 180                 return s
 181         }
 182         if s.Empty() {
 183                 return r
 184         }
 185         if r.Min.X > s.Min.X {
 186                 r.Min.X = s.Min.X
 187         }
 188         if r.Min.Y > s.Min.Y {
 189                 r.Min.Y = s.Min.Y
 190         }
 191         if r.Max.X < s.Max.X {
 192                 r.Max.X = s.Max.X
 193         }
 194         if r.Max.Y < s.Max.Y {
 195                 r.Max.Y = s.Max.Y
 196         }
 197         return r
 198 }
 199
 200 // Empty reports whether the rectangle contains no points.
 201 func (r Rectangle) Empty() bool {
 202         return r.Min.X >= r.Max.X || r.Min.Y >= r.Max.Y
 203 }
 204
 205 // Eq reports whether r and s contain the same set of points. All empty
 206 // rectangles are considered equal.
 207 func (r Rectangle) Eq(s Rectangle) bool {
 208         return r == s || r.Empty() && s.Empty()
 209 }
 210
 211 // Overlaps reports whether r and s have a non-empty intersection.
 212 func (r Rectangle) Overlaps(s Rectangle) bool {
 213         return !r.Empty() && !s.Empty() &&
 214                 r.Min.X < s.Max.X && s.Min.X < r.Max.X &&
 215                 r.Min.Y < s.Max.Y && s.Min.Y < r.Max.Y
 216 }
 217
 218 // In reports whether every point in r is in s.
 219 func (r Rectangle) In(s Rectangle) bool {
 220         if r.Empty() {
 221                 return true
 222         }
 223         // Note that r.Max is an exclusive bound for r, so that r.In(s)
 224         // does not require that r.Max.In(s).
 225         return s.Min.X <= r.Min.X && r.Max.X <= s.Max.X &&
 226                 s.Min.Y <= r.Min.Y && r.Max.Y <= s.Max.Y
 227 }
 228
 229 // Canon returns the canonical version of r. The returned rectangle has minimum
 230 // and maximum coordinates swapped if necessary so that it is well-formed.
 231 func (r Rectangle) Canon() Rectangle {
 232         if r.Max.X < r.Min.X {
 233                 r.Min.X, r.Max.X = r.Max.X, r.Min.X
 234         }
 235         if r.Max.Y < r.Min.Y {
 236                 r.Min.Y, r.Max.Y = r.Max.Y, r.Min.Y
 237         }
 238         return r
 239 }
 240
 241 // At implements the [Image] interface.
 242 func (r Rectangle) At(x, y int) color.Color {
 243         if (Point{x, y}).In(r) {
 244                 return color.Opaque
 245         }
 246         return color.Transparent
 247 }
 248
 249 // RGBA64At implements the [RGBA64Image] interface.
 250 func (r Rectangle) RGBA64At(x, y int) color.RGBA64 {
 251         if (Point{x, y}).In(r) {
 252                 return color.RGBA64{0xffff, 0xffff, 0xffff, 0xffff}
 253         }
 254         return color.RGBA64{}
 255 }
 256
 257 // Bounds implements the [Image] interface.
 258 func (r Rectangle) Bounds() Rectangle {
 259         return r
 260 }
 261
 262 // ColorModel implements the [Image] interface.
 263 func (r Rectangle) ColorModel() color.Model {
 264         return color.Alpha16Model
 265 }
 266
 267 // ZR is the zero [Rectangle].
 268 //
 269 // Deprecated: Use a literal [image.Rectangle] instead.
 270 var ZR Rectangle
 271
 272 // Rect is shorthand for [Rectangle]{Pt(x0, y0), [Pt](x1, y1)}. The returned
 273 // rectangle has minimum and maximum coordinates swapped if necessary so that
 274 // it is well-formed.
 275 func Rect(x0, y0, x1, y1 int) Rectangle {
 276         if x0 > x1 {
 277                 x0, x1 = x1, x0
 278         }
 279         if y0 > y1 {
 280                 y0, y1 = y1, y0
 281         }
 282         return Rectangle{Point{x0, y0}, Point{x1, y1}}
 283 }
 284
 285 // mul3NonNeg returns (x * y * z), unless at least one argument is negative or
 286 // if the computation overflows the int type, in which case it returns -1.
 287 func mul3NonNeg(x int, y int, z int) int {
 288         if (x < 0) || (y < 0) || (z < 0) {
 289                 return -1
 290         }
 291         hi, lo := bits.Mul64(uint64(x), uint64(y))
 292         if hi != 0 {
 293                 return -1
 294         }
 295         hi, lo = bits.Mul64(lo, uint64(z))
 296         if hi != 0 {
 297                 return -1
 298         }
 299         a := int(lo)
 300         if (a < 0) || (uint64(a) != lo) {
 301                 return -1
 302         }
 303         return a
 304 }
 305
 306 // add2NonNeg returns (x + y), unless at least one argument is negative or if
 307 // the computation overflows the int type, in which case it returns -1.
 308 func add2NonNeg(x int, y int) int {
 309         if (x < 0) || (y < 0) {
 310                 return -1
 311         }
 312         a := x + y
 313         if a < 0 {
 314                 return -1
 315         }
 316         return a
 317 }