[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] exact algebraic numbers?



Hi Mike,

Such algebraic numbers are used in computational geometry, you can take a look at CGAL http://www.cgal.org, it's a powerfull Computational geometry written in C++ (a python binding exists) and it has an algebraic kernel for exact computation of points on a circle or on a sphere.
I'm not sure that it includes the transformations because it is done to maintain data structures like meshes, etc...
Well you have to see if it suits your need and if the effort of installing it is woth it!

Regards.
Olivier

2009/11/29 René Dudfield <renesd@xxxxxxxxx>
On Sun, Nov 29, 2009 at 5:59 AM, Michael George <mdgeorge@xxxxxxxxxxxxxx> wrote:
>
> Hello,
>
> For my game I need to represent right isosceles triangles, and do operations including translation and rotation in 15 degree increments.  Unfortunately, I cannot tolerate rounding error, because it will cause bad visual and gameplay artifacts.  I'm thinking of representing points as vectors where the components are of the form
>
> a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6)
>
> where a, b, c, and d are rationals.  I believe numbers of this form are sufficient for my purposes, although I haven't worked out all the proofs yet.  Anyway, I was wondering if anyone has done anything similar and can suggest a library I can use for manipulating such vectors before I go off and implement it myself.
>
> Thanks!
>
> --Mike


hi,

python 2.6 and 3.1 have a fractions module:
    http://docs.python.org/library/fractions.html

The Fraction class inherits from the abstract base class numbers.Rational:
   http://docs.python.org/library/numbers.html#numbers.Rational

To avoid rounding (and other numerical) errors, the typical technique
is to apply the transformations each time from the identity matrix.
So in a game where a rotation happens at say 1.0 - 1.444 degrees each
frame, you keep count of the total rotation (eg 1.444) and apply the
total rotation every frame.  Rather than applying the 1.0 rotation one
frame, and then applying the 1.444 rotation the next frame.   Over
10,000 frames or so, you can see there would be little rounding error.

You can also use integers instead of floats, but divide the value by
1,000,000 or so.  eg, 1.444 degrees could be 1,444,000.  Then as you
do not get the floating point problems.  If all of your angles are
between 0-360, and the angle increments are also small it turns out
ok.  Python has a long type, so you can get a lot of precision this
way, and avoid floating point problems somewhat.  Just before you use
the rotation, you can divide the number by 1,000,000 or so(1444000 /
1000000 == 1.444).


cu.



--
Rouiller Olivier
06 79 66 89 63
Résidence Léonard de Vinci
App. A008
59650 Villeneuve d'Ascq