Convex Hull Algorithm Algorithm
The Convex Hull Algorithm refers to a group of computational geometry algorithms that generate the smallest convex polygon that contains all the points of a given set in a two-dimensional plane. The convex hull is akin to stretching a rubber band around the set of points, such that it outlines the outermost points, forming a convex shape. The algorithms used to find the convex hull may vary, but some well-known approaches include the Gift Wrapping Algorithm (Jarvis March), Graham's Scan, QuickHull, and Chan's Algorithm. These algorithms have diverse applications, including computer graphics, pattern recognition, image processing, and spatial data analysis.
The efficiency of each algorithm can differ depending on the specific problem and input size. Gift Wrapping Algorithm has a time complexity of O(nh), where n is the number of input points and h is the number of convex hull vertices. Graham's Scan has a time complexity of O(n log n) and is generally faster in practice. QuickHull, inspired by the QuickSort algorithm, has an average-case complexity of O(n log n) but can degrade to O(n^2) in the worst case. Chan's Algorithm, a hybrid of the previous two approaches, has the optimal time complexity of O(n log h). The algorithm choice depends on the problem's constraints and the desired trade-offs between computational speed and implementation complexity.
/*
* Copyright (c) 2017 Kotlin Algorithm Club
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
package com.algorithmexamples.geometry.convexhull
import com.algorithmexamples.geometry.Point
interface ConvexHullAlgorithm {
fun convexHull(points: Array<Point>): Collection<Point>
}
