Method: Geometry::Polygon#wrap

Defined in:
lib/geometry/polygon.rb

#wrap ⇒ Polygon

Returns the convex hull using the Gift Wrapping algorithm

This implementation was cobbled together from many sources, but mostly from this implementation of the {http://butunclebob.com/ArticleS.UncleBob.ConvexHullTiming Jarvis March}

Returns:



196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/geometry/polygon.rb', line 196

def wrap
    # Start with a Point that's guaranteed to be on the hull
    leftmost_point = vertices.min_by {|v| v.x}
    current_point = vertices.select {|v| v.x == leftmost_point.x}.min_by {|v| v.y}

    current_angle = 0.0
    hull_points = [current_point]
    while true
  min_angle = 4.0
  min_point = nil
  vertices.each do |v1|
      next if current_point.equal? v1
      angle = pseudo_angle_for_edge(current_point, v1)
      min_point, min_angle = v1, angle if (angle >= current_angle) && (angle <= min_angle)
  end
  current_angle = min_angle
  current_point = min_point
  break if current_point == hull_points.first
  hull_points << min_point
    end
    Polygon.new *hull_points
end