Class: Geometry::Polygon

Inherits:
Polyline show all
Defined in:
lib/aurora-geometry/polygon.rb

Overview

A Polygon is a closed path comprised entirely of lines so straight they don’t even curve.

http://en.wikipedia.org/wiki/Polygon

The Polygon class is generally intended to represent Simple polygons, but there’s currently nothing that enforces simplicity.

Usage

Direct Known Subclasses

RegularPolygon

Instance Attribute Summary

Attributes inherited from Polyline

#edges, #vertices

Boolean operators collapse

Convex Hull collapse

Instance Method Summary collapse

Methods inherited from Polyline

#bisectors, #close!, #closed?, #eql?, #left_bisectors, #offset, #right_bisectors, #rightset

Constructor Details

#initialize(Edge, Edge, ...) ⇒ Polygon #initialize(Point, Point, ...) ⇒ Polygon

Construct a new Polygon from Points and/or Edges

The constructor will try to convert all of its arguments into Points and
 Edges. Then successive Points will be collpased into Edges. Successive
 Edges that share a common vertex will be added to the new Polygon. If
 there's a gap between Edges it will be automatically filled with a new
 Edge. The resulting Polygon will then be closed if it isn't already.

Overloads:

  • #initialize(Edge, Edge, ...) ⇒ Polygon
  • #initialize(Point, Point, ...) ⇒ Polygon 


30
31
32
33
 
# File 'lib/aurora-geometry/polygon.rb', line 30

def initialize(*args)
    super
    close!  # A Polygon is always closed
end

Instance Method Details

#<=>(point) ⇒ Number

Test a Geometry::Point for inclusion in the receiver using a simplified winding number algorithm

Parameters:

Returns:



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
# File 'lib/aurora-geometry/polygon.rb', line 70

def <=>(point)
    sum = edges.reduce(0) do |sum, e|
  direction = e.last.y <=> e.first.y
  # Ignore edges that don't cross the point's x coordinate
  next sum unless ((point.y <=> e.last.y) + (point.y <=> e.first.y)).abs <= 1

  if 0 == direction   # Special case horizontal edges
      return 0 if ((point.x <=> e.last.x) + (point.x <=> e.first.x)).abs <= 1
      next sum     # Doesn't intersect
  else
      is_left = e <=> point
      return 0 if 0 == is_left
      next sum unless is_left
      sum += 0 <=> (direction + is_left)
  end
    end
    (0 == sum) ? -1 : 1
end

#clockwise? ⇒ Boolean

Check the orientation of the Geometry::Polygon

Returns:



43
44
45
 
# File 'lib/aurora-geometry/polygon.rb', line 43

def clockwise?
    edges.map {|e| (e.last.x - e.first.x) * (e.last.y + e.first.y)}.reduce(:+) >= 0
end

#close ⇒ Polygon

This method returns the receiver because a Geometry::Polygon is always closed

Returns:



37
38
39
 
# File 'lib/aurora-geometry/polygon.rb', line 37

def close
    close!
end

#convex ⇒ Polygon

Returns the convex hull of the Geometry::Polygon

Returns:



189
190
191
 
# File 'lib/aurora-geometry/polygon.rb', line 189

def convex
    wrap
end

#outset(distance) ⇒ Polygon

Outset the receiver by the specified distance

Parameters:

  • distance (Number) —

    The distance to offset by

Returns:



224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
 
# File 'lib/aurora-geometry/polygon.rb', line 224

