1 // Copyright 2015 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 s2 16 17 // This file implements functions for various S2 measurements. 18 19 import "math" 20 21 // A Metric is a measure for cells. It is used to describe the shape and size 22 // of cells. They are useful for deciding which cell level to use in order to 23 // satisfy a given condition (e.g. that cell vertices must be no further than 24 // "x" apart). You can use the Value(level) method to compute the corresponding 25 // length or area on the unit sphere for cells at a given level. The minimum 26 // and maximum bounds are valid for cells at all levels, but they may be 27 // somewhat conservative for very large cells (e.g. face cells). 28 type Metric struct { 29 // Dim is either 1 or 2, for a 1D or 2D metric respectively. 30 Dim int 31 // Deriv is the scaling factor for the metric. 32 Deriv float64 33 } 34 35 // Defined metrics. 36 // Of the projection methods defined in C++, Go only supports the quadratic projection. 37 38 // Each cell is bounded by four planes passing through its four edges and 39 // the center of the sphere. These metrics relate to the angle between each 40 // pair of opposite bounding planes, or equivalently, between the planes 41 // corresponding to two different s-values or two different t-values. 42 var ( 43 MinAngleSpanMetric = Metric{1, 4.0 / 3} 44 AvgAngleSpanMetric = Metric{1, math.Pi / 2} 45 MaxAngleSpanMetric = Metric{1, 1.704897179199218452} 46 ) 47 48 // The width of geometric figure is defined as the distance between two 49 // parallel bounding lines in a given direction. For cells, the minimum 50 // width is always attained between two opposite edges, and the maximum 51 // width is attained between two opposite vertices. However, for our 52 // purposes we redefine the width of a cell as the perpendicular distance 53 // between a pair of opposite edges. A cell therefore has two widths, one 54 // in each direction. The minimum width according to this definition agrees 55 // with the classic geometric one, but the maximum width is different. (The 56 // maximum geometric width corresponds to MaxDiag defined below.) 57 // 58 // The average width in both directions for all cells at level k is approximately 59 // AvgWidthMetric.Value(k). 60 // 61 // The width is useful for bounding the minimum or maximum distance from a 62 // point on one edge of a cell to the closest point on the opposite edge. 63 // For example, this is useful when growing regions by a fixed distance. 64 var ( 65 MinWidthMetric = Metric{1, 2 * math.Sqrt2 / 3} 66 AvgWidthMetric = Metric{1, 1.434523672886099389} 67 MaxWidthMetric = Metric{1, MaxAngleSpanMetric.Deriv} 68 ) 69 70 // The edge length metrics can be used to bound the minimum, maximum, 71 // or average distance from the center of one cell to the center of one of 72 // its edge neighbors. In particular, it can be used to bound the distance 73 // between adjacent cell centers along the space-filling Hilbert curve for 74 // cells at any given level. 75 var ( 76 MinEdgeMetric = Metric{1, 2 * math.Sqrt2 / 3} 77 AvgEdgeMetric = Metric{1, 1.459213746386106062} 78 MaxEdgeMetric = Metric{1, MaxAngleSpanMetric.Deriv} 79 80 // MaxEdgeAspect is the maximum edge aspect ratio over all cells at any level, 81 // where the edge aspect ratio of a cell is defined as the ratio of its longest 82 // edge length to its shortest edge length. 83 MaxEdgeAspect = 1.442615274452682920 84 85 MinAreaMetric = Metric{2, 8 * math.Sqrt2 / 9} 86 AvgAreaMetric = Metric{2, 4 * math.Pi / 6} 87 MaxAreaMetric = Metric{2, 2.635799256963161491} 88 ) 89 90 // The maximum diagonal is also the maximum diameter of any cell, 91 // and also the maximum geometric width (see the comment for widths). For 92 // example, the distance from an arbitrary point to the closest cell center 93 // at a given level is at most half the maximum diagonal length. 94 var ( 95 MinDiagMetric = Metric{1, 8 * math.Sqrt2 / 9} 96 AvgDiagMetric = Metric{1, 2.060422738998471683} 97 MaxDiagMetric = Metric{1, 2.438654594434021032} 98 99 // MaxDiagAspect is the maximum diagonal aspect ratio over all cells at any 100 // level, where the diagonal aspect ratio of a cell is defined as the ratio 101 // of its longest diagonal length to its shortest diagonal length. 102 MaxDiagAspect = math.Sqrt(3) 103 ) 104 105 // Value returns the value of the metric at the given level. 106 func (m Metric) Value(level int) float64 { 107 return math.Ldexp(m.Deriv, -m.Dim*level) 108 } 109 110 // MinLevel returns the minimum level such that the metric is at most 111 // the given value, or MaxLevel (30) if there is no such level. 112 // 113 // For example, MinLevel(0.1) returns the minimum level such that all cell diagonal 114 // lengths are 0.1 or smaller. The returned value is always a valid level. 115 // 116 // In C++, this is called GetLevelForMaxValue. 117 func (m Metric) MinLevel(val float64) int { 118 if val < 0 { 119 return MaxLevel 120 } 121 122 level := -(math.Ilogb(val/m.Deriv) >> uint(m.Dim-1)) 123 if level > MaxLevel { 124 level = MaxLevel 125 } 126 if level < 0 { 127 level = 0 128 } 129 return level 130 } 131 132 // MaxLevel returns the maximum level such that the metric is at least 133 // the given value, or zero if there is no such level. 134 // 135 // For example, MaxLevel(0.1) returns the maximum level such that all cells have a 136 // minimum width of 0.1 or larger. The returned value is always a valid level. 137 // 138 // In C++, this is called GetLevelForMinValue. 139 func (m Metric) MaxLevel(val float64) int { 140 if val <= 0 { 141 return MaxLevel 142 } 143 144 level := math.Ilogb(m.Deriv/val) >> uint(m.Dim-1) 145 if level > MaxLevel { 146 level = MaxLevel 147 } 148 if level < 0 { 149 level = 0 150 } 151 return level 152 } 153 154 // ClosestLevel returns the level at which the metric has approximately the given 155 // value. The return value is always a valid level. For example, 156 // AvgEdgeMetric.ClosestLevel(0.1) returns the level at which the average cell edge 157 // length is approximately 0.1. 158 func (m Metric) ClosestLevel(val float64) int { 159 x := math.Sqrt2 160 if m.Dim == 2 { 161 x = 2 162 } 163 return m.MinLevel(x * val) 164 } 165