• 15
• 15
• 11
• 9
• 10

# 2D Vector and Point template classes

This topic is 3143 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi guys, i have implemented and slightly modified some code i found for 2D vector and point classes. But i am a bit stumped trying to make them template classes. Posting here is a last resort, i have looked on google already but searching for "vector" comes up with std::vectors and "point" thinks i mean pointer. Anyway, i am having trouble specifically with referring to the Vector class in the class definition of Point. I don't know how to correctly declare it (without causing cyclic dependency). Here is the code. (Note: the code may be freely used and modified and i have included the copyright notice with it) Point.h
/////////////////////////////////////////////////////////////////////
// File: Vector.h                                                  //
// Date: 11/8/09                                                   //
// Desc: 2D vector definition. Modified from http://softsurfer.com //
//                                                                 //
//  Copyright 2003, softSurfer (www.softsurfer.com)                //
//  This code may be freely used and modified for any purpose      //
//  providing that this copyright notice is included with it.      //
//  SoftSurfer makes no warranty for this code, and cannot be held //
//  liable for any real or imagined damage resulting from its use. //
//  Users of this code must verify correctness for their           //
//  application.                                                   //
//                                                                 //
/////////////////////////////////////////////////////////////////////

#ifndef _POINT_H_
#define _POINT_H_

#include <math.h>

namespace physics {

template <class T>
class Vector;

template <class T>
class Point {
friend Vector<T>;
public:
T x, y;

Point() : x(0), y(0) {}
Point(T x, T y) : x(x), y(y) {}
~Point() {};

//----------------------------------------------------------
// Comparison
bool operator==(Point);
bool operator!=(Point);

//----------------------------------------------------------
// Point and Vector Operations (always valid)
Vector operator-(Point);       // Vector difference
Point  operator+(Vector);      // +translate
Point  operator-(Vector);      // -translate
Point& operator+=(Vector);     // inc translate
Point& operator-=(Vector);     // dec translate

//----------------------------------------------------------
// Point Scalar Operations (convenient but often illegal)
// using any type of scalar (int, float, or double)
//    are not valid for points in general,
//    unless they are 'affine' as coeffs of
//    a sum in which all the coeffs add to 1,
//    such as: the sum (a*P + b*Q) with (a+b == 1).
//    The programmer must enforce this (if they want to).

// Scalar Multiplication
friend Point operator*(T, Point);
friend Point operator*(Point, T);
// Scalar Division
friend Point operator/(Point, T);

//----------------------------------------------------------
// Point Addition (also convenient but often illegal)
//    is not valid unless part of an affine sum.
//    The programmer must enforce this (if they want to).
friend Point operator+(Point, Point);     // add points

//----------------------------------------------------------
// Point Relations
friend T dist(Point, Point);         // Distance
friend T distSquared(Point, Point);  // Distance^2
};

}  // namespace physics

#endif  // _POINT_H_


Point.cpp
#include "ballistic/include.h"
#include "Point.h"
#include "Vector.h"
using namespace physics;

//------------------------------------------------------------------
// Comparison
//------------------------------------------------------------------

template <class T>
bool Point<T>::operator==(Point<T> q) {
return (x == q.x && y == q.y);
}

template <class T>
bool Point<T>::operator!=(Point<T> q) {
return (x != q.x || y != q.y);
}

//------------------------------------------------------------------
// Point Vector Operations
//------------------------------------------------------------------

template <class T>
Vector<T> Point<T>::operator-(Point<T> q) {   // Vector diff of Points
Vector<T> v;
v.x = x - q.x;
v.y = y - q.y;
return v;
}

template <class T>
Point<T> Point<T>::operator+(Vector<T> v) {   // +ve translation
Point<T> p;
p.x = x + v.x;
p.y = y + v.y;
return p;
}

template <class T>
Point<T> Point<T>::operator-(Vector<T> v) {   // -ve translation
Point<T> p;
p.x = x - v.x;
p.y = y - v.y;
return p;
}

template <class T>
Point<T>& Point<T>::operator+=(Vector<T> v) { // +ve translation
x += v.x;
y += v.y;
return *this;
}

template <class T>
Point<T>& Point<T>::operator-=(Vector<T> v) { // -ve translation
x -= v.x;
y -= v.y;
return *this;
}

//------------------------------------------------------------------
// Point Scalar Operations (convenient but often illegal)
//        are not valid for points in general,
//        unless they are 'affine' as coeffs of
//        a sum in which all the coeffs add to 1,
//        such as: the sum (a*P + b*q) with (a+b == 1).
//        The programmer must enforce this (if they want to).
//------------------------------------------------------------------

template <class T>
Point<T> operator*(T c, Point<T> q) {
Point<T> p;
p.x = c * q.x;
p.y = c * q.y;
return p;
}

