Class: EasyGeometry::D2::Polygon

Inherits:
Object
  • Object
show all
Defined in:
lib/easy_geometry/d2/polygon.rb

Overview

Must be at least 3 points

Direct Known Subclasses

Triangle

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ Polygon

Returns a new instance of Polygon.



18
19
20
21
22
 
# File 'lib/easy_geometry/d2/polygon.rb', line 18

def initialize(*args)
  @vertices = preprocessing_args(args)
  remove_consecutive_duplicates
  remove_collinear_points
end

Instance Attribute Details

#vertices ⇒ Object (readonly)

Returns the value of attribute vertices.



16
17
18
 
# File 'lib/easy_geometry/d2/polygon.rb', line 16

def vertices
  @vertices
end

Class Method Details

.is_right?(a, b, c) ⇒ Boolean

Return True/False for cw/ccw orientation.

Parameters:

a, b, c - EasyGeometry::D2::Point or Array of Numeric(coordinates)

Returns:

  • (Boolean)

Raises:

  • (TypeError) 


29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/easy_geometry/d2/polygon.rb', line 29

def self.is_right?(a, b, c)
  a = Point.new(a[0], a[1]) if a.is_a?(Array)
  raise TypeError, 'Must pass only Point objects' unless a.is_a?(Point)

  b = Point.new(b[0], b[1]) if b.is_a?(Array)
  raise TypeError, 'Must pass only Point objects' unless b.is_a?(Point)

  c = Point.new(c[0], c[1]) if c.is_a?(Array)
  raise TypeError, 'Must pass only Point objects' unless c.is_a?(Point)

  ba = b - a
  ca = c - a
  t_area = ba.x * ca.y - ca.x * ba.y

  t_area <= 0
end

Instance Method Details

#==(other) ⇒ Object

Returns True if self and other are the same mathematical entities



47
48
49
50
 
# File 'lib/easy_geometry/d2/polygon.rb', line 47

def ==(other)
  return false unless other.is_a?(Polygon)
  self.hashable_content == other.hashable_content
end

#area ⇒ Object

The area of the polygon. The area calculation can be positive or negative based on the orientation of the points. If any side of the polygon crosses any other side, there will be areas having opposite signs.



56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/easy_geometry/d2/polygon.rb', line 56

def area
  return @area if defined?(@area)

  sum = 0.0
  (0...vertices.length).each do |i|
    prev = vertices[i - 1]
    curr = vertices[i]

    sum += ((prev.x * curr.y) - (prev.y * curr.x))
  end

  @area = sum / 2
  @area
end

#bounds ⇒ Object

Return an array (xmin, ymin, xmax, ymax) representing the bounding rectangle for the geometric figure.

Returns:

Array of Numeric



128
129
130
131
132
133
134
135
136
 
# File 'lib/easy_geometry/d2/polygon.rb', line 128

def bounds
  return @bounds if defined?(@bounds)

  xs = vertices.map(&:x)
  ys = vertices.map(&:y)
  @bounds = [xs.min, ys.min, xs.max, ys.max]

  @bounds
end

#centroid ⇒ Object

The centroid of the polygon.

Returns

Point



88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/easy_geometry/d2/polygon.rb', line 88

def centroid
  return @centroid if defined?(@centroid)

  cx, cy = 0, 0

  (0...vertices.length).each do |i|
    prev = vertices[i - 1]
    curr = vertices[i]

    v = prev.x * curr.y - curr.x * prev.y
    cx += v * (prev.x + curr.x)
    cy += v * (prev.y + curr.y)
  end

  @centroid = Point.new(Rational(cx, 6 * self.area), Rational(cy, 6 * self.area))
  @centroid
end

#distance(other) ⇒ Object

Returns the shortest distance between self and other.

If other is a point, then self does not need to be convex. If other is another polygon self and other must be convex.

Raises:

  • (TypeError) 


305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
 
# File 'lib/easy_geometry/d2/polygon.rb', line 305

def distance(other)
  other = Point.new(other[0], other[1]) if other.is_a?(Array)

  if other.is_a?(Point)
    dist = BigDecimal('Infinity')
    
    sides.each do |side|
      current = side.distance(other)
      if current == 0
        return 0
      elsif current < dist
        dist = current
      end
    end
    
    return dist

  elsif other.is_a?(Polygon) && self.is_convex? && other.is_convex?
    return do_poly_distance(other)
  end

  raise TypeError, "Distance not handled for #{ other.class }"
end

#hashable_content ⇒ Object 



329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
 
# File 'lib/easy_geometry/d2/polygon.rb', line 329

def hashable_content
  d = {}

  s1 = ref_list(self.vertices, d)
  r_nor = rotate_left(s1, least_rotation(s1))

  s2 = ref_list(self.vertices.reverse, d)
  r_rev = rotate_left(s2, least_rotation(s2))

  if (r_nor <=> r_rev) == -1
    r = r_nor
  else
    r = r_rev
  end

  r.map {|order| d[order]}
end

#intersection(other) ⇒ Object

The intersection of polygon and geometry entity.

The intersection may be empty and can contain individual Points and complete Line Segments.



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
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
 
