rect.go

Documentation: github.com/golang/geo/r2

     1  // Copyright 2014 Google Inc. All rights reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package r2
    16  
    17  import (
    18  	"fmt"
    19  	"math"
    20  
    21  	"github.com/golang/geo/r1"
    22  )
    23  
    24  // Point represents a point in ℝ².
    25  type Point struct {
    26  	X, Y float64
    27  }
    28  
    29  // Add returns the sum of p and op.
    30  func (p Point) Add(op Point) Point { return Point{p.X + op.X, p.Y + op.Y} }
    31  
    32  // Sub returns the difference of p and op.
    33  func (p Point) Sub(op Point) Point { return Point{p.X - op.X, p.Y - op.Y} }
    34  
    35  // Mul returns the scalar product of p and m.
    36  func (p Point) Mul(m float64) Point { return Point{m * p.X, m * p.Y} }
    37  
    38  // Ortho returns a counterclockwise orthogonal point with the same norm.
    39  func (p Point) Ortho() Point { return Point{-p.Y, p.X} }
    40  
    41  // Dot returns the dot product between p and op.
    42  func (p Point) Dot(op Point) float64 { return p.X*op.X + p.Y*op.Y }
    43  
    44  // Cross returns the cross product of p and op.
    45  func (p Point) Cross(op Point) float64 { return p.X*op.Y - p.Y*op.X }
    46  
    47  // Norm returns the vector's norm.
    48  func (p Point) Norm() float64 { return math.Hypot(p.X, p.Y) }
    49  
    50  // Normalize returns a unit point in the same direction as p.
    51  func (p Point) Normalize() Point {
    52  	if p.X == 0 && p.Y == 0 {
    53  		return p
    54  	}
    55  	return p.Mul(1 / p.Norm())
    56  }
    57  
    58  func (p Point) String() string { return fmt.Sprintf("(%.12f, %.12f)", p.X, p.Y) }
    59  
    60  // Rect represents a closed axis-aligned rectangle in the (x,y) plane.
    61  type Rect struct {
    62  	X, Y r1.Interval
    63  }
    64  
    65  // RectFromPoints constructs a rect that contains the given points.
    66  func RectFromPoints(pts ...Point) Rect {
    67  	// Because the default value on interval is 0,0, we need to manually
    68  	// define the interval from the first point passed in as our starting
    69  	// interval, otherwise we end up with the case of passing in
    70  	// Point{0.2, 0.3} and getting the starting Rect of {0, 0.2}, {0, 0.3}
    71  	// instead of the Rect {0.2, 0.2}, {0.3, 0.3} which is not correct.
    72  	if len(pts) == 0 {
    73  		return Rect{}
    74  	}
    75  
    76  	r := Rect{
    77  		X: r1.Interval{Lo: pts[0].X, Hi: pts[0].X},
    78  		Y: r1.Interval{Lo: pts[0].Y, Hi: pts[0].Y},
    79  	}
    80  
    81  	for _, p := range pts[1:] {
    82  		r = r.AddPoint(p)
    83  	}
    84  	return r
    85  }
    86  
    87  // RectFromCenterSize constructs a rectangle with the given center and size.
    88  // Both dimensions of size must be non-negative.
    89  func RectFromCenterSize(center, size Point) Rect {
    90  	return Rect{
    91  		r1.Interval{Lo: center.X - size.X/2, Hi: center.X + size.X/2},
    92  		r1.Interval{Lo: center.Y - size.Y/2, Hi: center.Y + size.Y/2},
    93  	}
    94  }
    95  
    96  // EmptyRect constructs the canonical empty rectangle. Use IsEmpty() to test
    97  // for empty rectangles, since they have more than one representation. A Rect{}
    98  // is not the same as the EmptyRect.
    99  func EmptyRect() Rect {
   100  	return Rect{r1.EmptyInterval(), r1.EmptyInterval()}
   101  }
   102  
   103  // IsValid reports whether the rectangle is valid.
   104  // This requires the width to be empty iff the height is empty.
   105  func (r Rect) IsValid() bool {
   106  	return r.X.IsEmpty() == r.Y.IsEmpty()
   107  }
   108  
   109  // IsEmpty reports whether the rectangle is empty.
   110  func (r Rect) IsEmpty() bool {
   111  	return r.X.IsEmpty()
   112  }
   113  
   114  // Vertices returns all four vertices of the rectangle. Vertices are returned in
   115  // CCW direction starting with the lower left corner.
   116  func (r Rect) Vertices() [4]Point {
   117  	return [4]Point{
   118  		{r.X.Lo, r.Y.Lo},
   119  		{r.X.Hi, r.Y.Lo},
   120  		{r.X.Hi, r.Y.Hi},
   121  		{r.X.Lo, r.Y.Hi},
   122  	}
   123  }
   124  
   125  // VertexIJ returns the vertex in direction i along the X-axis (0=left, 1=right) and
   126  // direction j along the Y-axis (0=down, 1=up).
   127  func (r Rect) VertexIJ(i, j int) Point {
   128  	x := r.X.Lo
   129  	if i == 1 {
   130  		x = r.X.Hi
   131  	}
   132  	y := r.Y.Lo
   133  	if j == 1 {
   134  		y = r.Y.Hi
   135  	}
   136  	return Point{x, y}
   137  }
   138  
   139  // Lo returns the low corner of the rect.
   140  func (r Rect) Lo() Point {
   141  	return Point{r.X.Lo, r.Y.Lo}
   142  }
   143  
   144  // Hi returns the high corner of the rect.
   145  func (r Rect) Hi() Point {
   146  	return Point{r.X.Hi, r.Y.Hi}
   147  }
   148  
   149  // Center returns the center of the rectangle in (x,y)-space
   150  func (r Rect) Center() Point {
   151  	return Point{r.X.Center(), r.Y.Center()}
   152  }
   153  
   154  // Size returns the width and height of this rectangle in (x,y)-space. Empty
   155  // rectangles have a negative width and height.
   156  func (r Rect) Size() Point {
   157  	return Point{r.X.Length(), r.Y.Length()}
   158  }
   159  
   160  // ContainsPoint reports whether the rectangle contains the given point.
   161  // Rectangles are closed regions, i.e. they contain their boundary.
   162  func (r Rect) ContainsPoint(p Point) bool {
   163  	return r.X.Contains(p.X) && r.Y.Contains(p.Y)
   164  }
   165  
   166  // InteriorContainsPoint returns true iff the given point is contained in the interior
   167  // of the region (i.e. the region excluding its boundary).
   168  func (r Rect) InteriorContainsPoint(p Point) bool {
   169  	return r.X.InteriorContains(p.X) && r.Y.InteriorContains(p.Y)
   170  }
   171  
   172  // Contains reports whether the rectangle contains the given rectangle.
   173  func (r Rect) Contains(other Rect) bool {
   174  	return r.X.ContainsInterval(other.X) && r.Y.ContainsInterval(other.Y)
   175  }
   176  
   177  // InteriorContains reports whether the interior of this rectangle contains all of the
   178  // points of the given other rectangle (including its boundary).
   179  func (r Rect) InteriorContains(other Rect) bool {
   180  	return r.X.InteriorContainsInterval(other.X) && r.Y.InteriorContainsInterval(other.Y)
   181  }
   182  
   183  // Intersects reports whether this rectangle and the other rectangle have any points in common.
   184  func (r Rect) Intersects(other Rect) bool {
   185  	return r.X.Intersects(other.X) && r.Y.Intersects(other.Y)
   186  }
   187  
   188  // InteriorIntersects reports whether the interior of this rectangle intersects
   189  // any point (including the boundary) of the given other rectangle.
   190  func (r Rect) InteriorIntersects(other Rect) bool {
   191  	return r.X.InteriorIntersects(other.X) && r.Y.InteriorIntersects(other.Y)
   192  }
   193  
   194  // AddPoint expands the rectangle to include the given point. The rectangle is
   195  // expanded by the minimum amount possible.
   196  func (r Rect) AddPoint(p Point) Rect {
   197  	return Rect{r.X.AddPoint(p.X), r.Y.AddPoint(p.Y)}
   198  }
   199  
   200  // AddRect expands the rectangle to include the given rectangle. This is the
   201  // same as replacing the rectangle by the union of the two rectangles, but
   202  // is more efficient.
   203  func (r Rect) AddRect(other Rect) Rect {
   204  	return Rect{r.X.Union(other.X), r.Y.Union(other.Y)}
   205  }
   206  
   207  // ClampPoint returns the closest point in the rectangle to the given point.
   208  // The rectangle must be non-empty.
   209  func (r Rect) ClampPoint(p Point) Point {
   210  	return Point{r.X.ClampPoint(p.X), r.Y.ClampPoint(p.Y)}
   211  }
   212  
   213  // Expanded returns a rectangle that has been expanded in the x-direction
   214  // by margin.X, and in y-direction by margin.Y. If either margin is empty,
   215  // then shrink the interval on the corresponding sides instead. The resulting
   216  // rectangle may be empty. Any expansion of an empty rectangle remains empty.
   217  func (r Rect) Expanded(margin Point) Rect {
   218  	xx := r.X.Expanded(margin.X)
   219  	yy := r.Y.Expanded(margin.Y)
   220  	if xx.IsEmpty() || yy.IsEmpty() {
   221  		return EmptyRect()
   222  	}
   223  	return Rect{xx, yy}
   224  }
   225  
   226  // ExpandedByMargin returns a Rect that has been expanded by the amount on all sides.
   227  func (r Rect) ExpandedByMargin(margin float64) Rect {
   228  	return r.Expanded(Point{margin, margin})
   229  }
   230  
   231  // Union returns the smallest rectangle containing the union of this rectangle and
   232  // the given rectangle.
   233  func (r Rect) Union(other Rect) Rect {
   234  	return Rect{r.X.Union(other.X), r.Y.Union(other.Y)}
   235  }
   236  
   237  // Intersection returns the smallest rectangle containing the intersection of this
   238  // rectangle and the given rectangle.
   239  func (r Rect) Intersection(other Rect) Rect {
   240  	xx := r.X.Intersection(other.X)
   241  	yy := r.Y.Intersection(other.Y)
   242  	if xx.IsEmpty() || yy.IsEmpty() {
   243  		return EmptyRect()
   244  	}
   245  
   246  	return Rect{xx, yy}
   247  }
   248  
   249  // ApproxEqual returns true if the x- and y-intervals of the two rectangles are
   250  // the same up to the given tolerance.
   251  func (r Rect) ApproxEqual(r2 Rect) bool {
   252  	return r.X.ApproxEqual(r2.X) && r.Y.ApproxEqual(r2.Y)
   253  }
   254  
   255  func (r Rect) String() string { return fmt.Sprintf("[Lo%s, Hi%s]", r.Lo(), r.Hi()) }
   256
View as plain text