Class: WindingPolygon::SweepLine
- Inherits:
-
Object
- Object
- WindingPolygon::SweepLine
- Defined in:
- lib/winding-polygon/sweep_line.rb
Instance Attribute Summary collapse
-
#polygon ⇒ Object
readonly
Returns the value of attribute polygon.
-
#tree ⇒ Object
readonly
Returns the value of attribute tree.
Instance Method Summary collapse
- #add(event) ⇒ Object
- #add_segment(seg) ⇒ Object
- #find(event) ⇒ Object
- #find_segment(seg) ⇒ Object
-
#initialize(polygon) ⇒ SweepLine
constructor
A new instance of SweepLine.
-
#intersect(s1, s2) ⇒ Object
test intersect of 2 segments and return: nil when none, point when intersecting.
- #remove(seg) ⇒ Object
- #swap(s1, s2) ⇒ Object
Constructor Details
Instance Attribute Details
#polygon ⇒ Object (readonly)
Returns the value of attribute polygon.
4 5 6 |
# File 'lib/winding-polygon/sweep_line.rb', line 4 def polygon @polygon end |
#tree ⇒ Object (readonly)
Returns the value of attribute tree.
3 4 5 |
# File 'lib/winding-polygon/sweep_line.rb', line 3 def tree @tree end |
Instance Method Details
#add(event) ⇒ Object
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# 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) ⇒ Object
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
# 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) ⇒ Object
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
# 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) ⇒ Object
94 95 96 97 98 99 100 101 102 103 |
# 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) ⇒ Object
test intersect of 2 segments and return: nil when none, point when intersecting
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 |
# 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) ⇒ Object
105 106 107 108 109 110 111 112 113 114 115 116 |
# 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) ⇒ Object
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
# 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 |