Module: Gifenc::Geometry

Defined in:
lib/geometry.rb

Overview

This module encapsulates all the necessary geometric functionality, and more generally, all mathematical methods that may be useful for several tasks of the library, such as drawing, resampling, etc.

Every method that takes a point as argument may be supplied by providing either a Point or a [Float, Float] array representing its coordinates, regardless of whether the documentation has one or the other in the method's specification.

Defined Under Namespace

Classes: Point

Constant Summary collapse

PRECISION =

Precision of the floating point math. Anything below this threshold will be considered 0.

Returns:

  • (Float) —

    Floating point math precision.

1E-7
ORIGIN =

The point representing the origin of coordinates.

Returns:

  • (Point) —

    Origin of coordinates.

Point.new(0, 0)
E1 =

The point representing the first vector of the canonical base.

Returns:

  • (Point) —

    First canonical vector.

Point.new(1, 0)
E2 =

The point representing the second vector of the canonical base.

Returns:

  • (Point) —

    Second canonical vector.

Point.new(0, 1)

Class Method Summary collapse

Class Method Details

.bbox(points, pad = 0) ⇒ Array<Integer>

Finds the bounding box of a set of points, i.e., the minimal rectangle containing all specified points.

Parameters:

  • points (Array<Array<Integer>>) —

    The list of points, each provided as a tuple of coordinates [X, Y].

  • pad (Integer) (defaults to: 0) —

    The amount of extra padding pixels to take on each side of the rectangle. If negative, the rectangle will be smaller and thus not contain all points.

Returns:

  • (Array<Integer>) —

    Bounding box in the form [X, Y, W, H], where [X, Y] are the coordinates of the upper left corner of the rectangle, and [W, H] are its width and height, respectively.



536
537
538
539
540
541
542
543
 
# File 'lib/geometry.rb', line 536

def self.bbox(points, pad = 0)
  points = points.map{ |p| Point.parse(p) }
  x0 = points.min_by(&:x).x.round - pad
  y0 = points.min_by(&:y).y.round - pad
  x1 = points.max_by(&:x).x.round + pad
  y1 = points.max_by(&:y).y.round + pad
  [x0, y0, x1 - x0 + 1, y1 - y0 + 1]
end

.bound_check(points, bbox, silent = false) ⇒ Boolean

Checks if a list of points is entirely contained in the specified bounding box.

Parameters:

  • silent (Boolean) (defaults to: false) —

    Whether to raise an exception or simply return false when the check is failed.

Returns:

  • (Boolean) —

    Whether all points are contained in the bounding box or not.

Raises:

  • (Exception::CanvasError) —

    If the points are not contained in the bounding box and silent has not been set.



641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
 
# File 'lib/geometry.rb', line 641

def self.bound_check(points, bbox, silent = false)
  bbox = [0, 0, bbox.width, bbox.height] if bbox.is_a?(Image)
  points.map!{ |p| Point.parse(p) }
  outer_points = points.select{ |p|
    !p.x.between?(bbox[0], bbox[0] + bbox[2] - 1) ||
    !p.y.between?(bbox[1], bbox[1] + bbox[3] - 1)
  }
  if outer_points.size > 0
    return false if silent
    points_str = outer_points.take(3).map{ |p| "(#{p.x}, #{p.y})" }
                             .join(', ') + '...'
    raise Exception::CanvasError, "Out of bounds pixels found: #{points_str}"
  end
  true
end

.center(points) ⇒ Point

Find the center of mass (barycenter) of a list of points. This will always be contained within the convex hull of the supplied points.

Parameters:

  • points (Array<Point>) —

    The list of points.

Returns:

  • (Point) —

    The center of mass of the points.

Raises:



698
699
700
701
702
 
# File 'lib/geometry.rb', line 698

def self.center(points)
  raise Exception::GeometryError, "Cannot find center of empty list of points." if points.size == 0
  points.map!{ |p| Point.parse(p) }
  points.sum(ORIGIN) / points.size
end

.comb_convex(points, weights) ⇒ Point

Compute a convex combination of points given the weights. This is simply a linear combination, but the weights are normalized so they sum to 1. If they're positive, the resulting point will always be contained within the convex hull of the supplied points, hence the name. The two provided arrays should have the same length.

