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 const ( 18 // maxEdgeDeviationRatio is set so that MaxEdgeDeviation will be large enough 19 // compared to snapRadius such that edge splitting is rare. 20 // 21 // Using spherical trigonometry, if the endpoints of an edge of length L 22 // move by at most a distance R, the center of the edge moves by at most 23 // asin(sin(R) / cos(L / 2)). Thus the (MaxEdgeDeviation / SnapRadius) 24 // ratio increases with both the snap radius R and the edge length L. 25 // 26 // We arbitrarily limit the edge deviation to be at most 10% more than the 27 // snap radius. With the maximum allowed snap radius of 70 degrees, this 28 // means that edges up to 30.6 degrees long are never split. For smaller 29 // snap radii, edges up to 49 degrees long are never split. (Edges of any 30 // length are not split unless their endpoints move far enough so that the 31 // actual edge deviation exceeds the limit; in practice, splitting is rare 32 // even with long edges.) Note that it is always possible to split edges 33 // when MaxEdgeDeviation is exceeded. 34 maxEdgeDeviationRatio = 1.1 35 ) 36