module WindingPolygon

# 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

# 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

# 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

# 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