module Terraformer::ConvexHull

Constants

DEFAULT_IMPL

Attributes

impl[RW]

Public Class Methods

for(points) click to toggle source
# File lib/terraformer/convex_hull.rb, line 22
def for points
  hull = __send__ @impl || DEFAULT_IMPL, flatten_coordinates_from(points)
  if hull.length == 1
    Point.new hull[0]
  else
    Polygon.new hull
  end
end
test() click to toggle source
# File lib/terraformer/convex_hull.rb, line 10
def test
  require 'ruby-prof'
  wc = Terraformer.parse 'test/examples/waldocanyon.geojson'
  RubyProf.start
  wc.convex_hull
  result = RubyProf.stop
  printer = RubyProf::FlatPrinter.new(result)
  printer.print(STDOUT)
  # printer = RubyProf::GraphPrinter.new(result)
  # printer.print(STDOUT, {})
end

Private Class Methods

cross(o, a, b) click to toggle source

en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#Ruby

# File lib/terraformer/convex_hull.rb, line 71
def cross o, a, b
  (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
end
flatten_coordinates_from(points) click to toggle source
# File lib/terraformer/convex_hull.rb, line 33
def flatten_coordinates_from points
  cs = []
  Geometry.iter_coordinate points, :each do |c|
    cs << c
  end
  cs.sort!.uniq!
  cs
end
jarvis_march(points) click to toggle source
# File lib/terraformer/convex_hull.rb, line 58
def jarvis_march points
  return points if points.length < 3
  hull = [points.sort[0]]
  hull.each do |p|
    q = next_point points, p
    hull << q if q != hull[0]
  end
  hull << hull[0]
  hull
end
monotone(points) click to toggle source
# File lib/terraformer/convex_hull.rb, line 75
def monotone points
  return points if points.length < 3
  lower = Array.new
  points.each{|p|
    while lower.length > 1 and cross(lower[-2], lower[-1], p) <= 0 do lower.pop end
    lower.push(p)
  }
  upper = Array.new
  points.reverse_each{|p|
    while upper.length > 1 and cross(upper[-2], upper[-1], p) <= 0 do upper.pop end
    upper.push(p)
  }
  hull = lower[0...-1] + upper[0...-1]
  hull << hull[0]
end
next_point(points, p) click to toggle source
# File lib/terraformer/convex_hull.rb, line 48
def next_point points, p
  q = p
  points.each do |r|
    t = turn p, q, r
    q = r if t == BigMath::N_ONE or t == BigMath::ZERO &&
      p.squared_euclidean_distance_to(r) > p.squared_euclidean_distance_to(q)
  end
  q
end
turn(p, q, r) click to toggle source

tixxit.wordpress.com/2009/12/09/jarvis-march/

# File lib/terraformer/convex_hull.rb, line 44
def turn p, q, r
  ((q[0] - p[0]) * (r[1] - p[1]) - (r[0] - p[0]) * (q[1] - p[1])) <=> BigMath::ZERO
end