Skip to content

Instantly share code, notes, and snippets.

@cab404 cab404/vecs.kt
Last active Sep 27, 2018

Embed
What would you like to do?
Simple 2D utilities for Kotlin
import kotlin.math.*
data class Vec2(
val x: Float,
val y: Float
) {
constructor() : this(0f, 0f)
constructor(x: Number, y: Number) : this(x.toFloat(), y.toFloat())
companion object {
val ZERO = Vec2(0f, 0f)
/** Random normal vector */
val RANDOM
get() =
Vec2(1f, 0f)
.rotate(Math.random().toFloat() * 360)
}
operator fun times(scalar: Number) = Vec2(x * scalar.toFloat(), y * scalar.toFloat())
operator fun div(scalar: Number) = Vec2(x / scalar.toFloat(), y / scalar.toFloat())
operator fun plus(vec: Vec2) = Vec2(x + vec.x, y + vec.y)
operator fun minus(vec: Vec2) = Vec2(x - vec.x, y - vec.y)
operator fun unaryMinus() = this * -1f
infix fun dst2To(to: Vec2) = (x - to.x).pow(2) + (y - to.y).pow(2)
infix fun dstTo(to: Vec2) = sqrt(this dst2To to)
infix fun scl(by: Vec2) = Vec2(x * by.x, y * by.y)
fun norm() = (this dstTo ZERO).let { dst -> Vec2(x / dst, y / dst) }
fun rotate(degrees: Float): Vec2 {
val rad = (degrees / 180 * PI).toFloat()
return Vec2(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad))
}
}
typealias Line = Pair<Vec2, Vec2>
/**
* Returns array...
* * of zero points, if there is no intersection;
* * of one point, if there's one intersection;
* * of two points (segment), if it is continuous intersection;
* */
fun intersectLines(l1: Line, l2: Line): List<Vec2> {
// Checking if lines are in rectangular bounds of each other
infix fun Float.rng(that: Float) = if (that > this) this..that else that..this
if (l1.first.x !in l2.first.x rng l2.second.x && l2.first.x !in l1.first.x rng l1.second.x)
return emptyList()
if (l1.first.y !in l2.first.y rng l2.second.y && l2.first.y !in l1.first.y rng l1.second.y)
return emptyList()
/* to be invoked in case of collinearities */
fun solveCollinearLines(): List<Vec2> {
val l1a = listOf(l1.first, l1.second)
val l2a = listOf(l2.first, l2.second)
val centralSegment = (l1a + l2a)
.sortedBy { it.x }
.sortedBy { it.y }
.drop(1)
.take(2)
return centralSegment.distinct()
}
// start
val s = listOf(l1.first, l2.first)
// delta
val d = listOf(l1.second - l1.first, l2.second - l2.first)
val (s1, s2) = s
val (d1, d2) = d
// s1.x + (a * d1.x) = s2.x + (b * d2.x)
// s1.y + (a * d1.y) = s2.y + (b * d2.y)
// (a * d1.x) - (b * d2.x) = s2.x - s1.x
// (a * d1.y) - (b * d2.y) = s2.y - s1.y
val sx = s2.x - s1.x
val sy = s2.y - s1.y
// (a * d1.x) - (b * d2.x) = sx
// (a * d1.y) - (b * d2.y) = sy
// Checking for perpendiculars
listOf(l1, l2, l1).windowed(2).forEach { (a, b) ->
if (a.first.x == a.second.x && b.first.y == b.second.y) {
val collideX = listOf(b.first.x, b.second.x)
.sorted()
.let { (a, b) -> a..b }
.contains(a.first.x)
val collideY = listOf(a.first.y, a.second.y)
.sorted()
.let { (a, b) -> a..b }
.contains(b.first.y)
return if (collideX && collideY) listOf(Vec2(a.first.x, b.first.y))
else emptyList()
}
}
// Checking special cases of collinear and parallel lines
listOf(
listOf(d1.x, d2.x, sx),
listOf(d1.y, d2.y, sy)
).forEach {
if (it.take(2).all { it == 0f })
return if (it.last() == 0f)
// collinear, system can be described with one equation
solveCollinearLines()
else
// parallel, system can not be solved
emptyList()
}
val compX = listOf(d1.x, -d2.x)
val compY = listOf(d1.y, -d2.y)
val divisible = compX.zip(compY).indexOfFirst { it.first != 0f && it.second != 0f }
val solveFor = divisible.inc().rem(2)
// If system degenerates to two same variable equations
if (divisible == -1)
return if ((compX.all { it == 0f } && sx != 0f) || (compY.all { it == 0f } && sy != 0f))
// parallel, system can not be solved.
listOf()
else
// collinear, system can be described with one equation
solveCollinearLines()
val mul = compX[divisible] / compY[divisible]
val coef = compX[solveFor] - compY[solveFor] * mul
val sum = sx - sy * mul
if (coef == 0f)
return if (sum == 0f)
// final equation is a useless koala
solveCollinearLines()
else
// final equation is not solvable
listOf()
return listOf(s[solveFor] + d[solveFor] * (sum / coef))
}
typealias Poly = List<Vec2>
/**
* Finds longest clockwise path through given polygons
*
* @param checkForLoops Whether or not check for infinite loops, that might occur on non-clockwise polygons.
* */
fun union(p1: Poly, p2: Poly, checkForLoops: Boolean = true): Poly {
var (current, other) =
listOf(p1, p2)
.map { poly ->
val offset = poly.withIndex().minBy { it.value.y }!!.index
(poly.drop(offset) + poly.take(offset)).toList()
}
.sortedBy { it.first().y }
val startPoly = current
var cp = 0
val path = mutableListOf(startPoly[0])
val loopCheck = mutableSetOf<Pair<Int, Int>>()
fun swapPolys() {
other = current.also { current = other }
}
fun nextEdge() {
cp += 1; cp %= current.size
}
nextEdge()
fun Poly.edge(i: Int) = this[i] to this[(i + 1) % size]
while (cp != 0 || current != startPoly) {
path.add(current[cp])
val edge = current.edge(cp)
if (checkForLoops && !loopCheck.add(cp to (if (current == startPoly) 0 else 1)))
throw IllegalArgumentException("One of the polys is incorrectly oriented!")
for (op in 0 until other.size) {
val testEdge = other.edge(op)
val intersection = intersectLines(edge, testEdge)
if (intersection.isNotEmpty()) {
if (intersection.size == 1)
path.add(intersection[0])
path.add(testEdge.second)
swapPolys()
cp = op
break
}
}
nextEdge()
}
return path
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.