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:



200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
 
# File 'lib/geometry/polygon.rb', line 200

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