def outset(distance)
    bisector_edges = outset_bisectors(distance)
    bisector_pairs = bisector_edges.push(bisector_edges.first).each_cons(2)

    # Create the offset edges and then wrap them in Hashes so the edges
    #  can be altered while walking the array
    active_edges = edges.zip(bisector_pairs).map do |e,offset|
  offset_edge = Edge.new(e.first+offset.first.vector, e.last+offset.last.vector)

  # Skip zero-length edges
  {:edge => (offset_edge.first == offset_edge.last) ? nil : offset_edge}
    end

    # Walk the array and handle any intersections
    active_edges.each_with_index do |e, i|
  e1 = e[:edge]
  next unless e1 # Ignore deleted edges

  intersection, j = find_last_intersection(active_edges, i, e1)
  if intersection
      e2 = active_edges[j][:edge]
      wrap_around_is_shortest = ((i + active_edges.count - j) < (j-i))

      if intersection.is_a? Point
    if wrap_around_is_shortest
        active_edges[i][:edge] = Edge.new(intersection, e1.last)
        active_edges[j][:edge] = Edge.new(e2.first, intersection)
    else
        active_edges[i][:edge] = Edge.new(e1.first, intersection)
        active_edges[j][:edge] = Edge.new(intersection, e2.last)
    end
      else
    # Handle the collinear case
    active_edges[i][:edge] = Edge.new(e1.first, e2.last)
    active_edges[j].delete(:edge)
    wrap_around_is_shortest = false
      end

      # Delete everything between e1 and e2
      if wrap_around_is_shortest # Choose the shortest path
    for k in 0...i do
        active_edges[k].delete(:edge)
    end
    for k in j...active_edges.count do
        next if k==j    # Exclude e2
        active_edges[k].delete(:edge)
    end
      else
    for k in i...j do
        next if k==i    # Exclude e1 and e2
        active_edges[k].delete(:edge)
    end
      end

      redo    # Recheck the modified edges
  end
    end
    Polygon.new *(active_edges.map {|e| e[:edge]}.compact.map {|e| [e.first, e.last]}.flatten)
end

#outset_bisectors(length) ⇒ Array<Edge>

Vertex bisectors suitable for outsetting

Parameters:

  • length (Number) —

    The distance to offset by

Returns:

  • (Array<Edge>) —

    Edges representing the bisectors



287
288
289
 
# File 'lib/aurora-geometry/polygon.rb', line 287

def outset_bisectors(length)
    vertices.zip(spokes).map {|v,b| b ? Edge.new(v, v+(b * length)) : nil}
end

#reverse ⇒ Polygon

Returns A new Geometry::Polygon with orientation that’s the opposite of the receiver.

Returns:



48
49
50
 
# File 'lib/aurora-geometry/polygon.rb', line 48

def reverse
    self.class.new *(self.vertices.reverse)
end

#reverse! ⇒ Polygon

Reverse the receiver and return it

Returns:

  • (Polygon) —

    the reversed receiver



54
55
56
57
58
59
60
61
62
63
 
# File 'lib/aurora-geometry/polygon.rb', line 54

def reverse!
    super

    # Simply reversing the vertex array causes the reversed polygon to
    #  start at what had been the last vertex, instead of starting at
    #  the same vertex and just going the other direction.
    vertices.unshift vertices.pop

    self
end

#spokes ⇒ Array<Vector>

Generate the unit-length spokes for each vertex

Returns:

  • (Array<Vector>) —

    the unit Vectors representing the spoke of each vertex



293
294
295
 
# File 'lib/aurora-geometry/polygon.rb', line 293

def spokes
    clockwise? ? left_bisectors : right_bisectors
end

#union(other) ⇒ Polygon Also known as: +

Create a new Geometry::Polygon that’s the union of the receiver and a passed Geometry::Polygon

