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

#eql?, #offset, #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
34
35
 
# File 'lib/geometry/polygon.rb', line 30

def initialize(*args)
    super

    # Close the polygon if needed
    @edges.push Edge.new(@edges.last.last, @edges.first.first) unless @edges.empty? || (@edges.last.last == @edges.first.first)
end

Instance Method Details

#<=>(point) ⇒ Number

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

Parameters:

Returns:



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/geometry/polygon.rb', line 53

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:



39
40
41
 
# File 'lib/geometry/polygon.rb', line 39

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

#convex ⇒ Polygon

Returns the convex hull of the Geometry::Polygon

Returns:



172
173
174
 
# File 'lib/geometry/polygon.rb', line 172

def convex
    wrap
end

#offset_bisectors(length) ⇒ Array<Edge>

Vertex bisectors suitable for offsetting

Parameters:

  • length (Number) —

    The distance to offset by

Returns:

  • (Array<Edge>) —

    Edges representing the bisectors



269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
 
# File 'lib/geometry/polygon.rb', line 269

def offset_bisectors(length)
    vectors = edges.map {|e| e.direction }
    winding = 0
    sums = vectors.unshift(vectors.last).each_cons(2).map do |v1,v2|
	k = v1[0]*v2[1] - v1[1]*v2[0]	# z-component of v1 x v2
	winding += k
	if v1 == v2			# collinear, same direction?
	    Vector[-v1[1], v1[0]]
	elsif 0 == k			# collinear, reverse direction
	    nil
	else
	    by = (v2[1] - v1[1])/k
	    v = (0 == v1[1]) ? v2 : v1
	    Vector[(v[0]*by - 1)/v[1], by]
	end
    end

    # Check the polygon's orientation. If clockwise, negate length as a hack for injecting a -1 into the final result
    length = -length if winding >= 0
    vertices.zip(sums).map {|v,b| b ? Edge.new(v, v+(b * length)) : nil}
end

#outset(distance) ⇒ Polygon

Outset the receiver by the specified distance

Parameters:

  • distance (Number) —

    The distance to offset by

Returns:



207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
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
 
# File 'lib/geometry/polygon.rb', line 207

def outset(distance)
    bisectors = offset_bisectors(distance)
    offsets = (bisectors.each_cons(2).to_a << [bisectors.last, bisectors.first])

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

	# Skip zero-length edges
	{:edge => (offset.first == offset.last) ? nil : offset}
    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)
	    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

#reverse ⇒ Polygon

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

Returns:



44
45
46
 
# File 'lib/geometry/polygon.rb', line 44

def reverse
    self.class.new *(self.vertices.reverse)
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:



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
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
 
# File 'lib/geometry/polygon.rb', line 78

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:



179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 
# File 'lib/geometry/polygon.rb', line 179

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