[Freeciv-Dev] Re: Trigonometry of Freeciv

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Thu, Sep 27, 2001 at 08:06:10PM +0100, Gregory Berkolaiko wrote:
> 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.

Thanks for the explanation.

> > 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"

IMHO this is the line a line drawing algorithm like Bresenham will
draw if it gets the global start and end point. Note that currently
these information aren't available. Missing is only the start
position. I'm sure we can solve this by adding goto_src_x and
goto_src_y fields.

> but I think on square lattice Ross's straightest direction will
> produce a good one.

Ack.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "This is Linux Country. On a quiet night, you can hear Windows reboot."