template <class T>
Point<T> operator*(Point<T> q, T c) {
Point<T> p;
p.x = c * q.x;
p.y = c * q.y;
return p;
}

template <class T>
Point<T> operator/(Point<T> q, T c) {
Point<T> p;
p.x = q.x / c;
p.y = q.y / c;
return p;
}

//------------------------------------------------------------------
// Point Addition (also convenient but often illegal)
//    is not valid unless part of an affine sum.
//    The programmer must enforce this (if they want to).
//------------------------------------------------------------------
template <class T>
Point<T> operator+(Point<T> q, Point<T> r) {
Point<T> p;
p.x = q.x + r.x;
p.y = q.y + r.y;
return p;
}

//------------------------------------------------------------------
// Distance between Points
//------------------------------------------------------------------

template <class T>
T dist(Point<T> p, Point<T> q) {      // Euclidean distance
T dx = p.x - q.x;
T dy = p.y - q.y;
return sqrt(dx*dx + dy*dy);
}

template <class T>
T distSquared(Point<T> p, Point<T> q) {// squared distance (more efficient)
T dx = p.x - q.x;
T dy = p.y - q.y;
return (dx*dx + dy*dy);
}


Vector.h
#ifndef _VECTOR_H_
#define _VECTOR_H_

#include "Point.h"

namespace physics {

template <class T>
class Vector : public Point<T> {
public:
Vector() : x(0), y(0) {}
Vector(T x, T y) : x(x), y(y) {}
static Vector fromPolar(T dist, double angle);

T length() { return (T)sqrt(x*x + y*y); }

//----------------------------------------------------------
// Vector Unary Operations
Vector operator-();                // unary minus
Vector operator~();                // unary 2D perp operator

//----------------------------------------------------------
// Scalar Multiplication
friend Vector operator*(T, Vector);
friend Vector operator*(Vector, T);
// Scalar Division
friend Vector operator/(Vector, T);

//----------------------------------------------------------
// Vector Arithmetic Operations
Vector operator-(Vector);      // vector subtract
T operator*(Vector);           // inner dot product
T operator|(Vector);           // 2D exterior perp product

Vector& operator*=(T);         // vector scalar mult
Vector& operator/=(T);         // vector scalar div
Vector& operator+=(Vector);    // vector increment
Vector& operator-=(Vector);    // vector decrement

// Returns a normalized vector from this one
Vector normalized();

// Normalizes the given vector
static void normalize(Vector& v);
};

}  // namespace physics

#endif  // _VECTOR_H_


Vector.cpp
#include "ballistic/include.h"
#include "Vector.h"
using namespace physics;

template <class T>
Vector<T> Vector<T>::fromPolar(T dist, double angle) {
}

//------------------------------------------------------------------
//  Unary Ops
//------------------------------------------------------------------

// unary minus
template <class T>
Vector<T> Vector<T>::operator-() {
Vector<T> v;
v.x = -x; v.y = -y;
return v;
}

// unary 2D perp operator
template <class T>
Vector<T> Vector<T>::operator~() {
Vector<T> v;
v.x = -y; v.y = x;
return v;
}

//------------------------------------------------------------------
//  Scalar Ops
//------------------------------------------------------------------

// Scalar Multiplies
template <class T>
Vector<T> operator*(T c, Vector<T> w) {
Vector<T> v;
v.x = c * w.x;
v.y = c * w.y;
return v;
}

template <class T>
Vector<T> operator*(Vector<T> w, T c) {
Vector<T> v;
v.x = c * w.x;
v.y = c * w.y;
return v;
}

// Scalar Divides
template <class T>
Vector<T> operator/(Vector<T> w, T c) {
Vector<T> v;
v.x = w.x / c;
v.y = w.y / c;
return v;
}

//------------------------------------------------------------------
//  Arithmetic Ops
//------------------------------------------------------------------

template <class T>
Vector<T> Vector<T>::operator+(Vector<T> w) {
Vector<T> v;
v.x = x + w.x;
v.y = y + w.y;
return v;
}

template <class T>
Vector<T> Vector<T>::operator-(Vector<T> w) {
Vector<T> v;
v.x = x - w.x;
v.y = y - w.y;
return v;
}

//------------------------------------------------------------------
//  Products
//------------------------------------------------------------------

// Inner Dot Product
template <class T>
T Vector<T>::operator*(Vector<T> w) {
return (x * w.x + y * w.y);
}

// 2D Exterior Perp Product
template <class T>
T Vector<T>::operator|(Vector<T> w) {
return (x * w.y - y * w.x);
}

//------------------------------------------------------------------
//  Shorthand Ops
//------------------------------------------------------------------

template <class T>
Vector<T>& Vector<T>::operator*=(T c) {         // vector scalar mult
x *= c;  y *= c;
return *this;
}

