class WindingPolygon::SweepLine

Attributes

polygon[R]
tree[R]

Public Class Methods

new(polygon) click to toggle source
# File lib/winding-polygon/sweep_line.rb, line 6
def initialize(polygon)
  @tree    = AVLTree.new
  @polygon = polygon
end

Public Instance Methods

add(event) click to toggle source
# File lib/winding-polygon/sweep_line.rb, line 11
def add(event)
  # build up segment data
  seg = Segment.new(event)
  p1 = @polygon.vertices[seg.edge]
  p2 = @polygon.vertices[seg.edge + 1]

  # if it is being added, then it must be a LEFT edge event
  # but need to determine which endpoint is the left one first

  if p1.compare(p2) < 0
    seg.left_point  = p1
    seg.right_point = p2
  else
    seg.left_point  = p2
    seg.right_point = p1
  end

  # Add node to tree and setup linkages to "above" and "below"
  # edges as per algorithm
  nd = @tree.insert(seg)

  nx = nd.next
  np = nd.prev

  if !nx.nil?
    seg.above = nx.value
    seg.above.below = seg
  end

  if !np.nil?
    seg.below = np.value
    seg.below.above = seg
  end
  return seg

end
add_segment(seg) click to toggle source
# File lib/winding-polygon/sweep_line.rb, line 48
def add_segment(seg)
  seg.below=seg.above=nil

  # Add node to tree and setup linkages to "above" and "below"
  # edges as per algorithm
  nd = @tree.insert(seg)

  nx = nd.next
  np = nd.prev

  if !nx.nil?
    seg.above = nx.value
    seg.above.below = seg
  end

  if !np.nil?
    seg.below = np.value
    seg.below.above = seg
  end
  return seg

end
find(event) click to toggle source
# File lib/winding-polygon/sweep_line.rb, line 71
def find(event)
  # need a segment to find it in the tree
  seg = Segment.new(event)
  p1 = @polygon.vertices[seg.edge]
  p2 = @polygon.vertices[seg.edge + 1]

  # if it is being added, then it must be a LEFT edge event
  # but need to determine which endpoint is the left one first
  if p1.compare(p2) < 0
    seg.left_point  = p1
    seg.right_point = p2
  else
    seg.left_point  = p2
    seg.right_point = p1
  end

  node = @tree.search(seg)

  return nil if node.nil?

  node.value
end
find_segment(seg) click to toggle source
# File lib/winding-polygon/sweep_line.rb, line 94
def find_segment(seg)
  node = @tree.search(seg)

   if node.nil?
     node =  @tree.scan(seg)
     return nil if node.nil?
   end

  node.value
end
intersect(s1,s2) click to toggle source

test intersect of 2 segments and return: nil when none, point when intersecting

# File lib/winding-polygon/sweep_line.rb, line 163
def intersect(s1,s2)
  # no intersect if either segment doesn't existend
  return nil if s1.nil? || s2.nil?

  # check for consecutive edges in polygon
  e1 = s1.edge
  e2 = s2.edge

  # no non-simple intersect since consecutive
  polygon_edges = @polygon.vertices.length-1
  return nil if (((e1+1)%polygon_edges === e2) || (e1 === (e2+1)%polygon_edges))


  #test for existence of an intersect point
  #s2 left point sign
  lsign = s2.left_point.is_left(s1.left_point, s1.right_point)
  #s2 right point sign
  rsign = s2.right_point.is_left(s1.left_point, s1.right_point)

  # s2 endpoints have same sign relative to s1  => on same side => no intersect is possible
  return nil if (lsign * rsign > 0)

  # s1 left point sign
  lsign = s1.left_point.is_left(s2.left_point, s2.right_point)
  #s1 right point sign
  rsign = s1.right_point.is_left(s2.left_point, s2.right_point)

  # s1 endpoints have same sign relative to s2 => on same side => no intersect is possible
  return nil  if (lsign * rsign > 0)

  #segments s1 and s2 straddle. Intersect exists.
  intersection_point = s1.intersection_point_with(s2)
  return nil if intersection_point.nil?
  intersection_point
end
remove(seg) click to toggle source
# File lib/winding-polygon/sweep_line.rb, line 105
def remove(seg)
  nd = @tree.search(seg)
  return if nd.nil?

  nx = nd.next
  nx.value.below = seg.below if !nx.nil?

  np = nd.prev
  np.value.above = seg.above if !np.nil?

  @tree.delete(seg)
end
swap(s1,s2) click to toggle source
# File lib/winding-polygon/sweep_line.rb, line 118
def swap(s1,s2)
  nd1 = @tree.search(s1)
  return if nd1.nil?

  nd2 = @tree.search(s2)
  return if nd2.nil?


  nx1 = nd1.next
  nx1.value.below = nd2.value if !nx1.nil?

  np1 = nd1.prev
  np1.value.above = nd2.value if !np1.nil?

  nx2 = nd2.next
  nx2.value.below = nd1.value if !nx2.nil?

  np2 = nd2.prev
  np2.value.above = nd1.value if !np2.nil?


  nd1.value = s2
  nd2.value = s1

  temp = s1
  s1=s2
  s2=temp



  temp_above = s1.above
  temp_below = s1.below

  s1.above = s2.above
  s1.below = s2.below

  s2.above = temp_above
  s2.below = temp_below


  [s1,s2]

end