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 r1 16 17 import ( 18 "fmt" 19 "math" 20 ) 21 22 // Interval represents a closed interval on ℝ. 23 // Zero-length intervals (where Lo == Hi) represent single points. 24 // If Lo > Hi then the interval is empty. 25 type Interval struct { 26 Lo, Hi float64 27 } 28 29 // EmptyInterval returns an empty interval. 30 func EmptyInterval() Interval { return Interval{1, 0} } 31 32 // IntervalFromPoint returns an interval representing a single point. 33 func IntervalFromPoint(p float64) Interval { return Interval{p, p} } 34 35 // IsEmpty reports whether the interval is empty. 36 func (i Interval) IsEmpty() bool { return i.Lo > i.Hi } 37 38 // Equal returns true iff the interval contains the same points as oi. 39 func (i Interval) Equal(oi Interval) bool { 40 return i == oi || i.IsEmpty() && oi.IsEmpty() 41 } 42 43 // Center returns the midpoint of the interval. 44 // It is undefined for empty intervals. 45 func (i Interval) Center() float64 { return 0.5 * (i.Lo + i.Hi) } 46 47 // Length returns the length of the interval. 48 // The length of an empty interval is negative. 49 func (i Interval) Length() float64 { return i.Hi - i.Lo } 50 51 // Contains returns true iff the interval contains p. 52 func (i Interval) Contains(p float64) bool { return i.Lo <= p && p <= i.Hi } 53 54 // ContainsInterval returns true iff the interval contains oi. 55 func (i Interval) ContainsInterval(oi Interval) bool { 56 if oi.IsEmpty() { 57 return true 58 } 59 return i.Lo <= oi.Lo && oi.Hi <= i.Hi 60 } 61 62 // InteriorContains returns true iff the interval strictly contains p. 63 func (i Interval) InteriorContains(p float64) bool { 64 return i.Lo < p && p < i.Hi 65 } 66 67 // InteriorContainsInterval returns true iff the interval strictly contains oi. 68 func (i Interval) InteriorContainsInterval(oi Interval) bool { 69 if oi.IsEmpty() { 70 return true 71 } 72 return i.Lo < oi.Lo && oi.Hi < i.Hi 73 } 74 75 // Intersects returns true iff the interval contains any points in common with oi. 76 func (i Interval) Intersects(oi Interval) bool { 77 if i.Lo <= oi.Lo { 78 return oi.Lo <= i.Hi && oi.Lo <= oi.Hi // oi.Lo ∈ i and oi is not empty 79 } 80 return i.Lo <= oi.Hi && i.Lo <= i.Hi // i.Lo ∈ oi and i is not empty 81 } 82 83 // InteriorIntersects returns true iff the interior of the interval contains any points in common with oi, including the latter's boundary. 84 func (i Interval) InteriorIntersects(oi Interval) bool { 85 return oi.Lo < i.Hi && i.Lo < oi.Hi && i.Lo < i.Hi && oi.Lo <= oi.Hi 86 } 87 88 // Intersection returns the interval containing all points common to i and j. 89 func (i Interval) Intersection(j Interval) Interval { 90 // Empty intervals do not need to be special-cased. 91 return Interval{ 92 Lo: math.Max(i.Lo, j.Lo), 93 Hi: math.Min(i.Hi, j.Hi), 94 } 95 } 96 97 // AddPoint returns the interval expanded so that it contains the given point. 98 func (i Interval) AddPoint(p float64) Interval { 99 if i.IsEmpty() { 100 return Interval{p, p} 101 } 102 if p < i.Lo { 103 return Interval{p, i.Hi} 104 } 105 if p > i.Hi { 106 return Interval{i.Lo, p} 107 } 108 return i 109 } 110 111 // ClampPoint returns the closest point in the interval to the given point "p". 112 // The interval must be non-empty. 113 func (i Interval) ClampPoint(p float64) float64 { 114 return math.Max(i.Lo, math.Min(i.Hi, p)) 115 } 116 117 // Expanded returns an interval that has been expanded on each side by margin. 118 // If margin is negative, then the function shrinks the interval on 119 // each side by margin instead. The resulting interval may be empty. Any 120 // expansion of an empty interval remains empty. 121 func (i Interval) Expanded(margin float64) Interval { 122 if i.IsEmpty() { 123 return i 124 } 125 return Interval{i.Lo - margin, i.Hi + margin} 126 } 127 128 // Union returns the smallest interval that contains this interval and the given interval. 129 func (i Interval) Union(other Interval) Interval { 130 if i.IsEmpty() { 131 return other 132 } 133 if other.IsEmpty() { 134 return i 135 } 136 return Interval{math.Min(i.Lo, other.Lo), math.Max(i.Hi, other.Hi)} 137 } 138 139 func (i Interval) String() string { return fmt.Sprintf("[%.7f, %.7f]", i.Lo, i.Hi) } 140 141 const ( 142 // epsilon is a small number that represents a reasonable level of noise between two 143 // values that can be considered to be equal. 144 epsilon = 1e-15 145 // dblEpsilon is a smaller number for values that require more precision. 146 // This is the C++ DBL_EPSILON equivalent. 147 dblEpsilon = 2.220446049250313e-16 148 ) 149 150 // ApproxEqual reports whether the interval can be transformed into the 151 // given interval by moving each endpoint a small distance. 152 // The empty interval is considered to be positioned arbitrarily on the 153 // real line, so any interval with a small enough length will match 154 // the empty interval. 155 func (i Interval) ApproxEqual(other Interval) bool { 156 if i.IsEmpty() { 157 return other.Length() <= 2*epsilon 158 } 159 if other.IsEmpty() { 160 return i.Length() <= 2*epsilon 161 } 162 return math.Abs(other.Lo-i.Lo) <= epsilon && 163 math.Abs(other.Hi-i.Hi) <= epsilon 164 } 165 166 // DirectedHausdorffDistance returns the Hausdorff distance to the given interval. For two 167 // intervals x and y, this distance is defined as 168 // 169 // h(x, y) = max_{p in x} min_{q in y} d(p, q). 170 func (i Interval) DirectedHausdorffDistance(other Interval) float64 { 171 if i.IsEmpty() { 172 return 0 173 } 174 if other.IsEmpty() { 175 return math.Inf(1) 176 } 177 return math.Max(0, math.Max(i.Hi-other.Hi, other.Lo-i.Lo)) 178 } 179