template <class T>
Vector<T>& Vector<T>::operator/=(T c) {         // vector scalar div
x /= c;  y /= c;
return *this;
}

template <class T>
Vector<T>& Vector<T>::operator+=(Vector<T> w) { // vector increment
x += w.x;  y += w.y;
return *this;
}

template <class T>
Vector<T>& Vector<T>::operator-=(Vector<T> w) { // vector decrement
x -= w.x;  y -= w.y;
return *this;
}

template <class T>
Vector<T> Vector<T>::normalized() {
if (x == 0 && y == 0) return Vector();
T len = length();
Vector<T> v;
v.x = x / len;
v.y = y / len;
return v;
}

template <class T>
void Vector<T>::normalize(Vector& v) {
if (v.x == 0 && v.y == 0) return;
T len = v.length();
v.x /= len;
v.y /= len;
}


I have had trouble compiling it, the current error i get is:
Point.cpp
.\physics\Point.cpp(54) : error C2371: 'physics::Point<T>::operator +' : redefinition; different basic types
c:\...\physics\Point.h(44) : see declaration of 'physics::Point<T>::operator +'
I would really appreciate it if someone could explain what i am doing wrong. thanks [Edited by - XTAL256 on August 16, 2009 4:17:09 AM]

##### Share on other sites
You shouldn't separate the definition of your template class from its declaration.
The definition of your template class and its declaration should reside in the same file. There should only be one file, for example, "Point.h", where everything is defined and implemented.
In short, put all that are inside your ".cpp" files inside their corresponding ".hpp" files.

##### Share on other sites
Besides what johnstanp said (which is sadly true), I have a few random comments.

The way Mathematicians usually look at these things, vectors are more basic entities than points and can be defined without making any reference to points.

In Affine Geometry, once you pick a point as the origin you can describe any point as "the origin plus some vector". Then it makes sense to represent a point by that vector.

Scalar multiplication and division are not well-defined operations on points, since the result depends on your selection of origin. I wouldn't provide them. Same thing goes for addition of points. There is an argument for providing these operations in that it makes it possible to write expressions like M = (P + Q) / 2;', which is a valid operation, because what you are doing is computing a barycenter. I think I prefer to provide an explicit function to compute the barycenter if I need one.

I wouldn't overload operators ~, * and | for vectors to represent "take a perpendicular", "dot product" and "2D exterior perp product" (I didn't even have a name for this operation), because they are not standard enough, so people will have a hard time understanding code that uses them. I would much rather see functions used for this purpose: perp(v)', dot(v,w)' and exterior_perp_product(v,w)'. If anything, what you are calling v|w' should be called v^w', because that operation is almost identical to the wedge product.

What's the point of having all those friend' declarations if everything in your classes is public?

##### Share on other sites

1. Symbols that start with an underscore followed by a capital letter are reserved by the implementation, so I would recommend just using (e.g.) POINT_H_ or POINT_H rather than _POINT_H_.

2. Since you're using C++, the correct header to include would be cmath rather than math.h.

3. This is somewhat subjective, but I wouldn't put general math classes in a 'physics' namespace (such classes can be used in many contexts, not just physics).

4. Don't implement empty non-virtual destructors (the compiler-generated destructor will suffice in this case).

5. Binary operators are usually best implemented as non-member functions (read any of the many previous threads on vector and matrix classes for more info on this). It looks like you've implemented some of the binary operators this way, but not all of them.

6. Unless I'm missing something, the non-member functions don't need to be friends of the classes (since the data is all public).

7. Implement operator!= as return !(a==b) (following the principle of code reuse).

8. Code such as:
Vector<T> v;v.x = x - q.x;v.y = y - q.y;return v;
Can be more concisely written as:
return Vector<T>(x - q.x, y - q.y);
I'll also just offer my personal opinion on something. Occasionally you'll come across long, spirited discussions online as to whether a math library should have separate point and vector classes, or just a vector class. Some people swear by separate classes, but in my experience (and I stress that this is only IMX), this approach is rarely used in commercial code or in popular commercial or free math libraries. (I'm sure someone will be able to offer counterexamples - again, I'm just saying that in the math libraries I have studied or used myself this approach has rarely been used).

I've written a lot of code using various math libraries, and I can honestly say that not once have I encountered a case where I wished I had separate point and vector classes available. IMO, this adds a layer of complexity that is unnecessary and unhelpful, and that you just end up having to jump through hoops to work around.

Note that here I'm talking about game development; in a more rigorous mathematical context, having separate point and vector classes might be useful.

