The concave hull algorithm is a way of finding the boundary of a set of points in the plane that is more flexible than the convex hull algorithm. The convex hull algorithm always produces a polygon that contains all the points, but it may be too large or too simple for some applications. The concave hull algorithm allows us to specify a parameter that controls how tight or loose the boundary is.
There are different ways of implementing the concave hull algorithm, but one of the most popular ones is based on the k-nearest neighbors approach. This algorithm was proposed by Duckham et al. (2008) 1 and it works as follows:
- Start with an arbitrary point from the input set and add it to the output list.
- Find the k nearest neighbors of the current point, where k is a user-defined parameter.
- Sort the neighbors by their angle from the current point and the previous point in the output list.
- Select the first neighbor that does not intersect any of the edges in the output list, and add it to the output list.
- Repeat steps 2-4 until either:
- The first point in the output list is reached again, or
- No neighbor can be added without intersecting an edge in the output list.
- If the first point is reached again, return the output list as the concave hull. Otherwise, increase k by one and start over.
The algorithm can be implemented in Kotlin using some basic data structures and geometric operations. Here is a possible code snippet:
// A data class to represent a point with x and y coordinates data class Point(val x: Double, val y: Double) // A function to compute the Euclidean distance between two points fun distance(p1: Point, p2: Point): Double { return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)) } // A function to compute the angle between three points fun angle(p1: Point, p2: Point, p3: Point): Double { val v1 = Point(p2.x - p1.x, p2.y - p1.y) val v2 = Point(p3.x - p2.x, p3.y - p2.y) val dot = v1.x * v2.x + v1.y * v2.y val det = v1.x * v2.y - v1.y * v2.x return Math.atan2(det, dot) } // A function to check if two line segments intersect fun intersect(p1: Point, p2: Point, q1: Point, q2: Point): Boolean { // Find the four orientations needed for general and special cases val o1 = orientation(p1, p2, q1) val o2 = orientation(p1, p2, q2) val o3 = orientation(q1, q2, p1) val o4 = orientation(q1, q2, p2) // General case if (o1 != o2 && o3 != o4) return true // Special cases // p1, p2 and q1 are colinear and q1 lies on segment p1p2 if (o1 == 0 && onSegment(p1, q1, p2)) return true // p1, p2 and q2 are colinear and q2 lies on segment p1p2 if (o2 == 0 && onSegment(p1, q2, p2)) return true // q1, q2 and p1 are colinear and p1 lies on segment q1q2 if (o3 == 0 && onSegment(q1, p1, q2)) return true // q1, q2 and p2 are colinear and p2 lies on segment q1q2 if (o4 == 0 && onSegment(q1, p2, q2)) return true // Doesn't fall in any of the above cases return false } // A function to find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are colinear // 1 --> Clockwise // 2 --> Counterclockwise fun orientation(p: Point, q: Point, r: Point): Int { // See https://www.geeksforgeeks.org/orientation-3-ordered-points/ // for details of below formula. val value = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y) if (value == 0.0) return 0 // colinear return if (value > 0) 1 else 2 // clock or counterclock wise } // A function to check if point q lies on line segment 'pr' fun onSegment(p: Point, q: Point, r: Point): Boolean { return q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) && q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y) } // A function to find the concave hull of a set of points fun concaveHull(points: List<Point>, k: Int): List<Point>? { // Check if the input is valid if (points.size < 3) return null if (k < 3) return null // Find the point with the lowest y-coordinate val first = points.minByOrNull { it.y } ?: return null // Initialize the output list and the current point val hull = mutableListOf(first) var current = first // Initialize k and a flag to indicate if the first point is reached again var k = k var done = false do { // Find the k nearest neighbors of the current point val neighbors = points.sortedBy { distance(it, current) }.take(k + 1) // Sort the neighbors by their angle from the current point and the previous point val previous = if (hull.size == 1) Point(current.x - 1, current.y) else hull[hull.size - 2] val sorted = neighbors.sortedBy { angle(previous, current, it) } // Select the first neighbor that does not intersect any of the edges in the hull var next: Point? = null for (p in sorted) { var valid = true for (i in 0 until hull.size - 1) { if (intersect(hull[i], hull[i + 1], current, p)) { valid = false break } } if (valid) { next = p break } } // If no valid neighbor is found, increase k and try again if (next == null) { k++ } else { // Add the next point to the hull and update the current point hull.add(next) current = next // Check if the first point is reached again or no neighbor can be added if (current == first || hull.size == points.size) { done = true } } } while (!done) // Return the hull as a list of points return hull }
I hope this blog post helps you understand how to implement the concave hull algorithm in Kotlin. Kotlin is a modern and concise programming language that is fully interoperable with Java and can run on multiple platforms234 If you want to learn more about Kotlin, you can check out some of these resources:
- The official Kotlin website: https://kotlinlang.org/
- The official Kotlin documentation: https://kotlinlang.org/docs/home.html
- The official Kotlin playground: https://play.kotlinlang.org/
- The official Kotlin blog: https://blog.jetbrains.com/kotlin/
- The official Kotlin YouTube channel: https://www.youtube.com/channel/UCP7uiEZIqci43m22KDl0sNw
Thank you for reading and happy coding! 😊
1: Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008). Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition, Vol.41(10), pp.3194-3206. https://doi.org/10.1016/j.patcog.2008.03.023
2: Kotlin Programming Language – GeeksforGeeks. https://www.geeksforgeeks.org/kotlin-programming-language/
3: Kotlin Programming Language. https://kotlinlang.org/
All-new Amazon Fire HD 10 tablet, built for relaxation, 10.1" vibrant Full HD screen, octa-core processor, 3 GB RAM, latest model (2023 release), 32 GB, Black
$139.99 (as of April 26, 2024 10:52 GMT -04:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
Amazon Fire 7 Kids tablet, ages 3-7. Top-selling 7" kids tablet on Amazon - 2022 | ad-free content with parental controls included, 10-hr battery, 16 GB, Blue
$109.99 (as of April 26, 2024 10:52 GMT -04:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
TP-Link AC1200 WiFi Router (Archer A54) - Dual Band Wireless Internet Router, 4 x 10/100 Mbps Fast Ethernet Ports, Supports Guest WiFi, Access Point Mode, IPv6 and Parental Controls
$31.49 (as of April 26, 2024 10:52 GMT -04:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
havit HV-F2056 15.6"-17" Laptop Cooler Cooling Pad - Slim Portable USB Powered (3 Fans), Black/Blue
$22.39 (as of April 26, 2024 10:52 GMT -04:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
TP-Link Deco AX3000 WiFi 6 Mesh System(Deco X55) - Covers up to 6500 Sq.Ft. , Replaces Wireless Router and Extender, 3 Gigabit ports per unit, supports Ethernet Backhaul (3-pack)
$169.99 (as of April 26, 2024 10:52 GMT -04:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
Author: John Rowan
I am a Senior Android Engineer and I love everything to do with computers. My specialty is Android programming but I actually love to code in any language specifically learning new things.Share this:
