class EasyGeometry::D2::Polygon

Must be at least 3 points

Attributes

vertices[R]

Public Class Methods

is_right?(a, b, c) click to toggle source

Return True/False for cw/ccw orientation.

Parameters:

a, b, c - EasyGeometry::D2::Point or Array of Numeric(coordinates)
# 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
new(*args) click to toggle source
# File lib/easy_geometry/d2/polygon.rb, line 18
def initialize(*args)
  @vertices = preprocessing_args(args)
  remove_consecutive_duplicates
  remove_collinear_points
end

Public Instance Methods

==(other) click to toggle source

Returns True if self and other are the same mathematical entities

# 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() click to toggle source

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.

# 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() click to toggle source

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

Returns:

Array of Numeric
# 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() click to toggle source

The centroid of the polygon.

Returns

Point
# 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) click to toggle source

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.

# 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() click to toggle source
# 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) click to toggle source

The intersection of polygon and geometry entity.

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

# 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?() click to toggle source

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.
# 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) click to toggle source

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

# 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() click to toggle source

The perimeter of the polygon.

# 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() click to toggle source

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

Returns

Array of Segments
# 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

Private Instance Methods

do_poly_distance(e2) click to toggle source

Calculates the least distance between the exteriors of two convex polygons e1 and e2. Does not check for the convexity of the polygons as this is checked by Polygon.#distance.

Method:

1

cgm.cs.mcgill.ca/~orm/mind2p.html

Uses rotating calipers:

2

en.wikipedia.org/wiki/Rotating_calipers

and antipodal points:

3

en.wikipedia.org/wiki/Antipodal_point

# File lib/easy_geometry/d2/polygon.rb, line 359
def do_poly_distance(e2)
  e1 = self

  # Tests for a possible intersection between the polygons and outputs a warning
  e1_center = e1.centroid
  e2_center = e2.centroid
  e1_max_radius = Rational(0)
  e2_max_radius = Rational(0)

  e1.vertices.each do |vertex|
    r = e1_center.distance(vertex)
    e1_max_radius = r if e1_max_radius < r
  end

  e2.vertices.each do |vertex|
    r = e2_center.distance(vertex)
    e2_max_radius = r if e2_max_radius < r          
  end

  center_dist = e1_center.distance(e2_center)
  if center_dist <= e1_max_radius + e2_max_radius
    puts "Polygons may intersect producing erroneous output"
  end

  # Find the upper rightmost vertex of e1 and the lowest leftmost vertex of e2
  e1_ymax = e1.vertices.first
  e2_ymin = e2.vertices.first

  e1.vertices.each do |vertex|
    if vertex.y > e1_ymax.y || (vertex.y == e1_ymax.y && vertex.x > e1_ymax.x)
      e1_ymax = vertex
    end
  end
  
  e2.vertices.each do |vertex|
    if vertex.y < e2_ymin.y || (vertex.y == e2_ymin.y && vertex.x < e2_ymin.x)
      e2_ymin = vertex
    end
  end

  min_dist = e1_ymax.distance(e2_ymin)

  # Produce a dictionary with vertices of e1 as the keys and, for each vertex, the points
  # to which the vertex is connected as its value. The same is then done for e2.

  e1_connections = {}
  e2_connections = {}

  e1.sides.each do |side|
    if e1_connections[side.p1].nil?
      e1_connections[side.p1] = [side.p2]
    else
      e1_connections[side.p1] << side.p2
    end

    if e1_connections[side.p2].nil?
      e1_connections[side.p2] = [side.p1]
    else
      e1_connections[side.p2] << side.p1            
    end
  end

  e2.sides.each do |side|
    if e2_connections[side.p1].nil?
      e2_connections[side.p1] = [side.p2]
    else
      e2_connections[side.p1] << side.p2
    end

    if e2_connections[side.p2].nil?
      e2_connections[side.p2] = [side.p1]
    else
      e2_connections[side.p2] << side.p1
    end
  end

  e1_current = e1_ymax
  e2_current = e2_ymin
  support_line = Line.new([0, 0], [1, 0])

  # Determine which point in e1 and e2 will be selected after e2_ymin and e1_ymax,
  # this information combined with the above produced dictionaries determines the
  # path that will be taken around the polygons

  point1 = e1_connections[e1_ymax][0]
  point2 = e1_connections[e1_ymax][1]
  angle1 = support_line.angle_between(Line.new(e1_ymax, point1))
  angle2 = support_line.angle_between(Line.new(e1_ymax, point2))

  if angle1 < angle2
    e1_next = point1
  elsif angle2 < angle1
    e1_next = point2
  elsif e1_ymax.distance(point1) > e1_ymax.distance(point2)
    e1_next = point2
  else
    e1_next = point1
  end

  point1 = e2_connections[e2_ymin][0]
  point2 = e2_connections[e2_ymin][1]
  angle1 = support_line.angle_between(Line.new(e2_ymin, point1))
  angle2 = support_line.angle_between(Line.new(e2_ymin, point2))

  if angle1 > angle2
    e2_next = point1
  elsif angle2 > angle1
    e2_next = point2
  elsif e2_ymin.distance(point1) > e2_ymin.distance(point2)
    e2_next = point2
  else
    e2_next = point1
  end

  # Loop which determines the distance between anti-podal pairs and updates the
  # minimum distance accordingly. It repeats until it reaches the starting position.

  while true
    e1_angle = support_line.angle_between(Line.new(e1_current, e1_next))
    e2_angle = Math::PI - support_line.angle_between(Line.new(e2_current, e2_next))

    if e1_angle < e2_angle
      support_line = Line.new(e1_current, e1_next)
      e1_segment = Segment.new(e1_current, e1_next)
      min_dist_current = e1_segment.distance(e2_current)

      if min_dist_current < min_dist
        min_dist = min_dist_current
      end

      if e1_connections[e1_next][0] != e1_current
        e1_current = e1_next
        e1_next = e1_connections[e1_next][0]
      else
        e1_current = e1_next
        e1_next = e1_connections[e1_next][1]
      end
    elsif e1_angle > e2_angle
      support_line = Line.new(e2_next, e2_current)
      e2_segment = Segment.new(e2_current, e2_next)
      min_dist_current = e2_segment.distance(e1_current)

      if min_dist_current < min_dist
        min_dist = min_dist_current
      end

      if e2_connections[e2_next][0] != e2_current
        e2_current = e2_next
        e2_next = e2_connections[e2_next][0]
      else
        e2_current = e2_next
        e2_next = e2_connections[e2_next][1]
      end

    else
      support_line = Line.new(e1_current, e1_next)
      e1_segment = Segment.new(e1_current, e1_next)
      e2_segment = Segment.new(e2_current, e2_next)
      min1 = e1_segment.distance(e2_next)
      min2 = e2_segment.distance(e1_next)

      min_dist_current = [min1, min2].min

      if min_dist_current < min_dist
        min_dist = min_dist_current
      end

      if e1_connections[e1_next][0] != e1_current
        e1_current = e1_next
        e1_next = e1_connections[e1_next][0]
      else
        e1_current = e1_next
        e1_next = e1_connections[e1_next][1]
      end

      if e2_connections[e2_next][0] != e2_current
        e2_current = e2_next
        e2_next = e2_connections[e2_next][0]
      else
        e2_current = e2_next
        e2_next = e2_connections[e2_next][1]
      end
    end

    break if e1_current == e1_ymax && e2_current == e2_ymin
  end

  return min_dist
