Module: WindingPolygon

Defined in:
lib/winding-polygon.rb,
lib/winding-polygon/point.rb,
lib/winding-polygon/vector.rb,
lib/winding-polygon/avltree.rb,
lib/winding-polygon/polygon.rb,
lib/winding-polygon/segment.rb,
lib/winding-polygon/version.rb,
lib/winding-polygon/sweep_line.rb,
lib/winding-polygon/event_queue.rb

Defined Under Namespace

Classes: AVLNode, AVLTree, EventQueue, Point, Polygon, Segment, SweepLine, Vector

Constant Summary collapse

VERSION = 
"0.0.14"

Class Method Summary collapse

Class Method Details

.decompose(input_polygon) ⇒ Object

Raises:

  • (Exception) 


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
 
# 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) ⇒ Object 



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# 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) ⇒ Object 



117
118
119
120
121
122
123
124
 
# 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) ⇒ Object 



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# 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