Shard Detail

convex_hull v0.5.0

Crystal implementation of finding the convex hull of a finite set of points in the plane
crystal convex-hull convex-hull-algorithms jarvis-march graham-scan

Install & Use

Add the following code to your project's shard.yml under:

dependencies to use in production
- OR -
development_dependencies to use in development


convex_hull:
  github: geocrystal/convex_hull

Readme

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

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.

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