How to represent a geometric line programmatically?

Question

I have been trying to design a library to do some simple geometric computations in an Euclidean space regardless of its dimension. While it is easy to represent points, vectors, hyperspheres and hyperplanes in a generic fashion, I am still unable to find a generic way to represent a (infinite) line, even though lines share properties across dimensions.

My best guess is that I could store some of the parameters of its parametric equation since it is easy to extend a parametric equation to a line in a space of any dimension:

x = x0 + at
y = y0 + bt
z = z0 + ct
// can be extended to any dimension

But even with this equation, I can't find what should be stored and what should not be in order to compare lines. With an ideal solution, two objects of type Line:

• would be programmatically equal (with operator==),
• would have equal representations in the memory.

What should I store in order to achieve that?

Answer 1

I think you're on the right track with your parametric equation.

What you have there is the vector form of the line equation.

L = R + tV

Where R is [x0, y0, z0] and V is [a, b, c].

You just need to normalize your equations. You would do that by finding the value of R such that |R| is at a minimum, which occurs when R is perpendicular to V, or R.V = 0.

Also, since t can be scaled by any value, without changing the line, you should normalize V by dividing every coefficient by |V|

Answer 2

At a minimum, all you need to compare lines for equality is the parametric equation you already have.

Given lines L,M expressed as Dancrumb suggests:

L = X + tV
M = Y + tW

then L == M if V and W are parallel (or equal if they're normalized to unit length and some "positive" direction), and Y=X+tV for some t.

To get memberwise equality, normalizing the vector length & direction is the first step, but you also need some rule to normalize the point. You could, for example, choose the point on your line which is closest to the origin, and use that.

Pseudo code for normalizing your vectors and points:

vec normalize_vec(vec v) {
  // 1. force unit length
  v = v/v.length();
  // 2. force positive direction
  for (int i = 0; i < v.dimension(); ++i) {
    if (v[i] < 0) {
      v = v * -1;
      break;
    }
    if (v[i] > 0)
      break;
    // keep going until the first nonzero element
  }
  return v;
}

point closest(point p, line l) {
  return (a-p).dot(l.vec) * l.vec;
}

line normalize_line(line l) {
  point new_pt = closest(point::origin, l);
  vec new_vec = normalize(l.vec);
  return line(new_pt, new_vec);
}