Class: WindingPolygon::Polygon

Inherits:
Object
  • Object
show all
Defined in:
lib/winding-polygon/polygon.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(points) ⇒ Polygon

Returns a new instance of Polygon.



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# 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

Instance Attribute Details

#intersection_points ⇒ Object (readonly)

Returns the value of attribute intersection_points.



4
5
6
 
# File 'lib/winding-polygon/polygon.rb', line 4

def intersection_points
  @intersection_points
end

#segments ⇒ Object

Returns the value of attribute segments.



5
6
7
 
# File 'lib/winding-polygon/polygon.rb', line 5

def segments
  @segments
end

#simple_segments ⇒ Object

Returns the value of attribute simple_segments.



6
7
8
 
# File 'lib/winding-polygon/polygon.rb', line 6

def simple_segments
  @simple_segments
end

#vertices ⇒ Object (readonly)

Returns the value of attribute vertices.



3
4
5
 
# File 'lib/winding-polygon/polygon.rb', line 3

def vertices
  @vertices
end

Instance Method Details

#==(other_polygon) ⇒ Object 



159
160
161
162
163
164
 
# 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) ⇒ Object 



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



114
115
116
117
 
# 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 ⇒ Object 



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



59
60
61
62
63
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
 
# 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 ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
# 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) ⇒ Object 



150
151
152
153
154
155
156
157
 
# 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