ConvexHull

Crystal CI GitHub release License

Crystal implementation of finding the convex hull of a finite set of points in the plane.

Supported algorithms:

Installation

  1. Add the dependency to your shard.yml:

    dependencies:
  convex_hull:
    github: geocrystal/convex_hull

  2. Run shards install

Computing a Convex Hull

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.

convex hull

Instantiate algorithm

This library supports ConvexHull::GrahamScan and ConvexHull::JarvisMarch inherided from abstract class ConvexHull::Algorithm.

It accepts Array of one of these:

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),
# ...
# ]

Convex hull

Jarvis march

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}]

Graham scan

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.

Contributing

  1. Fork it (https://github.com/geocrystal/convex_hull/fork)
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create a new Pull Request

Contributors