Crystal implementation of finding the convex hull of a finite set of points in the plane.
Supported algorithms:
-
Add the dependency to your
shard.yml
:dependencies: convex_hull: github: geocrystal/convex_hull
-
Run
shards install
Given X, a set of points in 2-D, the convex hull is the minimum set of points that define a polygon containing all the points of X. If you imagine the points as pegs on a board, you can find the convex hull by surrounding the pegs by a loop of string and then tightening the string until there is no more slack.
The following is an example of a convex hull of 19 points.
This library supports ConvexHull::GrahamScan
and ConvexHull::JarvisMarch
inherided from abstract class ConvexHull::Algorithm
.
It accepts Array
of one of these:
Tuple(Number, Number)
ConvexHull::Point
- Sub-class of
ConvexHull::Point
And return Array
of ConvexHull::Point
.
require "convex_hull"
points = [
{-10, 3}, {-10, 4}, {-7, 8}, {-7, 2}, {-3, 4},
{-2, 2}, {7, 3}, {9, 5}, {9, -7}, {5, -10},
{7, -8}, {5, -4}, {5, -5}, {4, -6}, {2, -7},
{1, -8}, {-3, -4}, {-4, -6}, {-9, -5},
]
# or
#
# points = [
# ConvexHull::Point.new(-10, 3),
# ConvexHull::Point.new(-10, 4),
# ...
# ]
graham_scan = ConvexHull::GrahamScan.new(points)
graham_scan.map { |point| {point.x, point.y} }
# => [{-10, 4}, {-10, 3}, {-9, -5}, {5, -10}, {9, -7}, {9, 5}, {-7, 8}]
jarvis_march = ConvexHull::JarvisMarch.new(points)
jarvis_march.map { |point| {point.x, point.y} }
# => [{-10, 4}, {-10, 3}, {-9, -5}, {5, -10}, {9, -7}, {9, 5}, {-7, 8}]
The result is an ordered collection of objects of type ConvexHull::Point
.
- Fork it (https://github.com/geocrystal/convex_hull/fork)
- Create your feature branch (
git checkout -b my-new-feature
) - Commit your changes (
git commit -am 'Add some feature'
) - Push to the branch (
git push origin my-new-feature
) - Create a new Pull Request
- Anton Maminov - creator and maintainer