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