# File 'lib/easy_geometry/d2/polygon.rb', line 250

def intersection(other)
  intersection_result = []
  
  if other.is_a?(Polygon) 
    k = other.sides 
  else 
    k = [other]
  end

  self.sides.each do |side|
    k.each do |side1|
      intersection_result += side.intersection(side1)
    end
  end

  intersection_result.uniq! do |a|
    if a.is_a?(Point)
      [a.x, a.y]
    else
      [a.p1, a.p2].sort_by {|p| [p.x, p.y]} 
    end
  end
  points = []; segments = []

  intersection_result.each do |entity|
    points << entity    if entity.is_a?(Point)
    segments << entity  if entity.is_a?(Segment)
  end

  if !points.empty? && !segments.empty?
    points_in_segments = []

    points.each do |point|
      segments.each do |segment|
        points_in_segments << point if segment.contains?(point)
      end
    end

    points_in_segments.uniq! {|a| [a.x, a.y]}
    if !points_in_segments.empty?
      points_in_segments.each do |p|
        points.delete(p)
      end
    end

    return points.sort + segments.sort
  end

  return intersection_result.sort
end

#is_convex? ⇒ Boolean

Is the polygon convex? A polygon is convex if all its interior angles are less than 180 degrees and there are no intersections between sides.

Returns

True if this polygon is convex
False otherwise.

Returns:

  • (Boolean) 


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
 
# File 'lib/easy_geometry/d2/polygon.rb', line 146

def is_convex?
  return @is_convex if defined?(@is_convex)

  @is_convex = false

  cw = Polygon.is_right?(vertices[-2], vertices[-1], vertices[0])
  (1...vertices.length).each do |i|
    if cw ^ Polygon.is_right?(vertices[i - 2], vertices[i - 1], vertices[i])
      return @is_convex
    end
  end

  # check for intersecting sides
  sides = self.sides
  sides.each_with_index do |si, i|
    points = [si.p1, si.p2]

    first_number = 0
    first_number = 1 if i == sides.length - 1
    (first_number...i - 1).each do |j|
      sj = sides[j]
      if !points.include?(sj.p1) && !points.include?(sj.p2)
        hit = si.intersection(sj)
          return @is_convex if !hit.empty?
      end
    end
  end
                   
  @is_convex = !@is_convex
  @is_convex
end

#is_encloses_point?(point) ⇒ Boolean

Return True if p is enclosed by (is inside of) self, False otherwise. Being on the border of self is considered False.

Parameters:

Point or Array of Numeric(coordinates)

Returns:

bool

paulbourke.net/geometry/polygonmesh/#insidepoly

Returns:

  • (Boolean)

Raises:

  • (TypeError) 


188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
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
 
# File 'lib/easy_geometry/d2/polygon.rb', line 188

def is_encloses_point?(point)
  point = Point.new(point[0], point[1]) if point.is_a?(Array)
  raise TypeError, 'Must pass only Point objects' unless point.is_a?(Point)

  return false if vertices.include?(point)

  sides.each do |s|
    return false if s.contains?(point)
  end

  # move to point, checking that the result is numeric
  lit = []
  vertices.each do |v|
    lit << v - point
  end

  poly = Polygon.new(*lit)
  # polygon closure is assumed in the following test but Polygon removes duplicate pts so
  # the last point has to be added so all sides are computed. Using Polygon.sides is
  # not good since Segments are unordered.
  args = poly.vertices
  indices = (-args.length..0).to_a

  if poly.is_convex?
    orientation = nil
    indices.each do |i|
      a = args[i]
      b = args[i + 1]
      test = ((-a.y)*(b.x - a.x) - (-a.x)*(b.y - a.y)) < 0
      
      if orientation.nil?
        orientation = test
      elsif test != orientation
        return false
      end
    end

    return true
  end

  hit_odd = false
  p1x, p1y = args[0].x, args[0].y
  indices[1..-1].each do |i|
    p2x, p2y = args[i].x, args[i].y

    if [p1y, p2y].min < 0 && [p1y, p2y].max >= 0 && 
      [p1x, p2x].max >= 0 && p1y != p2y

      xinters = (-p1y)*(p2x - p1x)/(p2y - p1y) + p1x
      hit_odd = !hit_odd if p1x == p2x or 0 <= xinters            
    end 

    p1x, p1y = p2x, p2y
  end

  return hit_odd
end

#perimeter ⇒ Object

The perimeter of the polygon.



72
73
74
75
76
77
78
79
80
81
 
# File 'lib/easy_geometry/d2/polygon.rb', line 72

def perimeter
  return @perimeter if defined?(@perimeter)

  @perimeter = 0.0
  (0...vertices.length).each do |i|
    @perimeter += vertices[i - 1].distance(vertices[i])
  end

  @perimeter
end

#sides ⇒ Object

The directed line segments that form the sides of the polygon.

Returns

Array of Segments



111
112
113
114
115
116
117
118
119
120
 
# File 'lib/easy_geometry/d2/polygon.rb', line 111

def sides
  return @sides if defined?(@sides)

  @sides = []
  (-vertices.length...0).each do |i|
    @sides << Segment.new(vertices[i], vertices[i + 1])
  end

  @sides
end