Black Lives Matter. Support the Equal Justice Initiative.

Source file src/image/geom.go

Documentation: image

     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  // Bounds implements the Image interface.
   250  func (r Rectangle) Bounds() Rectangle {
   251  	return r
   252  }
   253  
   254  // ColorModel implements the Image interface.
   255  func (r Rectangle) ColorModel() color.Model {
   256  	return color.Alpha16Model
   257  }
   258  
   259  // ZR is the zero Rectangle.
   260  //
   261  // Deprecated: Use a literal image.Rectangle{} instead.
   262  var ZR Rectangle
   263  
   264  // Rect is shorthand for Rectangle{Pt(x0, y0), Pt(x1, y1)}. The returned
   265  // rectangle has minimum and maximum coordinates swapped if necessary so that
   266  // it is well-formed.
   267  func Rect(x0, y0, x1, y1 int) Rectangle {
   268  	if x0 > x1 {
   269  		x0, x1 = x1, x0
   270  	}
   271  	if y0 > y1 {
   272  		y0, y1 = y1, y0
   273  	}
   274  	return Rectangle{Point{x0, y0}, Point{x1, y1}}
   275  }
   276  
   277  // mul3NonNeg returns (x * y * z), unless at least one argument is negative or
   278  // if the computation overflows the int type, in which case it returns -1.
   279  func mul3NonNeg(x int, y int, z int) int {
   280  	if (x < 0) || (y < 0) || (z < 0) {
   281  		return -1
   282  	}
   283  	hi, lo := bits.Mul64(uint64(x), uint64(y))
   284  	if hi != 0 {
   285  		return -1
   286  	}
   287  	hi, lo = bits.Mul64(lo, uint64(z))
   288  	if hi != 0 {
   289  		return -1
   290  	}
   291  	a := int(lo)
   292  	if (a < 0) || (uint64(a) != lo) {
   293  		return -1
   294  	}
   295  	return a
   296  }
   297  
   298  // add2NonNeg returns (x + y), unless at least one argument is negative or if
   299  // the computation overflows the int type, in which case it returns -1.
   300  func add2NonNeg(x int, y int) int {
   301  	if (x < 0) || (y < 0) {
   302  		return -1
   303  	}
   304  	a := x + y
   305  	if a < 0 {
   306  		return -1
   307  	}
   308  	return a
   309  }
   310  

View as plain text