FeatureMapping.kt

/*
 * Copyright 2023 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package androidx.graphics.shapes

import androidx.core.graphics.div
import androidx.core.graphics.minus
import androidx.core.graphics.plus

/**
 * MeasuredFeatures contains a list of all features in a polygon along with the [0..1] progress
 * at that feature
 */
internal typealias MeasuredFeatures = List<Pair<Float, RoundedPolygon.Feature>>

/**
 * featureMapper creates a mapping between the "features" (rounded corners) of two shapes
 */
internal fun featureMapper(features1: MeasuredFeatures, features2: MeasuredFeatures): DoubleMapper {
    // We only use corners for this mapping.
    val filteredFeatures1 = features1.filter { it.second is RoundedPolygon.Corner }
    val filteredFeatures2 = features2.filter { it.second is RoundedPolygon.Corner }

    val (m1, m2) = if (filteredFeatures1.size > filteredFeatures2.size) {
        doMapping(filteredFeatures2, filteredFeatures1) to filteredFeatures2
    } else {
        filteredFeatures1 to doMapping(filteredFeatures1, filteredFeatures2)
    }
    val mm = m1.zip(m2).map { (f1, f2) -> f1.first to f2.first }

    debugLog(LOG_TAG) { mm.joinToString { "${it.first} -> ${it.second}" } }
    return DoubleMapper(*mm.toTypedArray()).also { dm ->
        debugLog(LOG_TAG) {
            val N = 10
            "Map: " +
                (0..N).joinToString { i -> "%.3f".format(dm.map(i.toFloat() / N)) } +
            "\nMb : " +
                (0..N).joinToString { i -> "%.3f".format(dm.mapBack(i.toFloat() / N)) }
        }
    }
}

/**
 * Returns distance along overall shape between two Features on the two different shapes.
 * This information is used to determine how to map features (and the curves that make up
 * those features).
 */
internal fun featureDistSquared(f1: RoundedPolygon.Feature, f2: RoundedPolygon.Feature): Float {
    // TODO: We might want to enable concave-convex matching in some situations. If so, the
    //  approach below will not work
    if (f1 is RoundedPolygon.Corner && f2 is RoundedPolygon.Corner && f1.convex != f2.convex) {
        // Simple hack to force all features to map only to features of the same concavity, by
        // returning an infinitely large distance in that case
        debugLog(LOG_TAG) { "*** Feature distance ∞ for convex-vs-concave corners" }
        return Float.MAX_VALUE
    }
    val (c1, c2) = listOf(f1, f2).map { f ->
        (f.cubics.first().p0 + f.cubics.last().p3) / 2f
    }
    val d = c1 - c2
    return d.x * d.x + d.y * d.y
}

/**
 * Returns a mapping of the features in f2 that best map to the features in f1. The result
 * will be a list of features in f2 that is the size of f1. This is done to figure out
 * what the best features are in f2 that map to the existing features in f1. For example, if
 * f1 has 3 features and f2 has 4, we want to know what the 3 features are in f2 that map to
 * the features in f1 (then we will create a placeholder feature in the smaller shape for
 * the morph).
 */
internal fun doMapping(f1: MeasuredFeatures, f2: MeasuredFeatures): MeasuredFeatures {
    // Pick the first mapping in a greedy way.
    val ix = f2.indices.minBy { featureDistSquared(f1[0].second, f2[it].second) }

    val m = f1.size
    val n = f2.size

    val ret = mutableListOf(f2[ix])
    var lastPicked = ix
    for (i in 1 until m) {
        // Check the indices we can pick, which one is better.
        // Leave enough items in f2 to pick matches for the items left in f1.
        val last = (ix - (m - i)).let { if (it > lastPicked) it else it + n }
        val best = (lastPicked + 1..last).minBy {
            featureDistSquared(f1[i].second, f2[it % n].second)
        }
        ret.add(f2[best % n])
        lastPicked = best
    }
    return ret
}

private val LOG_TAG = "FeatureMapping"