end
least_rotation(x) click to toggle source

Returns the number of steps of left rotation required to obtain lexicographically minimal array. en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation

# File lib/easy_geometry/d2/polygon.rb, line 563
def least_rotation(x)
  s = x + x                 # Concatenate arrays to it self to avoid modular arithmetic
  f = [-1] * s.length       # Failure function
  k = 0                     # Least rotation of array found so far

  (1...s.length).each do |j|
    sj = s[j]
    i = f[j - k - 1]

    while i != -1 && sj != s[k + i + 1]
      if sj < s[k + i + 1]
        k = j-i-1
      end

      i = f[i]
    end

    if sj != s[k + i + 1]
      if sj < s[k]
        k = j
      end
      
      f[j - k] = -1
    else
      f[j - k] = i + 1
    end
  end

  return k
end
preprocessing_args(args) click to toggle source

preprocessing_args - convert coordinates to points if necessary.

# File lib/easy_geometry/d2/polygon.rb, line 604
def preprocessing_args(args)
  args.map do |v|
    if v.is_a?(Array) && v.length == 2
      Point.new(*v)
    elsif v.is_a?(Point)
      v
    else
      raise TypeError, "Arguments should be arrays with coordinates or Points."
    end
  end
end
ref_list(point_list, d) click to toggle source
# File lib/easy_geometry/d2/polygon.rb, line 549
def ref_list(point_list, d)
  kee = {}
  
  point_list.sort_by {|p| [p.x, p.y]}.each_with_index do |p, i|
    kee[p] = i
    d[i] = p
  end

  point_list.map {|p| kee[p]}
end
remove_collinear_points() click to toggle source
# File lib/easy_geometry/d2/polygon.rb, line 631
def remove_collinear_points
  i = 0
  while i < vertices.length
    a, b, c = vertices[i], vertices[i - 1], vertices[i - 2]
    if Point.is_collinear?(a, b, c)
      vertices.delete_at(i - 1)
      vertices.delete_at(i - 2) if a == c
    else
      i += 1
    end
  end

  validate
end
remove_consecutive_duplicates() click to toggle source
# File lib/easy_geometry/d2/polygon.rb, line 616
def remove_consecutive_duplicates
  nodup = []        
  @vertices.each do |p|
    next if !nodup.empty? && p == nodup[-1]
    nodup << p
  end

  if nodup.length > 1 && nodup[-1] == nodup[0]
    nodup.pop # last point was same as first
  end

  @vertices = nodup
  validate
end
rotate_left(x, y) click to toggle source

Left rotates a list x by the number of steps specified in y.

# File lib/easy_geometry/d2/polygon.rb, line 596
def rotate_left(x, y)
  return [] if x.length == 0
 
  y = y % x.length
  x[y..-1] + x[0...y]
end
validate() click to toggle source
# File lib/easy_geometry/d2/polygon.rb, line 646
def validate
  raise ArgumentError, 'Number of vertices should be more than 2' if vertices.length < 3
end