Skip to content

Instantly share code, notes, and snippets.

@dniHze

dniHze/test.kt

Created Jan 23, 2018
Embed
What would you like to do?
How to pack circles in rectange in Kotlin.
import java.util.*
import kotlin.math.*
data class Point(var x: Double, var y: Double) {
fun vect(p: Point) = Point(p.x - x, p.y - y)
fun norm() = sqrt(x.pow(2) + y.pow(2))
fun dist(p: Point) = vect(p).norm()
fun add(p: Point) = Point(x + p.x, y + p.y)
fun mult(a: Double) = Point(x * a, y * a)
}
data class Circle(var radius: Double, val center: Point) {
fun distance(c: Circle) = center.dist(c.center) - radius - c.radius
}
class Packer<out T : Popular>(
private val circles: List<T>,
private val ratio: Double
) {
private fun compute(surface: Double): List<DistributedCircle<T>> {
val boundingR = sqrt(surface) * 100
val w = sqrt(surface * ratio)
val h = w / ratio
fun inRect(radius: Double, center: Point): Boolean {
return when {
center.x - radius < -w / 2 -> false
center.x + radius > w / 2 -> false
center.y - radius < -h / 2 -> false
center.y + radius > h / 2 -> false
else -> true
}
}
fun boundingCircle(x0: Double, y0: Double, x1: Double, y1: Double): Circle {
val xm = abs((x1 - x0) * w)
val ym = abs((y1 - y0) * h)
val m = max(xm, ym)
val theta = asin(m / 4 / boundingR)
val r = boundingR * (cos(theta))
return Circle(boundingR, Point(r * (y0 - y1) / 2 + (x0 + x1) * w / 4,
r * (x1 - x0) / 2 + (y0 + y1) * h / 4))
}
fun corner(radius: Double, c1: Circle, c2: Circle): List<Circle> {
var u = c1.center.vect(c2.center)
val A = u.norm()
if (A == .0) {
return listOf()
}
u = u.mult(1 / A)
val B = c1.radius + radius
val C = c2.radius + radius
if (A > (B + C)) {
return listOf()
}
val x = (A + (B.pow(2) - C.pow(2)) / A) / 2
val y = sqrt(B.pow(2) - x.pow(2))
val base = c1.center.add(u.mult(x))
val results = mutableListOf<Circle>()
val p1 = Point(base.x - u.y * y, base.y + u.x * y)
val p2 = Point(base.x + u.y * y, base.y - u.x * y)
if (inRect(radius, p1)) results.add(Circle(radius, p1))
if (inRect(radius, p2)) results.add(Circle(radius, p2))
return results
}
val default = circles.first()
val placed = mutableListOf<DistributedCircle<T>>(
DistributedCircle(boundingCircle(1.0, 1.0, 1.0, -1.0), default),
DistributedCircle(boundingCircle(1.0, -1.0, -1.0, -1.0), default),
DistributedCircle(boundingCircle(1.0, -1.0, -1.0, 1.0), default),
DistributedCircle(boundingCircle(-1.0, 1.0, 1.0, 1.0), default)
)
val unplaced = circles.toMutableList()
while (unplaced.isNotEmpty()) {
val lambda = Array(unplaced.size, {
-1e10
})
val circle = Array(unplaced.size, {
Circle(.0, Point(.0, .0))
})
for (i in unplaced.indices) {
var lambdaMin = 1e10
for (j in placed.indices)
for (k in (j + 1) until (placed.size - 1)) {
val corners = corner(unplaced[i].getPopularityPercentage(), placed[j].circle, placed[k].circle)
for (c in corners.indices) {
var dMin = 1e10
var isBroken = false
for (l in placed.indices) {
if (l == j || l == k)
continue
val d = placed[l].circle.distance(corners[c])
if (d < 0) {
isBroken = true
break
}
if (d < dMin) {
dMin = d
}
}
if (isBroken) continue
if (dMin < lambdaMin) {
lambdaMin = dMin
lambda[i] = 1 - dMin / unplaced[i].getPopularityPercentage()
circle[i] = corners[c]
}
}
}
}
var lambdaMax = -1e10
var iMax = -1
for (i in unplaced.indices) {
if (lambda[i] > lambdaMax) {
lambdaMax = lambda[i]
iMax = i
}
}
if (iMax == -1) break
val value = unplaced[iMax]
unplaced.removeAt(iMax)
placed.add(DistributedCircle(circle[iMax], value))
}
return placed.drop(4)
}
private fun solve(): List<DistributedCircle<T>> {
var surface = .0
circles.forEach {
surface += PI * it.getPopularityPercentage().pow(2)
}
val limit = surface / 1000
var step = surface / 2
val result = mutableListOf<DistributedCircle<T>>()
while (step > limit) {
val placement = compute(surface)
if (placement.size != circles.size) {
surface += step
} else {
result.clear()
result.addAll(placement)
surface -= step
}
step /= 2
}
return result
}
fun pack(): List<DistributedCircle<T>> {
return solve()
}
}
interface Popular {
fun getPopularityPercentage(): Double // 0.0..100.0
}
data class DistributedCircle<out T : Popular> constructor(
val circle: Circle,
val data: T
)
class Distributor<T : Popular>(val height: Double, val width: Double) {
fun distibute(data: Array<T>): Array<DistributedCircle<T>> {
return distibute(data.toList())
}
fun distibute(data: Collection<T>): Array<DistributedCircle<T>> {
val ratio = width / height
val packer = Packer(data.toList(), ratio)
val packedCircles = packer.pack()
// get sizes and bounds.
val mappedCenters = packedCircles.map { it.circle }
val minX = mappedCenters.map { it.center.x - it.radius }.min() ?: wtf()
val maxX = mappedCenters.map { it.center.x + it.radius }.max() ?: wtf()
val minY = mappedCenters.map { it.center.y - it.radius }.min() ?: wtf()
val maxY = mappedCenters.map { it.center.y + it.radius }.max() ?: wtf()
val dx = abs(minX)
val dy = abs(minY)
val w = abs(maxX) + abs(minX)
val h = abs(maxY) + abs(minY)
val scaleX = width / w
val scaleY = height / h
val finalScale = min(scaleX, scaleY)
packedCircles.forEach {
it.circle.center.x += dx
it.circle.center.y += dy
it.circle.center.x *= finalScale
it.circle.center.y *= finalScale
it.circle.radius *= finalScale
}
return packedCircles.toTypedArray()
}
private fun <K> wtf(): K = throw IllegalArgumentException()
}
data class Tag(private var popularity: Double = -1.0) : Popular {
init {
if (popularity < 0) {
popularity = Random().nextDouble() * 100.0
}
}
override fun getPopularityPercentage() = popularity
}
fun main(args: Array<String>) {
val circles = 7
val data = List(circles, {
Tag()
})
data.forEach(::println)
println("---- ----")
val distributor = Distributor<Tag>(1920.0, 1080.0)
val distributedData = distributor.distibute(data).toList()
distributedData.forEach(::println)
println("---- ----")
distributedData.map { "(x - ${it.circle.center.x})^2 + (y - ${it.circle.center.y})^2 = ${it.circle.radius.pow(2)}" }.forEach(::println)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment