[Freeciv-Dev] Trigonometry of Freeciv

[Gregory Berkolaiko <gberkolaiko@xxxxxxxxxxx>]

Raimar,

As promised, here is an attempt at explaining the differences between
Eucledean and "freeciv" geometry.

First of all, in our, Eucledean, space the distance from origin (0,0) to
a point (x,y) is given by sqrt(x*x + y*y).  In Freeciv, which is played
on square lattice the distance is given by max(abs(x), abs(y)) (think
about IgTer unit).

What are the consequences?  Let us draw a unit ball: i.e. all points with
distance <1 from the origin, see trig1.gif  The problem of finding the
straightest directions to all points can be considered as problem of
dividing the first quadrant of the ball into 4 equal parts.  Then the
first quarter will be "East", second and third quarter will be
"NorthEast" and the fourth will be "North".  The quarters can be "equal"
in the sense of equal area or in the sense of having equal arc (external
boundary) lengths.

As you can see, in Eucledean space the division is given by lines at
angles pi/8, pi/4, 3pi/8.  In freeciv space, however, the division is 
arctan(1/2), pi/4, pi/4+arctan(1/2), as you can see for yourself.  Equal
arc length and equal area divisions coincide in both cases.

Just to sound impressive, freeciv space is called l-infinity in maths.

To be more concrete, one can try to assign the directions to the cells of
the square, see trig2.gif.  There I tried to assign the directions (1=E,
2=NE, 3=N) in the most fair way.  The spaces left blank do not admit the
"best" assignement, they lie on the dividing line.  But it doesn't matter
that much which direction you assign to them.

> The more I think about this the more I'm convinced that an line
> drawing at the start instead of incremental calls to
> straightest_direction is the best solution here. This can be done with
> Bresenham's line drawing algorithm. What do you think about this?
> 
> I admit that your method matches the ideal line more closely (however
> I think this isn't really necessary). The question is now what other
> differences exists in other cases between your method and the ideal
> line? Can you prove that your algorithm will always match the ideal
> line?

I am not sure what is the "ideal line" but I think on square lattice
Ross's straightest direction will produce a good one.

Hope my explanation is not too sketchy,
G.

____________________________________________________________
Do You Yahoo!?
Get your free @yahoo.co.uk address at http://mail.yahoo.co.uk
or your free @yahoo.ie address at http://mail.yahoo.ie