module WindingPolygon
Constants
- VERSION
Public Class Methods
decompose(input_polygon)
click to toggle source
# File lib/winding-polygon.rb, line 12 def self.decompose(input_polygon) raise Exception.new("The input polygon is invalid") if input_polygon.nil? || input_polygon.vertices.nil? || input_polygon.vertices.size<4 || input_polygon.vertices.first != input_polygon.vertices.last intersection_points = input_polygon.get_intersection_points return [input_polygon.vertices] if intersection_points.nil? || intersection_points.size==0 input_polygon.simple_segments.sort_by!{|seg| [seg.left_point] } simple_polygons = Array.new while !input_polygon.simple_segments.nil? && input_polygon.simple_segments.size>=3 simple_polygon = get_one_simple_polygon(get_first_segment(input_polygon), input_polygon) simple_polygons << simple_polygon if !simple_polygon.nil? end simple_polygons #make sure they're real simple final_simple_polygons = Array.new simple_polygons.each do |polylgon| final_decompose(final_simple_polygons, polylgon) end final_simple_polygons end
final_decompose(final_simple_polygons, polygon)
click to toggle source
# File lib/winding-polygon.rb, line 38 def self.final_decompose(final_simple_polygons, polygon) first_duplicate = polygon.detect { |p| polygon.count(p)>1 && p!=polygon.first } if first_duplicate.nil? final_simple_polygons << polygon return end index1 = polygon.index(first_duplicate) index2 = polygon.rindex(first_duplicate) polygon1 = polygon[0..index1].concat(polygon[index2+1..polygon.length-1]) if !polygon1.detect { |p| polygon1.count(p)>1 && p!=polygon1.first }.nil? self.final_decompose(final_simple_polygons, polygon1) else final_simple_polygons << polygon1 end polygon2 = polygon[index1..index2] if !polygon2.detect { |p| polygon2.count(p)>1 && p!=polygon2.first }.nil? self.final_decompose(final_simple_polygons, polygon2) else final_simple_polygons << polygon2 end end
get_first_segment(input_polygon)
click to toggle source
# File lib/winding-polygon.rb, line 117 def self.get_first_segment(input_polygon) start_point = input_polygon.simple_segments[0].left_point first_segment_candidates = input_polygon.simple_segments.select { |seg| seg.left_point == start_point }.dup #puts "edg1:#{first_segment_candidates[0].edge}, edg2:#{first_segment_candidates[1].edge}" first_segment_candidates.sort! input_polygon.simple_segments.delete_if { |seg| seg.left_point==first_segment_candidates[0].left_point && seg.right_point==first_segment_candidates[0].right_point } first_segment_candidates[0] end
get_one_simple_polygon(first_segment, input_polygon)
click to toggle source
# File lib/winding-polygon.rb, line 64 def self.get_one_simple_polygon(first_segment, input_polygon) current_simple_polygon = Array.new current_simple_polygon_vertices = Array.new current_simple_polygon << first_segment current_simple_polygon_vertices << first_segment.left_point << first_segment.right_point current_point = first_segment.right_point while !input_polygon.simple_segments.nil? && input_polygon.simple_segments.size>=1 previous_edge = current_simple_polygon.last.edge next_segment_candidates = input_polygon.simple_segments.select { |seg| seg.edge!=previous_edge && (seg.left_point == current_point ||seg.right_point == current_point) }.dup return nil if next_segment_candidates.empty? if !next_segment_candidates.nil? && next_segment_candidates.size>=2 #determine previous segment vector if current_point == current_simple_polygon.last.left_point v0 = Vector.new(current_simple_polygon.last.right_point.x-current_point.x, current_simple_polygon.last.right_point.y-current_point.y) else v0 = Vector.new(current_simple_polygon.last.left_point.x-current_point.x, current_simple_polygon.last.left_point.y-current_point.y) end #determine next segment vector if current_point == next_segment_candidates[0].left_point v1 = Vector.new(next_segment_candidates[0].right_point.x-current_point.x, next_segment_candidates[0].right_point.y-current_point.y) else v1 = Vector.new(next_segment_candidates[0].left_point.x-current_point.x, next_segment_candidates[0].left_point.y-current_point.y) end if v1.cross_product(v0) > 0 current_simple_polygon << next_segment_candidates[0] else current_simple_polygon << next_segment_candidates[1] end else current_simple_polygon << next_segment_candidates[0] end if current_simple_polygon.last.left_point == current_point current_point = current_simple_polygon.last.right_point else current_point = current_simple_polygon.last.left_point end current_simple_polygon_vertices << current_point input_polygon.simple_segments.delete_if { |seg| seg.left_point==current_simple_polygon.last.left_point && seg.right_point==current_simple_polygon.last.right_point } return current_simple_polygon_vertices if current_simple_polygon.first.left_point == current_simple_polygon.last.left_point end current_simple_polygon_vertices end