1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
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
|