Returns:

  • (Point) —

    The resulting convex combination.

Raises:



686
687
688
689
690
691
 
# File 'lib/geometry.rb', line 686

def self.comb_convex(points, weights)
  return ORIGIN if points.size == 0
  weight = weights.sum
  raise Exception::GeometryError, "Cannot find convex combination, weights sum to 0." if weight.abs < PRECISION
  comb_linear(points, weights.map{ |w| w.to_f / weight })
end

.comb_linear(points, weights) ⇒ Point

Compute a linear combination of points given the weights. The two supplied arrays should have the same length.

Parameters:

  • points (Array<Point>) —

    The points to combine.

  • weights (Array<Float>) —

    The weights to utilize for each point.

Returns:

  • (Point) —

    The resulting linear combination.

Raises:



663
664
665
666
667
668
669
670
671
672
673
674
675
 
# File 'lib/geometry.rb', line 663

def self.comb_linear(points, weights)
  if points.size != weights.size
    raise Exception::GeometryError, "Point and weight counts differ."
  end
  return ORIGIN if points.size == 0

  points.map!{ |p| Point.parse(p) }
  res = points[0] * weights[0]
  points[1..-1].each_with_index{ |p, i|
    res += p * weights[i + 1]
  }
  res
end

.convex_hull(points, reduced = false) ⇒ Array<Point>

Compute the convex hull of a set of points. The convex hull is the smallest convex set containing the supplied points. This method will return the points located in the boundary of said hull in CCW order. The interior of the polygon they delimit is thus the convex hull.

The reduced version will only include the extreme points of the boundary, i.e. the vertices, as opposed to all of them. The algorithm employed in both cases is the most basic one, known as the Jarvis march.

Parameters:

  • points (Array<Point>) —

    The list of points.

  • reduced (Boolean) (defaults to: false) —

    Whether to only return the vertices of the hull.

Returns:

  • (Array<Point>) —

    The points composing the boundary of the convex hull.



607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
 
# File 'lib/geometry.rb', line 607

def self.convex_hull(points, reduced = false)
  points = points.uniq.map{ |p| Point.parse(p) }
  return points if points.size < 3
  hull_1 = points.min_by{ |p| [p.x, p.y] }
  hull_2 = nil
  hull_old = nil
  hull = []
  until hull_1 == hull.first
    hull << hull_1
    hull_2 = (points[0 ... 3] - [hull_1, hull_old]).first
    points.each{ |p|
      next if p == hull_1 || p == hull_2 || p == hull_old
      index = cw(hull_1, p, hull_2)
      next if index > PRECISION
      if index.abs < PRECISION
        d_new = hull_1.distance(p)
        d_old = hull_1.distance(hull_2)
      end
      hull_2 = p if index < -PRECISION || (reduced ? d_new > d_old : d_new < d_old)
    }
    hull_old = hull_1
    hull_1 = hull_2
  end
  hull
end

.direction(p1: nil, p2: nil, angle: nil) ⇒ Point

Find the unit direction vector of a line given either the endpoints or the angle.

Parameters:

  • p1 (Point) (defaults to: nil) —

    One point of the line.

  • p2 (Point) (defaults to: nil) —

    Another point of the line.

  • angle (Float) (defaults to: nil) —

    The angle in radians.

Returns:

  • (Point) —

    The unit direction vector.

Raises:



519
520
521
522
523
524
 
# File 'lib/geometry.rb', line 519

def self.direction(p1: nil, p2: nil, angle: nil)
  return Point.parse([1, angle], :polar) if angle
  raise Exception::GeometryError, "Couldn't parse direction, endpoints or|
    angle must be supplied." if !p1 || !p2
  (Point.parse(p1) - Point.parse(p2)).normalize
end

.endpoint(point: nil, vector: nil, direction: nil, angle: nil, length: nil) ⇒ Array<Integer>

Finds the endpoint of a line given the startpoint and something else. Namely, either of the following:

  • The displacement vector (vector).
  • The direction vector (direction) and the length (length).
  • The angle (angle) and the length (length).