This is a simplified implementation of the alogrithm outlined in the
paper {http://gvu.gatech.edu/people/official/jarek/graphics/papers/04PolygonBooleansMargalit.pdf An algorithm for computing the union, intersection or difference of two polygons}.
In particular, this method assumes the receiver and passed {Polygon}s are "island" type and that the desired output is "regular", as those terms are described in the paper.

Parameters:

Returns:



95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/aurora-geometry/polygon.rb', line 95

def union(other)
    # Table 1: Both polygons are islands and the operation is union, so both must have the same orientation
    # Reverse the other polygon if the orientations are different
    other = other.reverse if self.clockwise? != other.clockwise?

    # Receiver's vertex ring
    ringA = VertexRing.new
    self.vertices.each {|v| ringA.push v, (other <=> v)}

    # The other vertex ring
    ringB = VertexRing.new
    other.vertices.each {|v| ringB.push v, (self <=> v)}

    # Find intersections
    offsetA = 0
    edgesB = other.edges.dup
    self.edges.each_with_index do |a, indexA|
  offsetB = 0
  ringB.edges_with_index do |b, indexB|
      intersection = a.intersection(b)
      if intersection === true
    if (a.first == b.first) and (a.last == b.last)      # Equal edges
    elsif (a.first == b.last) and (a.last == b.first)   # Ignore equal but opposite edges
    else
        if a.vector.normalize == b.vector.normalize # Same direction?
      offsetA += 1 if ringA.insert_boundary(indexA + 1 + offsetA, b.first)
      offsetB += 1 if ringB.insert_boundary(indexB + 1 + offsetB, a.last)
        else    # Opposite direction
      offsetA += 1 if ringA.insert_boundary(indexA + 1 + offsetA, b.last)
      offsetB += 1 if ringB.insert_boundary(indexB + 1 + offsetB, a.first)
        end
    end
      elsif intersection.is_a?(Point)
    offsetA += 1 if ringA.insert_boundary(indexA + 1 + offsetA, intersection)
    offsetB += 1 if ringB.insert_boundary(indexB + 1 + offsetB, intersection)
      end
  end
    end

    # Table 2: Both polygons are islands and the operation is union, so select outside from both polygons
    edgeFragments = []
    [[ringA, other], [ringB, self]].each do |ring, other_polygon|
  ring.edges do |v1,v2|
      if (v1[:type] == -1) or (v2[:type] == -1)
    edgeFragments.push :first => v1[:vertex], :last => v2[:vertex]
      elsif (v1[:type] == 0) and (v2[:type] == 0)
    if (other_polygon <=> Point[(v1[:vertex] + v2[:vertex])/2]) <= 0
        edgeFragments.push :first => v1[:vertex], :last => v2[:vertex]
    end
      end
  end
    end

    # Delete any duplicated edges. Array#uniq doesn't do the right thing, so using inject instead.
    edgeFragments = edgeFragments.inject([]) {|result,h| result << h unless result.include?(h); result}

    # Delete any equal-and-opposite edges
    edgeFragments = edgeFragments.reject {|f| edgeFragments.find {|f2| (f[:first] == f2[:last]) and (f[:last] == f2[:first])} }

    # Construct the output polygons
    output = edgeFragments.reduce([Array.new]) do |output, fragment|
  next output if fragment.empty?
  polygon = output.last
  polygon.push fragment[:first], fragment[:last] if polygon.empty?
  while 1 do
      adjacent_fragment = edgeFragments.find {|f| fragment[:last] == f[:first]}
      break unless adjacent_fragment

      polygon.push adjacent_fragment[:first], adjacent_fragment[:last]
      fragment = adjacent_fragment.dup
      adjacent_fragment.clear

      break if polygon.first == polygon.last # closed?
  end
  output << Array.new
    end

    # If everything worked properly there should be only one output Polygon
    output.reject! {|a| a.empty?}
    output = Polygon.new *(output[0])

    # Table 4: Both input polygons are "island" type and the operation
    #  is union, so the output polygon's orientation should be the same
    #  as the input polygon's orientation
    (self.clockwise? != output.clockwise?) ? output.reverse : output
end

#wrap ⇒ Polygon

Returns the convex hull using the Gift Wrapping algorithm

This implementation was cobbled together from many sources, but mostly from this implementation of the {http://butunclebob.com/ArticleS.UncleBob.ConvexHullTiming Jarvis March}

Returns:



196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/aurora-geometry/polygon.rb', line 196

def wrap
    # Start with a Point that's guaranteed to be on the hull
    leftmost_point = vertices.min_by {|v| v.x}
    current_point = vertices.select {|v| v.x == leftmost_point.x}.min_by {|v| v.y}

    current_angle = 0.0
    hull_points = [current_point]
    while true
  min_angle = 4.0
  min_point = nil
  vertices.each do |v1|
      next if current_point.equal? v1
      angle = pseudo_angle_for_edge(current_point, v1)
      min_point, min_angle = v1, angle if (angle >= current_angle) && (angle <= min_angle)
  end
  current_angle = min_angle
  current_point = min_point
  break if current_point == hull_points.first
  hull_points << min_point
    end
    Polygon.new *hull_points
end