package coffee.liz.rookery.puzzle

import kotlin.math.abs
import kotlin.math.cos
import kotlin.math.sin
import kotlin.math.sqrt

data class V3(val x: Double, val y: Double, val z: Double) {
    operator fun plus(o: V3) = V3(x + o.x, y + o.y, z + o.z)
    operator fun minus(o: V3) = V3(x - o.x, y - o.y, z - o.z)
    operator fun times(k: Double) = V3(x * k, y * k, z * k)
    infix fun dot(o: V3) = x * o.x + y * o.y + z * o.z
    infix fun cross(o: V3) = V3(y * o.z - z * o.y, z * o.x - x * o.z, x * o.y - y * o.x)
    val length: Double get() = sqrt(this dot this)
    fun unit(): V3 = this * (1.0 / length)

    /** Rotate about unit axis [k] by [angle] radians, right-handed (counter-clockwise seen from +k). */
    fun rotate(k: V3, angle: Double): V3 {
        val c = cos(angle); val s = sin(angle)
        return this * c + (k cross this) * s + k * ((k dot this) * (1 - c))
    }

    companion object { val ZERO = V3(0.0, 0.0, 0.0) }
}

/** A convex planar polygon, vertices counter-clockwise seen from outside. */
class Polygon(val points: List<V3>) {
    val centroid: V3 = points.fold(V3.ZERO) { a, p -> a + p } * (1.0 / points.size)
    val normal: V3 get() = ((points[1] - points[0]) cross (points[2] - points[0])).unit()
    val area: Double get() {
        var acc = V3.ZERO
        for (i in points.indices) acc += points[i] cross points[(i + 1) % points.size]
        return acc.length / 2
    }

    /** Sutherland–Hodgman split by the plane `dot(p, n) = c`: (part above, part below), either may be null. */
    fun split(n: V3, c: Double, eps: Double = 1e-9): Pair<Polygon?, Polygon?> {
        val above = mutableListOf<V3>()
        val below = mutableListOf<V3>()
        for (i in points.indices) {
            val a = points[i]; val b = points[(i + 1) % points.size]
            val da = (a dot n) - c; val db = (b dot n) - c
            if (da >= -eps) above += a
            if (da <= eps) below += a
            if ((da > eps && db < -eps) || (da < -eps && db > eps)) {
                val p = a + (b - a) * (da / (da - db))
                above += p; below += p
            }
        }
        fun mk(ps: List<V3>) = if (ps.size >= 3) Polygon(ps).takeIf { it.area > 1e-7 } else null
        return mk(above) to mk(below)
    }

    fun map(f: (V3) -> V3) = Polygon(points.map(f))

    /** Shrink toward the centroid, for drawing stickers with plastic showing between them. */
    fun inset(k: Double) = map { centroid + (it - centroid) * k }
}

internal fun approxEq(a: V3, b: V3, eps: Double = 1e-6) = abs(a.x - b.x) < eps && abs(a.y - b.y) < eps && abs(a.z - b.z) < eps