Parameters:

  • point (Array<Integer>) (defaults to: nil) —

    The [X, Y] coordinates of the startpoint.

  • vector (Array<Integer>) (defaults to: nil) —

    The coordinates of the displacement vector.

  • direction (Array<Integer>) (defaults to: nil) —

    The coordinates of the direction vector. If this method is chosen, the length must be provided as well. Note that this vector will be normalized automatically.

  • angle (Float) (defaults to: nil) —

    Angle of the line in radians (0-2Pi). If this method is chosen, the length must be provided as well.

  • length (Float) (defaults to: nil) —

    The length of the line. Must be provided if either the direction or the angle method is being used.

Returns:

  • (Array<Integer>) —

    The [X, Y] coordinates of the line's endpoint.

Raises:

  • (Exception::GeometryError) —

    If the supplied parameters don't suffice to determine a line (e.g. provided the angle but not the length).



488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
 
# File 'lib/geometry.rb', line 488

def self.endpoint(
    point: nil, vector: nil, direction: nil, angle: nil, length: nil
  )
  raise Exception::GeometryError, "The line start must be specified." if !point
  point = Point.parse(point)
  if vector
    vector = Point.parse(vector)
    x1 = point.x + vector.x
    y1 = point.y + vector.y
  else
    raise Exception::GeometryError, "Either the endpoint, the vector or the length must be provided." if !length
    if direction
      direction = Point.parse(direction).normalize
    else
      raise Exception::GeometryError, "The angle must be specified if no direction is provided." if !angle
      direction = Point.new(Math.cos(angle), Math.sin(angle))
    end
    x1 = (point.x + length * direction.x).to_i
    y1 = (point.y + length * direction.y).to_i
  end
  Point.new(x1, y1)
end

.rect_overlap(*rects) ⇒ Array<Float>?

Calculate the intersection of multiple rectangles. The rectangles must be supplied in the usual format of bounding boxes, i.e. [X, Y, W, H], where X and Y are the coordinates of the upper left corner of the rectangle with respect to the image, and W and H are the width and height of the rectangle, respectively. The result will be a rectangle in the same format, if the intersection is non-empty, or nil otherwise.

Parameters:

  • rects (Array<Array<Float>>) —

    The rectangles to intersect.

Returns:

  • (Array<Float>, nil) —

    The resulting intersection.



553
554
555
556
557
558
559
560
561
562
563
 
# File 'lib/geometry.rb', line 553

def self.rect_overlap(*rects)
  return if rects.empty?

  rect = rects[0]
  rects[1..-1].each{ |r|
    rect = rect_overlap_two(rect, r)
    return if !rect
  }

  rect
end

.transform(points, bbox) ⇒ Array<Array<Integer>>

Computes the coordinates of a list of points relative to a provided bbox. This can be useful when we have the coordinates relative to the whole logical screen, but we want to use them in an image that doesn't cover the whole canvas. We can simply provide the bounding box of the image, that specifies the image's offset and dimensions, and this will transform the coordinates so that they can be used in the image with the same result. In practice, this simply translates the points by subtracting the upper left corner of the bounding box.

Parameters:

  • points (Array<Array<Integer>>) —

    The list of points, each provided as a tuple of coordinates [X, Y].

  • bbox (Array<Integer>) —

    The bounding box in the form [X, Y, W, H], where [X, Y] are the coordinates of the upper left corner of the rectangle, and [W, H] are its width and height, respectively.

Returns:

  • (Array<Array<Integer>>) —

    The list of transformed points.



592
593
594
 
# File 'lib/geometry.rb', line 592

def self.transform(points, bbox)
  translate(points, [-bbox[0], -bbox[1]])
end

.translate(points, vector) ⇒ Array<Array<Integer>>

Translate a set of points according to a fixed vector. Given a list of points P1, ... , Pn and a translation vector t, this method will return the transformed list of points P1 + t, ... , Pn + t.

Parameters:

  • points (Array<Array<Integer>>) —

    The list of points, each provided as a tuple of coordinates [X, Y].

  • vector (Array<Integer>) —

    The translation vector to apply to all the supplied points.

Returns:

  • (Array<Array<Integer>>) —

    The list of translated points.



573
574
575
576
 
# File 'lib/geometry.rb', line 573

def self.translate(points, vector)
  vector = Point.parse(vector)
  points.map{ |p| Point.parse(p) + vector }
end