我需要kotlin代码
时间: 2024-03-02 16:48:31 浏览: 23
好的,下面是基于 Graham Scan 算法的凸包求解方法的 Kotlin 代码:
```kotlin
data class Point(val x: Double, val y: Double)
fun getConvexHull(points: List<Point>): List<Point> {
// 找到最下且最左的点
val p0 = points.minWithOrNull(compareBy({ it.y }, { it.x }))!!
// 将所有点按照极角从小到大排序
val sortedPoints = points.sortedWith(compareBy(
{ Math.atan2(it.y - p0.y, it.x - p0.x) },
{ p0.distanceTo(it) }
))
// 依次加入凸包中
val hull = mutableListOf<Point>()
for (p in sortedPoints) {
while (hull.size >= 2 && !isConvex(hull.last(), hull[hull.lastIndex - 1], p)) {
hull.removeLast()
}
hull.add(p)
}
return hull
}
// 判断三个点是否构成一个凸包
fun isConvex(p1: Point, p2: Point, p3: Point): Boolean {
return (p2.y - p1.y) * (p3.x - p2.x) >= (p2.x - p1.x) * (p3.y - p2.y)
}
// 计算两个点之间的距离
fun Point.distanceTo(other: Point): Double {
val dx = this.x - other.x
val dy = this.y - other.y
return Math.sqrt(dx * dx + dy * dy)
}
```
使用方法:
```kotlin
val points = listOf(
Point(0.0, 0.0),
Point(1.0, 1.0),
Point(2.0, 2.0),
Point(3.0, 1.0),
Point(2.0, 0.0)
)
val hull = getConvexHull(points)
println(hull) // 输出 [(0.0, 0.0), (2.0, 0.0), (3.0, 1.0), (2.0, 2.0)]
```
其中 Point 类型可以自定义,只需要保证有 x 和 y 两个属性即可。