1 /*
<lambda>null2  * Copyright 2024 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 package androidx.compose.ui.graphics
18 
19 import androidx.annotation.FloatRange
20 import androidx.compose.ui.geometry.Offset
21 import androidx.compose.ui.geometry.Rect
22 
23 /**
24  * Creates a new [PathHitTester] to query whether certain x/y coordinates lie inside a given [Path].
25  * A [PathHitTester] is optimized to perform multiple queries against a single path.
26  *
27  * The result of a query depends on the [fill type][Path.fillType] of the path.
28  *
29  * If the content of [path] changes, you must call [PathHitTester.updatePath] or create a new
30  * [PathHitTester] as [PathHitTester] will cache precomputed values to speed up queries.
31  *
32  * If [path] contains conic curves, they are converted to quadratic curves during the query process.
33  * The tolerance of that conversion is defined by [tolerance]. The tolerance should be appropriate
34  * to the coordinate systems used by the caller. For instance if the path is defined in pixels, 0.5
35  * (half a pixel) or 1.0 (a pixel) are appropriate tolerances. If the path is normalized and defined
36  * in the domain 0..1, the caller should choose a more appropriate tolerance close to or equal to
37  * one "query unit". The tolerance must be >= 0.
38  *
39  * @param path The [Path] to run queries against.
40  * @param tolerance When [path] contains conic curves, defines the maximum distance between the
41  *   original conic curve and its quadratic approximations. Set to 0.5 by default.
42  */
43 fun PathHitTester(path: Path, @FloatRange(from = 0.0) tolerance: Float = 0.5f) =
44     PathHitTester().apply { updatePath(path, tolerance) }
45 
46 private val EmptyPath = Path()
47 
48 /**
49  * A [PathHitTester] is used to query whether certain x/y coordinates lie inside a given [Path]. A
50  * [PathHitTester] is optimized to perform multiple queries against a single path.
51  */
52 class PathHitTester {
53     private var path = EmptyPath
54     private var tolerance = 0.5f
55 
56     // The bounds of [path], precomputed
57     private var bounds = Rect.Zero
58 
59     // When cached is set to true, the path's segments are cached inside an [IntervalTree]
60     // to speed up hit testing by performing computations against the segments that cross
61     // the y axis of the test position
62     private val intervals = IntervalTree<PathSegment>()
63 
64     // Scratch buffers used to avoid allocations when performing a hit test
65     private val curves = FloatArray(20)
66     private val roots = FloatArray(2)
67 
68     /**
69      * Sets the [Path] to run queries against.
70      *
71      * If [path] contains conic curves, they are converted to quadratic curves during the query
72      * process. This value defines the tolerance of that conversion.
73      *
74      * The tolerance should be appropriate to the coordinate systems used by the caller. For
75      * instance if the path is defined in pixels, 0.5 (half a pixel) or 1.0 (a pixel) are
76      * appropriate tolerances. If the path is normalized and defined in the domain 0..1, the caller
77      * should choose a more appropriate tolerance close to or equal to one "query unit". The
78      * tolerance must be >= 0.
79      *
80      * @param path The [Path] to run queries against.
81      * @param tolerance When [path] contains conic curves, defines the maximum distance between the
82      *   original conic curve and its quadratic approximations. Set to 0.5 by default.
83      */
updatePathnull84     fun updatePath(path: Path, @FloatRange(from = 0.0) tolerance: Float = 0.5f) {
85         this.path = path
86         this.tolerance = tolerance
87         bounds = path.getBounds()
88 
89         intervals.clear()
90         // TODO: We should handle conics ourselves, which would allow us to cheaply query
91         //       the number of segments in the path, which would in turn allow us to allocate
92         //       all of our data structures with an appropriate size to store everything in
93         //       a single array for instance
94         val iterator = path.iterator(PathIterator.ConicEvaluation.AsQuadratics, tolerance)
95         for (segment in iterator) {
96             when (segment.type) {
97                 PathSegment.Type.Line,
98                 PathSegment.Type.Quadratic,
99                 PathSegment.Type.Cubic -> {
100                     val (min, max) = computeVerticalBounds(segment, curves)
101                     intervals.addInterval(min, max, segment)
102                 }
103                 PathSegment.Type.Done -> break
104                 else -> {}
105             }
106         }
107     }
108 
109     /**
110      * Queries whether the specified [position] is inside this [Path]. The
111      * [path's fill type][Path.fillType] is taken into account to determine if the point lies inside
112      * this path or not.
113      *
114      * @param position The x/y coordinates of the point to test.
115      * @return True if [position] is inside this path, false otherwise.
116      */
containsnull117     operator fun contains(position: Offset): Boolean {
118         // TODO: If/when Compose supports inverse fill types, compute this value
119         val isInverse = false
120 
121         if (path.isEmpty || position !in bounds) {
122             return isInverse
123         }
124 
125         val (x, y) = position
126         val curvesArray = curves
127         val rootsArray = roots
128 
129         var winding = 0
130 
131         intervals.forEach(y) { interval ->
132             val segment = interval.data!!
133             val points = segment.points
134             when (segment.type) {
135                 PathSegment.Type.Line -> {
136                     winding += lineWinding(points, x, y)
137                 }
138                 PathSegment.Type.Quadratic -> {
139                     winding += quadraticWinding(points, x, y, curvesArray, rootsArray)
140                 }
141                 PathSegment.Type.Cubic -> {
142                     winding += cubicWinding(points, x, y, curvesArray, rootsArray)
143                 }
144                 PathSegment.Type.Done -> return@forEach
145                 else -> {} // Nothing to do for Move, Conic
146             }
147         }
148 
149         val isEvenOdd = path.fillType == PathFillType.EvenOdd
150         if (isEvenOdd) {
151             winding = winding and 1
152         }
153 
154         if (winding != 0) {
155             return !isInverse
156         }
157 
158         // TODO: handle cases where the point is on the curve
159 
160         return false
161     }
162 }
163