Efficient vector / point class in Python

Question

What is the best way to implement an efficient Vector / Point class (or even better: is it already) that can be used in both Python 2.7+ and 3.x?

I found blender-mathutils , but they seem to only support Python 3.x. Then this is a vector class that uses numpy , but it is only a three-dimensional vector. Using a list for Vector, such as the kivy vector class ( source code ), which has static attributes (x and y), seems strange. (There are all these list methods.)

I am currently using a class that extends namedtuple (as you can see below), but this has the disadvantage that you cannot change the coordinates. I think this can become a performance issue when thousands of objects are moved and each (new) tuple is created every time. (Correctly?)

class Vector2D(namedtuple('Vector2D', ('x', 'y'))): __slots__ = () def __abs__(self): return type(self)(abs(self.x), abs(self.y)) def __int__(self): return type(self)(int(self.x), int(self.y)) def __add__(self, other): return type(self)(self.x + other.x, self.y + other.y) def __sub__(self, other): return type(self)(self.x - other.x, self.y - other.y) def __mul__(self, other): return type(self)(self.x * other, self.y * other) def __div__(self, other): return type(self)(self.x / other, self.y / other) def dot_product(self, other): return self.x * other.x + self.y * other.y def distance_to(self, other): """ uses the Euclidean norm to calculate the distance """ return hypot((self.x - other.x), (self.y - other.y)) 

Edit: I did some testing, and it seems that using numpy.array or numpy.ndarray as a vector is too slow. (For example, getting an element takes almost twice as much, not to mention creating an array. I think it is more optimized to perform calculations on a large number of elements.)

So, I'm looking more for a lightweight vector class with a fixed number of fields (in my case, just x and y ) that can be used for games. (I do not want to reinvent the wheel, if already tested there.)

Answer 1

Yes, there is a vector class: it is in the standard NumPy module de facto. You create the following vectors:

 >>> v = numpy.array([1, 10, 123]) >>> 2*v array([ 2, 20, 246]) >>> u = numpy.array([1, 1, 1]) >>> vu array([ 0, 9, 122]) 

NumPy is very rich and gives you access to fast array operations: dot product ( numpy.dot() ), norm ( numpy.linalg.norm() ), etc.

Answer 2

The numpy vector class in terms of linear algebra is likely to be numpy.matrix , which is a subclass of numpy.ndarray . It is not cleaner as such, but it makes your code cleaner because algebraic operations are used instead of elementary.

 In [77]: a = np.array([1,2]) In [78]: b = np.array([3,3]) In [79]: a*b Out[79]: array([3, 6]) In [80]: np.dot(a,b) Out[80]: 9 In [81]: np.outer(a,b) Out[81]: array([[3, 3], [6, 6]]) In [82]: a = np.matrix(a).T In [83]: b = np.matrix(b) In [84]: b*a Out[84]: matrix([[9]]) In [85]: a*b Out[85]: matrix([[3, 3], [6, 6]]) 

If you want to create your own, attach it to one of them, for example:

 class v2d(np.ndarray): def __abs__(self): return np.linalg.norm(self) def dist(self,other): return np.linalg.norm(self-other) def dot(self, other): return np.dot(self, other) # and so on 

Which in the simplest case, you can simply do by looking at ndarray as a new class:

 In [63]: a = np.array([1,2]).view(v2d) In [64]: b = np.array([3,3]).view(v2d) In [65]: a Out[65]: v2d([1, 2]) In [66]: abs(b) Out[66]: 4.2426406871192848 In [67]: a - b Out[67]: v2d([-2, -1]) In [68]: a*b Out[68]: v2d([3, 6]) In [69]: a*3 Out[69]: v2d([3, 6]) In [70]: a.dist(b) Out[70]: 2.2360679774997898 In [71]: b.dist(a) Out[71]: 2.2360679774997898 In [72]: a.dot(b) Out[72]: 9 

The following is information on subclassing ndarray .

Answer 3

I needed a quick fix, so I just included the numpy array in my own. You will notice some design decisions which can be changed according to your needs (for example, by default). If you want to use it: https://gist.github.com/eigencoder/c029d7557e1f0828aec5

 import numpy as np class Point(np.ndarray): """ n-dimensional point used for locations. inherits +, -, * (as dot-product) > p1 = Point([1, 2]) > p2 = Point([4, 5]) > p1 + p2 Point([5, 7]) See ``test()`` for more usage. """ def __new__(cls, input_array=(0, 0)): """ :param cls: :param input_array: Defaults to 2d origin """ obj = np.asarray(input_array).view(cls) return obj @property def x(self): return self[0] @property def y(self): return self[1] @property def z(self): """ :return: 3rd dimension element. 0 if not defined """ try: return self[2] except IndexError: return 0 def __eq__(self, other): return np.array_equal(self, other) def __ne__(self, other): return not np.array_equal(self, other) def __iter__(self): for x in np.nditer(self): yield x.item() def dist(self, other): """ Both points must have the same dimensions :return: Euclidean distance """ return np.linalg.norm(self - other) def test(): v1 = Point([1, 2, 3]) v2 = Point([4, 5, 7]) v3 = Point([4, ]) sum12 = Point([5, 7, 10]) dot12 = Point([4, 10, 21]) # Access assert v2.x == 4 assert v2.y == 5 assert v2.z == 7 assert v3.z == 0 assert Point().x == 0 assert v2[0] == 4 assert v1[-1] == 3 # Not needed but inherited assert [x for x in v2] == [4, 5, 7], "Iteration should return all elements" # Operations assert v1 + v2 == sum12 assert v1 * v2 == dot12 assert v1.dist(v2) ** 2 == 34 assert v1 != v2 assert v2.size == 3, "v2 should be a 3d point" print "pass" if __name__ == "__main__": test()