In a previous article I introduced basic vector concepts. In this article, I show how apply the theory to common geometric problems.

About the Implementations

The implementations given here are written to illustrate some basic concepts. It is not production code, so it is not the best implementation in terms of maintainability, speed, or completeness. Read the tips at the end that point out some of the limitations (and possible improvements).

The code is written in Python, but should be easily readable to programmers of other languages.

Shape Representation

In most cases you will not choose your own representations of geometric figures, as these are typically determined by the library or game engine you are using. If you do roll out your own geometry primitives, however, you need to consider how you will typically get source data (that is, data formats of 3D models, hard-coded shapes, and scripted shapes), and what the typical operations on these primitives will be. In addition, you should take care that your representations work well together, otherwise your algorithms built on top will be clumsy.

The representations provided here will be used by the recipes.

Points and Vectors

As explained the previous article, there is no need to distinguish points from vectors, thus a single vector can be used to represent a point. Vectors are usually simply represented as a record, class or list of numbers – as many as the number of dimensions.

The following is a simple implementation of a 2D vector and its operations. It is pretty straightforward, so I present the entire block here without much explanation.

class Vector2D ():
  def __init__(self, x, y):
    self.x = x
    self.y = y
  
  def __str__(self):
      return '[%f, %f]' % (self.x, self.y)
  
  def neg(self):
    return Vector2D(-self.x, -self.y)
  
  def add(self, other):
    x_sum = self.x + other.x
    y_sum = self.y + other.y
  
    return Vector2D(x_sum, y_sum)
  
  def sub(self, other):
    x_dif = self.x - other.x
    y_dif = self.y - other.y
  
    return Vector2D(x_dif, y_dif)
  
  def sqr_length(self):
    return self.x * self.x + self.y * self.y
  
  def length(self):
    return sqrt(self.sqr_length())
  
  def scale(self, factor):
    return Vector2D(self.x * factor, self.y * factor)
  
  def duplicate(self):
    return Vector2D(self.x, self.y)
  
  def normalize(self):
    v = self.duplicate()
    v.normalize_inplace()
    return v
  
  def equals(self, other):
    return sqr(self.x - other.x) + sqr(self.y - other.y) < ZERO_DISTANCE_SQR
  
  def perp_op(self):
    return Vector2D(-self.y, self.x)
  
  def dot(self, other):
    return self.x * other.x + self.y * other.y
  
  def perpdot(self, other):
    return - self.y * other.x + self.x * other.y
  
  def proj_on(self, other):
    scale_factor = self.dot(other)/other.sqr_length()
    new_vector = other.scale(scale_factor)
    return new_vector
  
  def perp_on(self, other):
    scale_factor = -(self.perpdot(other)/other.sqr_length())
    new_vector = other.scale(scale_factor)
  
    return new_vector

A 3D Vector implementation is basically the same, with the obvious changes:

• An additional z component is added, and all functions take this extra component into account.
  
• The perp dot product is replaced with the cross product, like this:
  

    def cross(self, other):
      x = self.y*other.z – self.z*other.y
      y = self.z*other.x – self.x*other.z
      z = self.x*other.y – self.y*other.x

• The perp_on method is replaced with this:

    def perp_op(self, other):
      proj_vector = self.proj_on()
      
      return self.sub(proj_vector)