##### Share on other sites
Quote:
 Original post by jykI'll also just offer my personal opinion on something. Occasionally you'll come across long, spirited discussions online as to whether a math library should have separate point and vector classes, or just a vector class. Some people swear by separate classes, but in my experience (and I stress that this is only IMX), this approach is rarely used in commercial code or in popular commercial or free math libraries. (I'm sure someone will be able to offer counterexamples - again, I'm just saying that in the math libraries I have studied or used myself this approach has rarely been used).I've written a lot of code using various math libraries, and I can honestly say that not once have I encountered a case where I wished I had separate point and vector classes available. IMO, this adds a layer of complexity that is unnecessary and unhelpful, and that you just end up having to jump through hoops to work around.Note that here I'm talking about game development; in a more rigorous mathematical context, having separate point and vector classes might be useful.

I'm more familiar with the "rigorous mathematical" environment than with game development, so it should be no surprise that I favor the separate-classes approach. However, I think there are probably practical situations where it would matter. For instance, if you apply an affine transform (say local to world coordinates) to a model where you have vertices (points) and you have normals (vectors), you shouldn't apply the translation part of the transform to the normals, but you should apply everything to the vertices. How is this usually done with libraries that don't distinguish between point and vector?

To the OP: Where is that promised copyright notice? I am afraid you are currently in violation of this code's copyright...

##### Share on other sites
Quote:
 I'm more familiar with the "rigorous mathematical" environment than with game development, so it should be no surprise that I favor the separate-classes approach. However, I think there are probably practical situations where it would matter. For instance, if you apply an affine transform (say local to world coordinates) to a model where you have vertices (points) and you have normals (vectors), you shouldn't apply the translation part of the transform to the normals, but you should apply everything to the vertices. How is this usually done with libraries that don't distinguish between point and vector?
Sure, you're absolutely right that quite often it does matter. My observation is that the 'point vs. vector' problem is usually solved in one of the following two ways when working with a library that only offers a vector class:

1. Use homogenous coordinates and treat vectors and points uniformly (vectors with a w of 0, points with a w of 1).

2. Provide separate functions for manipulating vectors and points (for example, many libraries have separate 'transform point' and 'transform vector' functions).

There may be other ways to approach the problem, but these are the methods I've seen used most often.

##### Share on other sites
Quote:
 I wouldn't overload operators ~, * and | for vectors to represent "take a perpendicular", "dot product" and "2D exterior perp product" (I didn't even have a name for this operation), because they are not standard enough, so people will have a hard time understanding code that uses them. I would much rather see functions used for this purpose: perp(v)', dot(v,w)' and exterior_perp_product(v,w)'.
@The OP: I second this. A good rule of thumb: if it's not immediately apparent from context what a particular overload does, use a named function instead. (As with all things there are exceptions, but in the case of basic math classes I think this guideline is applicable.)

##### Share on other sites
"How is this usually done with libraries that don't distinguish between point and vector?"

It is traditional that one uses vectors with an "extra" component. A position vector reads [ X Y Z 1 ], a direction vector reads [ X Y Z 0 ]

Transformation matricies contain both the rotation 3x3 matrix and a row of translation -- the zero in the direction matrix means the translation elements are not added in.

##### Share on other sites
Quote:
 Original post by jyk1. Use homogenous coordinates and treat vectors and points uniformly (vectors with a w of 0, points with a w of 1).

This is a decent solution, but the purist in me would like to point out that homogeneous coordinates with w=0 don't represent vectors: They represent points at infinity. In homogeneous coordinates, [1 0 3 0] and [-2 0 -6 0] represent the same thing.

The arithmetic works, though. It's just the usage of the name "homogeneous coordinates" that bothers me. I should work on it with my therapist. :)

Quote:
 2. Provide separate functions for manipulating vectors and points (for example, many libraries have separate 'transform point' and 'transform vector' functions).

This makes sense. You still need to be aware of the difference between points and vectors, and it's simply that the type system doesn't help you.

I guess it's like having separate types for lengths, weights, times, angles... or simply using `float' for everything. In some sense, using a single class for point and vector is a lower-level way of doing things. My intuition is that this would be a good place to use the power of the C++ type system, but if game developers don't see the problem that this would solve, perhaps there isn't one.

##### Share on other sites
Firstly, i would like to point out that i didn't write all that code so don't blame me if it's not that great [smile]. In fact, i wasn't going to implement the ~, * and | operators, but i ended up just copying the whole code. I will remove them now, though, as i do agree that should be immediately apparent what overloaded operators do.
Secondly, i personally see the need for separate Point and Vector classes, or at least typedef one as the other. It seems a little silly to use a vector to describe, say, the position of something. Also, arithmetic operations have slightly different meaning on vectors (as you said, * and / aren't well defined on points).
Thirdly, i read that i should put template declaration and definition in the header file, but how do i stop cyclic dependencies? Vector is inherited by Point, but Point uses Vector.
Lastly, if i am going about all this the wrong way, how should i do it?

@alvaro: the copyright says i can freely use it as long as i include that copyright notice. I mentioned in my first post that i have included it in my code (just not in this post).