class WindingPolygon::Polygon

Attributes

intersection_points[R]
segments[RW]
simple_segments[RW]
vertices[R]

Public Class Methods

new(points) click to toggle source
# File lib/winding-polygon/polygon.rb, line 8
def initialize(points)
  @vertices = points
  @intersection_points = Array.new

  @simple_segments = Array.new

  @segments = Array.new
  for i in 0..@vertices.length-2

    seg = Segment.new({:edge=>i})

    if @vertices[i]<@vertices[i+1]
      seg.left_point = @vertices[i]
      seg.right_point = @vertices[i+1]
    else
      seg.left_point = @vertices[i+1]
      seg.right_point = @vertices[i]
    end

    @segments << seg

  end

end

Public Instance Methods

==(other_polygon) click to toggle source
# File lib/winding-polygon/polygon.rb, line 159
def ==(other_polygon)
  for i in 0..@vertices.size-1
    return false if @vertices[i] != other_polygon.vertices[i]
  end
  return true
end
add_to_intersection_point_collection(point) click to toggle source
# File lib/winding-polygon/polygon.rb, line 119
def add_to_intersection_point_collection(point)
  @intersection_points << point if !point.nil? &&  !@intersection_points.any?{|p| p.compare(point)==0}
end
find_intersection_point_between_segments(s1,s2, event_queue, sweep_line) click to toggle source
# File lib/winding-polygon/polygon.rb, line 114
def find_intersection_point_between_segments(s1,s2, event_queue, sweep_line)
  point =sweep_line.intersect(s1, s2)
  event_queue.insert(point_hash_with_edge_info(point, s1, s2)) if !point.nil?  && !event_queue.exist(point) && !@intersection_points.any?{|p| p==point}
end
get_first_intersection_point_hash() click to toggle source
# File lib/winding-polygon/polygon.rb, line 123
def get_first_intersection_point_hash
  event_queue  = EventQueue.new(self)
  sweep_line   = SweepLine.new(self)

  # This loop processes all events in the sorted queue
  # Events are only left or right vertices
  e = event_queue.events.shift
  while !e.nil? do
    if e[:type] == 'left'
      s = sweep_line.add(e)

      point = sweep_line.intersect(s, s.above)
      return point_hash_with_edge_info(point, s, s.above) if !point.nil?

      point = sweep_line.intersect(s, s.below)
      return point_hash_with_edge_info(point, s, s.below) if !point.nil?
    else
      s = sweep_line.find(e)
      point = sweep_line.intersect(s.above, s.below)
      return point_hash_with_edge_info(point, s.above, s.below) if !point.nil?
      sweep_line.remove(s)
    end
    e = event_queue.events.shift
  end
  return nil
end
get_intersection_points() click to toggle source
# File lib/winding-polygon/polygon.rb, line 59
def get_intersection_points
  event_queue  = EventQueue.new(self)
  sweep_line   = SweepLine.new(self)

  # This loop processes all events in the sorted queue
  # Events are only left or right vertices
  e = event_queue.events.shift
  while !e.nil? do

    if e[:type] == 'left'
      s = sweep_line.add(e)
      find_intersection_point_between_segments(s,s.above, event_queue, sweep_line)
      find_intersection_point_between_segments(s,s.below, event_queue, sweep_line)
    end

    if e[:type] == 'right'
      s = sweep_line.find_segment(@segments[e[:edge]])
      point = sweep_line.intersect(s.above, s.below)
      event_queue.insert(point_hash_with_edge_info(point, s.above, s.below)) if !point.nil? && !event_queue.exist(point)  && !@intersection_points.any?{|p| p==point}
      sweep_line.remove(s)
      @simple_segments << s
    end

    if e[:type] == 'intersection_point'
      add_to_intersection_point_collection(e[:vertex])

      s1 = sweep_line.find_segment(@segments[e[:edge1]])
      sweep_line.remove(s1)
      s11 = s1.dup
      s11.right_point = e[:vertex]
      @simple_segments << s11


      s2 = sweep_line.find_segment(@segments[e[:edge2]])
      sweep_line.remove(s2)
      s22 = s2.dup
      s22.right_point = e[:vertex]
      @simple_segments << s22

      @segments[e[:edge1]].left_point=e[:vertex]
      s1 = sweep_line.add_segment(@segments[e[:edge1]])
      find_intersection_point_between_segments(s1,s1.below, event_queue, sweep_line)

      @segments[e[:edge2]].left_point=e[:vertex]
      s2 = sweep_line.add_segment(@segments[e[:edge2]])
      find_intersection_point_between_segments(s2,s2.above, event_queue, sweep_line)
    end

    e = event_queue.events.shift
  end

  return nil if intersection_points.size==0
  @intersection_points
end
is_simple() click to toggle source
# File lib/winding-polygon/polygon.rb, line 33
def is_simple
  event_queue  = EventQueue.new(self)
  sweep_line   = SweepLine.new(self)

  # This loop processes all events in the sorted queue
  # Events are only left or right vertices
  e = event_queue.events.shift
  while !e.nil? do

    if e[:type] == 'left'
      s = sweep_line.add(e)

      return false  if !sweep_line.intersect(s, s.above).nil?
      return false  if !sweep_line.intersect(s, s.below).nil?
    else
      s = sweep_line.find(e)
      return false if !sweep_line.intersect(s.above, s.below).nil?
      sweep_line.remove(s)
    end

    e = event_queue.events.shift
  end

  return true
end
point_hash_with_edge_info(point, s1, s2) click to toggle source
# File lib/winding-polygon/polygon.rb, line 150
def point_hash_with_edge_info(point, s1, s2)
  if s1.right_point.y<s2.right_point.y
    edges=[s1.edge, s2.edge]
  else
    edges=[s2.edge, s1.edge]
  end
  {:point => point, :edge1 => edges[0], :edge2 => edges[1]}
end