Add the following code to your project's shard.yml under:
dependencies
to use in production
- OR -
development_dependencies
to use in development
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.
require "convex_hull"
# List of points {x, y}
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},
]
graham_scan = ConvexHull::GrahamScan.new(points)
# => #<ConvexHull::GrahamScan:0x...
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)
# => #<ConvexHull::JarvisMarch:0x...
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
.
git checkout -b my-new-feature
)git commit -am 'Add some feature'
)git push origin my-new-feature
)