Untitled

import androidx.compose.foundation.Canvas
import androidx.compose.foundation.gestures.detectTapGestures
import androidx.compose.foundation.layout.fillMaxSize
import androidx.compose.runtime.mutableStateListOf
import androidx.compose.runtime.remember
import androidx.compose.ui.Modifier
import androidx.compose.ui.geometry.Offset
import androidx.compose.ui.graphics.Color
import androidx.compose.ui.graphics.Path
import androidx.compose.ui.graphics.drawscope.Stroke
import androidx.compose.ui.input.pointer.pointerInput
import androidx.compose.ui.window.singleWindowApplication
import kotlin.math.atan2

fun main() = singleWindowApplication {
    val points = remember { mutableStateListOf<Offset>() }

    Canvas(modifier = Modifier.fillMaxSize().pointerInput(Unit) {
        detectTapGestures(onTap = { pos ->
          if(!(pos in points))
            points.add(pos)
        })
    }) {
        val hull = grahamScan(points) //вершины выпуклой оболочки
        val path = Path().apply {//путь из линий соед вершины
            hull.forEachIndexed { index, point ->
                if (index == 0) {
                    moveTo(point.x, point.y)
                } else {
                    lineTo(point.x, point.y)
                }
            }
            close()
        }
        drawPath(
            path = path,
            color = Color.Red,
            style = Stroke(width = 5f)
        )
        points.forEach { point ->
            drawCircle(
                color = Color.DarkGray,
                radius = 10f,
                center = point
            )
        }
    }
}

fun grahamScan(points: List<Offset>): List<Offset> {
    val sortedPoints = points.sortedWith(compareBy({ -it.y }, { it.x }))
    val lowerHull = mutableListOf<Offset>()
    val upperHull = mutableListOf<Offset>()

    for (point in sortedPoints) {
        while (lowerHull.size >= 2 && crossProduct(lowerHull[lowerHull.size - 2], lowerHull[lowerHull.size - 1], point) < 0) {
            lowerHull.removeAt(lowerHull.size - 1)
        }
        lowerHull.add(point)
    }

    for (point in sortedPoints.reversed()) {
        while (upperHull.size >= 2 && crossProduct(upperHull[upperHull.size - 2], upperHull[upperHull.size - 1], point) < 0) {
            upperHull.removeAt(upperHull.size - 1)
        }
        upperHull.add(point)
    }

    return (lowerHull + upperHull).distinct()
}

fun crossProduct(o: Offset, a: Offset, b: Offset): Float {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
}