1 /*
2 * Copyright 2022 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 @file:JvmName("Utils")
18
19 package androidx.graphics.shapes
20
21 import kotlin.jvm.JvmName
22 import kotlin.math.PI
23 import kotlin.math.abs
24 import kotlin.math.cos
25 import kotlin.math.sin
26 import kotlin.math.sqrt
27
28 /** This class has all internal methods, used by Polygon, Morph, etc. */
distancenull29 internal fun distance(x: Float, y: Float) = sqrt(x * x + y * y)
30
31 internal fun distanceSquared(x: Float, y: Float) = x * x + y * y
32
33 /** Returns unit vector representing the direction to this point from (0, 0) */
34 internal fun directionVector(x: Float, y: Float): Point {
35 val d = distance(x, y)
36 require(d > 0f) { "Required distance greater than zero" }
37 return Point(x / d, y / d)
38 }
39
directionVectornull40 internal fun directionVector(angleRadians: Float) = Point(cos(angleRadians), sin(angleRadians))
41
42 internal fun radialToCartesian(radius: Float, angleRadians: Float, center: Point = Zero) =
43 directionVector(angleRadians) * radius + center
44
45 /**
46 * These epsilon values are used internally to determine when two points are the same, within some
47 * reasonable roundoff error. The distance epsilon is smaller, with the intention that the roundoff
48 * should not be larger than a pixel on any reasonable sized display.
49 */
50 internal const val DistanceEpsilon = 1e-4f
51 internal const val AngleEpsilon = 1e-6f
52
53 /**
54 * This epsilon is based on the observation that people tend to see e.g. collinearity much more
55 * relaxed than what is mathematically correct. This effect is heightened on smaller displays. Use
56 * this epsilon for operations that allow higher tolerances.
57 */
58 internal const val RelaxedDistanceEpsilon = 5e-3f
59
60 internal fun Point.rotate90() = Point(-y, x)
61
62 internal val Zero = Point(0f, 0f)
63
64 internal val FloatPi = PI.toFloat()
65
66 internal val TwoPi: Float = 2 * PI.toFloat()
67
68 internal fun square(x: Float) = x * x
69
70 /** Linearly interpolate between [start] and [stop] with [fraction] fraction between them. */
71 internal fun interpolate(start: Float, stop: Float, fraction: Float): Float {
72 return (1 - fraction) * start + fraction * stop
73 }
74
75 /**
76 * Similar to num % mod, but ensures the result is always positive. For example: 4 % 3 =
77 * positiveModulo(4, 3) = 1, but: -4 % 3 = -1 positiveModulo(-4, 3) = 2
78 */
positiveModulonull79 internal fun positiveModulo(num: Float, mod: Float) = (num % mod + mod) % mod
80
81 /** Returns whether C is on the line defined by the two points AB */
82 internal fun collinearIsh(
83 aX: Float,
84 aY: Float,
85 bX: Float,
86 bY: Float,
87 cX: Float,
88 cY: Float,
89 tolerance: Float = DistanceEpsilon
90 ): Boolean {
91 // The dot product of a perpendicular angle is 0. By rotating one of the vectors,
92 // we save the calculations to convert the dot product to degrees afterwards.
93 val ab = Point(bX - aX, bY - aY).rotate90()
94 val ac = Point(cX - aX, cY - aY)
95 val dotProduct = abs(ab.dotProduct(ac))
96 val relativeTolerance = tolerance * ab.getDistance() * ac.getDistance()
97
98 return dotProduct < tolerance || dotProduct < relativeTolerance
99 }
100
101 /**
102 * Approximates whether corner at this vertex is concave or convex, based on the relationship of the
103 * prev->curr/curr->next vectors.
104 */
convexnull105 internal fun convex(previous: Point, current: Point, next: Point): Boolean {
106 // TODO: b/369320447 - This is a fast, but not reliable calculation.
107 return (current - previous).clockwise(next - current)
108 }
109
110 /*
111 * Does a ternary search in [v0..v1] to find the parameter that minimizes the given function.
112 * Stops when the search space size is reduced below the given tolerance.
113 *
114 * NTS: Does it make sense to split the function f in 2, one to generate a candidate, of a custom
115 * type T (i.e. (Float) -> T), and one to evaluate it ( (T) -> Float )?
116 */
findMinimumnull117 internal fun findMinimum(
118 v0: Float,
119 v1: Float,
120 tolerance: Float = 1e-3f,
121 f: FindMinimumFunction
122 ): Float {
123 var a = v0
124 var b = v1
125 while (b - a > tolerance) {
126 val c1 = (2 * a + b) / 3
127 val c2 = (2 * b + a) / 3
128 if (f.invoke(c1) < f.invoke(c2)) {
129 b = c2
130 } else {
131 a = c1
132 }
133 }
134 return (a + b) / 2
135 }
136
137 /** A functional interface for computing a Float value when finding the minimum at [findMinimum]. */
138 internal fun interface FindMinimumFunction {
invokenull139 fun invoke(value: Float): Float
140 }
141
142 internal const val DEBUG = false
143
144 internal inline fun debugLog(tag: String, messageFactory: () -> String) {
145 // TODO: Re-implement properly when the library goes KMP using expect/actual
146 if (DEBUG) {
147 println("$tag: ${messageFactory()}")
148 }
149 }
150