5

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?

10
  • 6
    How about two points on the line? Dec 17, 2013 at 23:39
  • 3
    You would do it the same way in math... two points on the line or one point and a slope Dec 17, 2013 at 23:47
  • 1
    The problem is that neither of those are unique descriptions of a given line. Morween asked for a method that would allow implementation of '=='. The slope and intercept uniquely identify a line. Two lines are equal iff their slopes and intercepts are equal. Store two tuples: the coordinates of the intercept (x0, y0, and z0) and the components of the slope (a, b, c). Dec 17, 2013 at 23:56
  • 3
    @CharlesE.Grant Storing points would allow implementation of operator== as you can calculate all the rest of it from those points. However, it does fail the "equal representations in memory" part.
    – Izkata
    Dec 18, 2013 at 0:45
  • I withdrew my answer, as it doesn't meet the requirement for equal representations in memory, but I would suggest reconsidering or questioning that requirement. Dec 18, 2013 at 0:50

2 Answers 2

11

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|

6
  • 3
    Should that be L = R + tV?
    – Useless
    Dec 18, 2013 at 8:21
  • Thanks... I was answering this on a bus on my cell phone; surprised that was the only typo :)
    – Dancrumb
    Dec 18, 2013 at 13:44
  • You meant "when R is perpendicular to V", not "to L"
    – Doc Brown
    Dec 18, 2013 at 13:44
  • Well, V and L are parallel, so both statements are true, but V may be a more practical choice for implementation. Conceptually, L makes more sense to me.
    – Dancrumb
    Dec 18, 2013 at 21:07
  • 1
    @Dancrumb: no, in your equation above L is a point on the line, which is never a parallel vector to V (except for R=0).
    – Doc Brown
    Dec 19, 2013 at 8:56
5

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);
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.