Class: Geometry::Polygon

Inherits:
Polyline show all
Defined in:
lib/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/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/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/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/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/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/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/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/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/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/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/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/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