1 // Copyright 2023 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 import ( 18 "math" 19 20 "github.com/golang/geo/s1" 21 ) 22 23 // A Snapper restricts the locations of the output vertices. For 24 // example, there are predefined snap functions that require vertices to be 25 // located at CellID centers or at E5/E6/E7 coordinates. The Snapper 26 // can also specify a minimum spacing between vertices (i.e. the snap radius). 27 // 28 // A Snapper defines the following methods: 29 // 30 // 1. The SnapPoint method, which snaps a point P to a nearby point (the 31 // 32 // candidate snap site). Any point may be returned, including P 33 // itself (the identity snap function). 34 // 35 // 2. SnapRadius, the maximum distance that vertices can move when 36 // 37 // snapped. The snapRadius must be at least as large as the maximum 38 // distance between P and SnapPoint(P) for any point P. 39 // 40 // 3. MaxEdgeDeviation, the maximum distance that edges can move when 41 // 42 // snapped. It is slightly larger than snapRadius because when a 43 // geodesic edge is snapped, the center of the edge moves further than 44 // its endpoints. This value is computed automatically by Builder. 45 // 46 // 4. MinVertexSeparation, the guaranteed minimum distance between 47 // 48 // vertices in the output. This is generally a fraction of 49 // snapRadius where the fraction depends on the snap function. 50 // 51 // 5. A MinEdgeVertexSeparation, the guaranteed minimum distance 52 // 53 // between edges and non-incident vertices in the output. This is 54 // generally a fraction of snapRadius where the fraction depends on 55 // the snap function. 56 // 57 // It is important to note that SnapPoint does not define the actual 58 // mapping from input vertices to output vertices, since the points it 59 // returns (the candidate snap sites) are further filtered to ensure that 60 // they are separated by at least the snap radius. For example, if you 61 // specify E7 coordinates (2cm resolution) and a snap radius of 10m, then a 62 // subset of points returned by SnapPoint will be chosen (the snap sites), 63 // and each input vertex will be mapped to the closest site. Therefore you 64 // cannot assume that P is necessarily snapped to SnapPoint(P). 65 // 66 // Builder makes the following guarantees (within a small error margin): 67 // 68 // 1. Every vertex is at a location returned by SnapPoint. 69 // 70 // 2. Vertices are within snapRadius of the corresponding input vertex. 71 // 72 // 3. Edges are within maxEdgeDeviation of the corresponding input edge 73 // 74 // (a distance slightly larger than snapRadius). 75 // 76 // 4. Vertices are separated by at least minVertexSeparation 77 // 78 // (a fraction of snapRadius that depends on the snap function). 79 // 80 // 5. Edges and non-incident vertices are separated by at least 81 // 82 // minEdgeVertexSeparation (a fraction of snapRadius). 83 // 84 // 6. Vertex and edge locations do not change unless one of the conditions 85 // 86 // above is not already met (idempotency / stability). 87 // 88 // 7. The topology of the input geometry is preserved (up to the creation 89 // 90 // of degeneracies). This means that there exists a continuous 91 // deformation from the input to the output such that no vertex 92 // crosses an edge. 93 type Snapper interface { 94 // SnapRadius reports the maximum distance that vertices can move when snapped. 95 // This requires that SnapRadius <= maxSnapRadius 96 SnapRadius() s1.Angle 97 98 // MaxEdgeDeviation returns the maximum distance that the center of an 99 // edge can move when snapped. This is slightly larger than SnapRadius 100 // because when a geodesic edge is snapped, the center of the edge moves 101 // further than its endpoints. 102 MaxEdgeDeviation() s1.Angle 103 104 // MinVertexSeparation returns the guaranteed minimum distance between 105 // vertices in the output. This is generally some fraction of SnapRadius. 106 MinVertexSeparation() s1.Angle 107 108 // MinEdgeVertexSeparation returns the guaranteed minimum spacing between 109 // edges and non-incident vertices in the output. This is generally some 110 // fraction of SnapRadius. 111 MinEdgeVertexSeparation() s1.Angle 112 113 // SnapPoint returns a candidate snap site for the given point. The final vertex 114 // locations are a subset of the snap sites returned by this function 115 // (spaced at least MinVertexSeparation apart). 116 // 117 // The only requirement is that SnapPoint(x) must return a point whose 118 // distance from x is no greater than SnapRadius. 119 SnapPoint(point Point) Point 120 } 121 122 // Ensure the various snapping function types satisfy the interface. 123 var ( 124 _ Snapper = IdentitySnapper{} 125 _ Snapper = CellIDSnapper{} 126 _ Snapper = IntLatLngSnapper{} 127 ) 128 129 // maxSnapRadius defines the maximum supported snap radius (equivalent to about 7800km). 130 // This value can't be larger than 85.7 degrees without changing the code 131 // related to minEdgeLengthToSplitChordAngle, and increasing it to 90 degrees 132 // or more would most likely require significant changes to the algorithm. 133 const maxSnapRadius = 70 * s1.Degree 134 135 // IdentitySnapper is a Snapper that snaps every vertex to itself. 136 // It should be used when vertices do not need to be snapped to a discrete set 137 // of locations (such as E7 lat/lngs), or when maximum accuracy is desired. 138 // 139 // If the snapRadius is zero, then all input vertices are preserved 140 // exactly. Otherwise, Builder merges nearby vertices to ensure that no 141 // vertex pair is closer than snapRadius. Furthermore, vertices are 142 // separated from non-incident edges by at least MinEdgeVertexSeparation, 143 // equal to (0.5 * snapRadius). For example, if the snapRadius is 1km, then 144 // vertices will be separated from non-incident edges by at least 500m. 145 type IdentitySnapper struct { 146 snapRadius s1.Angle 147 } 148 149 // NewIdentitySnapper returns an IdentitySnapper with the given snap radius. 150 func NewIdentitySnapper(snapRadius s1.Angle) IdentitySnapper { 151 return IdentitySnapper{ 152 snapRadius: snapRadius, 153 } 154 } 155 156 // SnapRadius returns this types snapping radius. 157 func (sf IdentitySnapper) SnapRadius() s1.Angle { 158 return sf.snapRadius 159 } 160 161 // MaxEdgeDeviation returns the maximum edge deviation this type supports. 162 func (sf IdentitySnapper) MaxEdgeDeviation() s1.Angle { 163 return maxEdgeDeviationRatio * sf.snapRadius 164 } 165 166 // MinVertexSeparation returns the minimum vertex separation for this snap type. 167 func (sf IdentitySnapper) MinVertexSeparation() s1.Angle { 168 return sf.snapRadius 169 } 170 171 // MinEdgeVertexSeparation returns the minimum edge vertex separation. 172 // For the identity snap function, edges are separated from all non-incident 173 // vertices by at least 0.5 * snapRadius. 174 func (sf IdentitySnapper) MinEdgeVertexSeparation() s1.Angle { 175 return 0.5 * sf.snapRadius 176 } 177 178 // SnapPoint snaps the given point to the appropriate level for this type. 179 func (sf IdentitySnapper) SnapPoint(point Point) Point { 180 return point 181 } 182 183 // CellIDSnapper is a type that snaps vertices to CellID centers. This can 184 // be useful if you want to encode your geometry compactly for example. You can 185 // snap to the centers of cells at any level. 186 // 187 // Every snap level has a corresponding minimum snap radius, which is simply 188 // the maximum distance that a vertex can move when snapped. It is 189 // approximately equal to half of the maximum diagonal length for cells at the 190 // chosen level. You can also set the snap radius to a larger value; for 191 // example, you could snap to the centers of leaf cells (1cm resolution) but 192 // set the snapRadius to 10m. This would result in significant extra 193 // simplification, without moving vertices unnecessarily (i.e., vertices that 194 // are at least 10m away from all other vertices will move by less than 1cm). 195 type CellIDSnapper struct { 196 level int 197 snapRadius s1.Angle 198 } 199 200 // NewCellIDSnapper returns a snap function with the default level set. 201 func NewCellIDSnapper() CellIDSnapper { 202 return CellIDSnapper{ 203 level: MaxLevel, 204 } 205 } 206 207 // CellIDSnapperForLevel returns a snap function at the given level. 208 func CellIDSnapperForLevel(level int) CellIDSnapper { 209 sf := CellIDSnapper{ 210 level: level, 211 } 212 sf.snapRadius = sf.minSnapRadiusForLevel(level) 213 return sf 214 } 215 216 // SnapRadius reports the maximum distance that vertices can move when snapped. 217 // This requires that SnapRadius <= maxSnapRadius 218 // Defines the snap radius to be used (see Builder). The snap radius 219 // must be at least the minimum value for the current level, but larger 220 // values can also be used (e.g., to simplify the geometry). 221 // 222 // This requires snapRadius >= MinSnapRadiusForLevel(level) 223 // and snapRadius <= maxSnapRadius 224 func (sf CellIDSnapper) SnapRadius() s1.Angle { 225 return sf.snapRadius 226 } 227 228 // minSnapRadiusForLevel returns the minimum allowable snap radius for the given level 229 // (approximately equal to half of the maximum cell diagonal length). 230 func (sf CellIDSnapper) minSnapRadiusForLevel(level int) s1.Angle { 231 // snapRadius needs to be an upper bound on the true distance that a 232 // point can move when snapped, taking into account numerical errors. 233 // 234 // The maximum error when converting from an Point to a CellID is 235 // MaxDiagMetric.Deriv * dblEpsilon. The maximum error when converting a 236 // CellID center back to a Point is 1.5 * dblEpsilon. These add up to 237 // just slightly less than 4 * dblEpsilon. 238 return s1.Angle(0.5*MaxDiagMetric.Value(level) + 4*dblEpsilon) 239 } 240 241 // levelForMaxSnapRadius reports the minimum Cell level (i.e., largest Cells) such 242 // that vertices will not move by more than snapRadius. This can be useful 243 // when choosing an appropriate level to snap to. The return value is 244 // always a valid level (out of range values are silently clamped). 245 // 246 // If you want to choose the snap level based on a distance, and then use 247 // the minimum possible snap radius for the chosen level, do this: 248 // 249 // sf := CellIDSnapperForLevel(f.levelForMaxSnapRadius(distance)); 250 func (sf CellIDSnapper) levelForMaxSnapRadius(snapRadius s1.Angle) int { 251 // When choosing a level, we need to acount for the error bound of 252 // 4 * dblEpsilon that is added by MinSnapRadiusForLevel. 253 return MaxDiagMetric.MinLevel(2 * (snapRadius.Radians() - 4*dblEpsilon)) 254 } 255 256 // MaxEdgeDeviation returns the maximum edge deviation this type supports. 257 func (sf CellIDSnapper) MaxEdgeDeviation() s1.Angle { 258 return maxEdgeDeviationRatio * sf.snapRadius 259 } 260 261 // MinVertexSeparation returns the guaranteed minimum distance between 262 // vertices in the output. This is generally some fraction of SnapRadius. 263 // For CellID snapping, the minimum separation between vertices depends on 264 // level and snapRadius. It can vary between 0.5 * snapRadius 265 // and snapRadius. 266 func (sf CellIDSnapper) MinVertexSeparation() s1.Angle { 267 // We have three different bounds for the minimum vertex separation: one is 268 // a constant bound, one is proportional to snapRadius, and one is equal to 269 // snapRadius minus a constant. These bounds give the best results for 270 // small, medium, and large snap radii respectively. We return the maximum 271 // of the three bounds. 272 // 273 // 1. Constant bound: Vertices are always separated by at least 274 // MinEdgeMetric.Value(level), the minimum edge length for the chosen snap level. 275 // 276 // 2. Proportional bound: It can be shown that in the plane, the worst-case 277 // configuration has a vertex separation of 2 / sqrt(13) * snapRadius. 278 // This is verified in the unit test, except that on the sphere the ratio 279 // is slightly smaller at cell level 2 (0.54849 vs. 0.55470). We reduce 280 // that value a bit more below to be conservative. 281 // 282 // 3. Best asymptotic bound: This bound bound is derived by observing we 283 // only select a new site when it is at least snapRadius away from all 284 // existing sites, and the site can move by at most 285 // 0.5 * MaxDiagMetric.Value(level) when snapped. 286 minEdge := s1.Angle(MinEdgeMetric.Value(sf.level)) 287 maxDiag := s1.Angle(MaxDiagMetric.Value(sf.level)) 288 return maxAngle(minEdge, 289 maxAngle(s1.Angle(2/math.Sqrt(13))*sf.snapRadius, sf.snapRadius-0.5*maxDiag)) 290 } 291 292 // MinEdgeVertexSeparation returns the guaranteed minimum spacing between 293 // edges and non-incident vertices in the output. 294 // For CellID snapping, the minimum separation between edges and 295 // non-incident vertices depends on level and snapRadius. It can 296 // be as low as 0.219 * snapRadius, but is typically 0.5 * snapRadius 297 // or more. 298 func (sf CellIDSnapper) MinEdgeVertexSeparation() s1.Angle { 299 // Similar to MinVertexSeparation, in this case we have four bounds: a 300 // constant bound that holds only at the minimum snap radius, a constant 301 // bound that holds for any snap radius, a bound that is proportional to 302 // snapRadius, and a bound that is equal to snapRadius minus a constant. 303 // 304 // 1. Constant bounds: 305 // (a) At the minimum snap radius for a given level, it can be shown that 306 // vertices are separated from edges by at least 0.5 * MinDiagMetric.Value(level) in 307 // the plane. The unit test verifies this, except that on the sphere the 308 // worst case is slightly better: 0.5652980068 * MinDiagMetric.Value(level). 309 // 310 // (b) Otherwise, for arbitrary snap radii the worst-case configuration 311 // in the plane has an edge-vertex separation of sqrt(3/19) * 312 // MinDiagMetric.Value(level), where sqrt(3/19) is about 0.3973597071. The unit 313 // test verifies that the bound is slighty better on the sphere: 314 // 0.3973595687 * MinDiagMetric.Value(level). 315 // 316 // 2. Proportional bound: In the plane, the worst-case configuration has an 317 // edge-vertex separation of 2 * sqrt(3/247) * snapRadius, which is 318 // about 0.2204155075. The unit test verifies this, except that on the 319 // sphere the bound is slightly worse for certain large Cells: the 320 // minimum ratio occurs at cell level 6, and is about 0.2196666953. 321 // 322 // 3. Best asymptotic bound: If snapRadius is large compared to the 323 // minimum snap radius, then the best bound is achieved by 3 sites on a 324 // circular arc of radius snapRadius, spaced MinVertexSeparation 325 // apart. An input edge passing just to one side of the center of the 326 // circle intersects the Voronoi regions of the two end sites but not the 327 // Voronoi region of the center site, and gives an edge separation of 328 // (MinVertexSeparation ** 2) / (2 * snapRadius). This bound 329 // approaches 0.5 * snapRadius for large snap radii, i.e. the minimum 330 // edge-vertex separation approaches half of the minimum vertex 331 // separation as the snap radius becomes large compared to the cell size. 332 minDiag := s1.Angle(MinDiagMetric.Value(sf.level)) 333 if sf.snapRadius == sf.minSnapRadiusForLevel(sf.level) { 334 // This bound only holds when the minimum snap radius is being used. 335 return 0.565 * minDiag // 0.500 in the plane 336 } 337 338 // Otherwise, these bounds hold for any snapRadius. 339 vertexSep := sf.MinVertexSeparation() 340 return maxAngle(s1.Angle(math.Sqrt(3.0/19.0))*minDiag, 341 maxAngle(s1.Angle(2*math.Sqrt(3.0/247.0))*sf.snapRadius, 342 0.5*(vertexSep/sf.snapRadius)*vertexSep)) 343 } 344 345 // SnapPoint returns a candidate snap site for the given point. 346 func (sf CellIDSnapper) SnapPoint(point Point) Point { 347 return CellFromPoint(point).id.Parent(sf.level).Point() 348 } 349 350 const ( 351 // The minum exponent supported for snapping. 352 minIntSnappingExponent = 0 353 // The maximum exponent supported for snapping. 354 maxIntSnappingExponent = 10 355 ) 356 357 // IntLatLngSnapper is a Snapper that snaps vertices to LatLngs in 358 // E5, E6, or E7 coordinates. These coordinates are expressed in degrees 359 // multiplied by a power of 10 and then rounded to the nearest integer. For 360 // example, in E6 coordinates the point (23.12345651, -45.65432149) would 361 // become (23123457, -45654321). 362 // 363 // Each exponent has a corresponding minimum snap radius, which is simply the 364 // maximum distance that a vertex can move when snapped. It is approximately 365 // equal to 1/sqrt(2) times the nominal point spacing; for example, for 366 // snapping to E7 the minimum snap radius is (1e-7 / sqrt(2)) degrees. 367 // You can also set the snap radius to any value larger than this; this can 368 // result in significant extra simplification (similar to using a larger 369 // exponent) but does not move vertices unnecessarily. 370 type IntLatLngSnapper struct { 371 exponent int 372 snapRadius s1.Angle 373 from, to s1.Angle 374 } 375 376 // NewIntLatLngSnapper returns a Snapper with the specified exponent. 377 func NewIntLatLngSnapper(exponent int) IntLatLngSnapper { 378 // Precompute the scale factors needed for snapping. Note that these 379 // calculations need to exactly match the ones in s1.Angle to ensure 380 // that the same Points are generated. 381 power := s1.Angle(math.Pow10(exponent)) 382 sf := IntLatLngSnapper{ 383 exponent: exponent, 384 from: power, 385 to: 1 / power, 386 } 387 sf.snapRadius = sf.minSnapRadiusForExponent(exponent) 388 return sf 389 } 390 391 // SnapRadius reports the snap radius to be used. The snap radius 392 // must be at least the minimum value for the current exponent, but larger 393 // values can also be used (e.g., to simplify the geometry). 394 // 395 // This requires snapRadius >= minSnapRadiusForExponent(sh.exponent) 396 // and snapRadius <= maxSnapRadius 397 func (sf IntLatLngSnapper) SnapRadius() s1.Angle { 398 return sf.snapRadius 399 } 400 401 // minSnapRadiusForExponent returns the minimum allowable snap radius for the given 402 // exponent (approximately equal to 10**(-exponent) / sqrt(2)) degrees). 403 func (sf IntLatLngSnapper) minSnapRadiusForExponent(exponent int) s1.Angle { 404 // snapRadius needs to be an upper bound on the true distance that a 405 // point can move when snapped, taking into account numerical errors. 406 // 407 // The maximum errors in latitude and longitude can be bounded as 408 // follows (as absolute errors in terms of dblEpsilon): 409 // 410 // Latitude Longitude 411 // Convert to LatLng: 1.000 1.000 412 // Convert to degrees: 1.032 2.063 413 // Scale by 10**exp: 0.786 1.571 414 // Round to integer: 0.5 * s1.Degrees(sf.to) 415 // Scale by 10**(-exp): 1.375 2.749 416 // Convert to radians: 1.252 1.503 417 // ------------------------------------------------------------ 418 // Total (except for rounding) 5.445 8.886 419 // 420 // The maximum error when converting the LatLng back to a Point is 421 // 422 // sqrt(2) * (maximum error in latitude or longitude) + 1.5 * dblEpsilon 423 // 424 // which works out to (9 * sqrt(2) + 1.5) * dblEpsilon radians. Finally 425 // we need to consider the effect of rounding to integer coordinates 426 // (much larger than the errors above), which can change the position by 427 // up to (sqrt(2) * 0.5 * sf.to) radians. 428 power := math.Pow10(exponent) 429 return (s1.Degree*s1.Angle((1/math.Sqrt2)/power) + s1.Angle((9*math.Sqrt2+1.5)*dblEpsilon)) 430 } 431 432 // exponentForMaxSnapRadius returns the minimum exponent such that vertices will 433 // not move by more than snapRadius. This can be useful when choosing an appropriate 434 // exponent for snapping. The return value is always a valid exponent (out of 435 // range values are silently clamped). 436 func (sf IntLatLngSnapper) exponentForMaxSnapRadius(snapRadius s1.Angle) int { 437 // When choosing an exponent, we need to acount for the error bound of 438 // (9 * sqrt(2) + 1.5) * dblEpsilon added by minSnapRadiusForExponent. 439 snapRadius -= (9*math.Sqrt2 + 1.5) * dblEpsilon 440 snapRadius = s1.Angle(math.Max(float64(snapRadius), 1e-30)) 441 exponent := math.Log10((1 / math.Sqrt2) / snapRadius.Degrees()) 442 443 // There can be small errors in the calculation above, so to ensure that 444 // this function is the inverse of minSnapRadiusForExponent we subtract a 445 // small error tolerance. 446 return maxInt(minIntSnappingExponent, 447 minInt(maxIntSnappingExponent, int(math.Ceil(exponent-2*dblEpsilon)))) 448 } 449 450 // MaxEdgeDeviation returns the maximum edge deviation this type supports. 451 func (sf IntLatLngSnapper) MaxEdgeDeviation() s1.Angle { 452 return maxEdgeDeviationRatio * sf.snapRadius 453 } 454 455 // MinVertexSeparation returns the guaranteed minimum distance between vertices 456 // in the output. For IntLatLng snapping, the minimum separation between vertices 457 // depends on exponent and snapRadius. 458 func (sf IntLatLngSnapper) MinVertexSeparation() s1.Angle { 459 // We have two bounds for the minimum vertex separation: one is proportional 460 // to snapRadius, and one is equal to snapRadius minus a constant. These 461 // bounds give the best results for small and large snap radii respectively. 462 // We return the maximum of the two bounds. 463 // 464 // 1. Proportional bound: It can be shown that in the plane, the worst-case 465 // configuration has a vertex separation of (sqrt(2) / 3) * snapRadius. 466 // This is verified in the unit test, except that on the sphere the ratio 467 // is slightly smaller (0.471337 vs. 0.471404). We reduce that value a 468 // bit more below to be conservative. 469 // 470 // 2. Best asymptotic bound: This bound bound is derived by observing we 471 // only select a new site when it is at least snapRadius away from all 472 // existing sites, and snapping a vertex can move it by up to 473 // ((1 / sqrt(2)) * sf.to) degrees. 474 return maxAngle((math.Sqrt2/3)*sf.snapRadius, 475 sf.snapRadius-s1.Degree*s1.Angle(1/math.Sqrt2)*sf.to) 476 } 477 478 // MinEdgeVertexSeparation returns the guaranteed minimum spacing between edges 479 // and non-incident vertices in the output. For IntLatLng snapping, the minimum 480 // separation between edges and non-incident vertices depends on level and 481 // snapRadius. It can be as low as 0.222 * snapRadius, but is typically 482 // 0.39 * snapRadius or more. 483 func (sf IntLatLngSnapper) MinEdgeVertexSeparation() s1.Angle { 484 // Similar to MinVertexSeparation, in this case we have three bounds: 485 // one is a constant bound, one is proportional to snapRadius, and one is 486 // equal to snapRadius minus a constant. 487 // 488 // 1. Constant bound: In the plane, the worst-case configuration has an 489 // edge-vertex separation of ((1 / sqrt(13)) * sf.to) degrees. 490 // The unit test verifies this, except that on the sphere the ratio is 491 // slightly lower when small exponents such as E1 are used 492 // (0.2772589 vs 0.2773501). 493 // 494 // 2. Proportional bound: In the plane, the worst-case configuration has an 495 // edge-vertex separation of (2 / 9) * snapRadius (0.222222222222). The 496 // unit test verifies this, except that on the sphere the bound can be 497 // slightly worse with large exponents (e.g., E9) due to small numerical 498 // errors (0.222222126756717). 499 // 500 // 3. Best asymptotic bound: If snapRadius is large compared to the 501 // minimum snap radius, then the best bound is achieved by 3 sites on a 502 // circular arc of radius snapRadius, spaced MinVertexSeparation 503 // apart (see CellIDSnapper.MinEdgeVertexSeparation). This 504 // bound approaches 0.5 * snapRadius as the snap radius becomes large 505 // relative to the grid spacing. 506 vertexSep := sf.MinVertexSeparation() 507 return maxAngle(s1.Angle(1/math.Sqrt(13))*s1.Degree*sf.to, 508 maxAngle((2.0/9.0)*sf.snapRadius, 0.5*(vertexSep/sf.snapRadius)*vertexSep)) 509 } 510 511 // SnapPoint returns a candidate snap site for the given point. 512 func (sf IntLatLngSnapper) SnapPoint(point Point) Point { 513 input := LatLngFromPoint(point) 514 lat := s1.Angle(roundAngle(input.Lat * sf.from)) 515 lng := s1.Angle(roundAngle(input.Lng * sf.from)) 516 return PointFromLatLng(LatLng{lat * sf.to, lng * sf.to}) 517 } 518