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