Young programmers project: Basic geometry

Basic geometry

In this appendix I try to teach you some basic geometry, things you will need to know when drawing a game board for instance. I do assume that you have some understanding of mathematics!

Dealing with coordinates

Drawing objects in a window means that you deal with coordinates: the distances from left to right and from top to bottom (or the other way around). They are almost always called x and y. And this is where things get complicated: on computers the vertical coordinate (y) runs from top to bottom - not the other way around! This is probably due to history, but almost every system that I know of does it like this - at least when you refer to the coordinates in the window, the pixel coordinates (pixel is short for picture element, the dots that make up the screen).

So if you draw a line from pixels (10,10) to pixels (200,100) it runs down, not up (see the picture below):

Code for picture:
canvas .c -width 300 -height 300 -bg white
pack   .c -fill both
.c create line 10 10 200 100 -fill black

digression Having the y coordinate run from top to bottom makes sense when you think of numbering lines of text. Probably this was convenient, when the technique was developed to display the text on a tv screen or a monitor and when graphical presentation became possible. Yes, modern computers are loaded with historical stuff :). end digression

It is often easier to work with so-called world coordinates rather than pixel coordinates - they can be meters or inches or whatever you prefer.

digression Units like meter or inch are very important when you do calculations on a computer, because they are not visible on the stupid thing! That is, 50 meter is just the number 50, so if you multiply 50 meter by 1 hectometer to get the area of a stretch of land, it will happily do that for you and say "the answer is 50". "50 what?", you ask? Indeed, the computer does not know! You will have to provide the information yourself.

One way of doing that is to convert numbers with a unit directly to a single well-known unit. In the above case: 1 hm becomes 100 m. So the outcome is then: 5000 - and you know it is 5000 m sq (but the computer still does not!)

Actually, Tcl/Tk does support other coordinate units than pixels: you can specify the coordinates as millimeters, centimeters or inches by adding "m", "c" or "i" to the end of the number. Like:

   .c create line 1c 1c 10c 10c

Tcl/Tk will convert the centimeters to pixels automatically (this is one of the few times, that the computer does know about units :)

end digression

If you work with world coordinates, define the lower left corner to be (xmin,ymin) and the top right corner to be (xmax,ymax). Let the window be "w" pixels wide and "h" pixels high. Then these formulae convert world coordinates (xw,yw) to and from pixel coordinates (xp,yp):

  set xscale [expr {($xmax-$xmin) / $w}]
  set yscale [expr {($ymax-$ymin) / $h}]

  set xw     [expr {$xmin + $xscale * $xp}]
  set yw     [expr {$ymax - $yscale * $yp}]

  set xp     [expr {($xw-$xmin) / $xscale}]
  set yp     [expr {($ymax-$yw) / $yscale}]

(Note the difference between the two - because the pixel y coordinate runs from top to bottom!)

You will probably want to put these formulae in a separate procedure for easy use. TODO: provide these procedures!

Angles and distances

Sometimes you need to go from a known point A to a point B that is some distance (r) away from A in some direction (a) where a is the angle between the line connecting A and B and the horizontal line from A to the right (see below)

Code for picture:
canvas .c -width 300 -height 200 -bg white
pack   .c -fill both
.c create line  50 180 300 180 -fill black
.c create line  50 180 250  80 -fill black -width 2
.c create line  40 160 240  60 -fill black -arrow both
.c create arc  -50 280 150  80 -start 0 -extent 27
.c create text  45 190 -text "A"
.c create text 255  75 -text "B"
.c create text 105 115 -text "r"
.c create text 165 160 -text "a"

(For instance: you are programming a billiard game and the queue hits the queue ball under the angle a).

How do you calculate the coordinates of B? First you must know whether the angle a is in degrees (360 degrees is full-circle) or in radians (2pi radians is full-circle). If a is in degrees, then convert it to radians:

   set convrad [expr {3.1415926/180.0}]
   set arad    [expr {$convrad*$a}]

Then the vector (dx,dy) (what ordinary people call an arrow) from A to B is:

   set dx [expr {$r * cos($a)}]
   set dy [expr {$r * sin($a)}]

And you find the coordinates (xb,yb) of point B (point A has the coordinates (xa,ya)) via:

   set xb [expr {$xa + $dx}]
   set yb [expr {$ya + $dy}]

(Note: the angle is chosen positive if you go counter-clockwise from the horizontal line to the line AB that runs from A to B and it is negative if you go clockwise).

Calculating the distance between two points is simple: use good old Pythagoras:

Code for picture:
canvas .c -width 300 -height 150 -bg white
pack   .c -fill both

.c create line  50 120 250  20 -fill black -width 2
.c create line  50 120 250 120 -fill black
.c create line 250 120 250  20 -fill black
.c create text  45 130 -text "A"
.c create text 255  15 -text "B"
.c create text 200 130 -text "a"
.c create text 260  70 -text "b"
.c create text 120  60 -text "c"

There is a convenient function in Tcl for this. Once you know the sides a and b (a = xb-xa, b = yb-ya), then just do:

   set c [expr {hypot($a,$b)}]

It gives you the distance rightaway and this saves a lot of typing at times :)

Stars

Here is a small program to draw a five-pointed star:

canvas .c -width 300 -height 300 -bg white
pack   .c -fill both

set xc 150
set yc 150
set r  100
set xfirst  [expr {$xc+$r}]
set yfirst  $yc
set convrad [expr {3.1415926/180.0}]

for { set i 1 } { $i <= 5 } { incr i } {
   set a       [expr {144*$i*$convrad}]
   set xsecond [expr {$xc+$r*cos($a)}]
   set ysecond [expr {$yc+$r*sin($a)}]
   .c create line  $xfirst $yfirst $xsecond $ysecond -fill black -width 2
   set xfirst $xsecond
   set yfirst $ysecond
}

This is the result:

The picture

Let us draw the star again, now with a few symbols:

Code for picture:
canvas .c -width 300 -height 300 -bg white
pack   .c -fill both

set xc 150
set yc 150
set r  100
set xfirst  [expr {$xc+$r}]
set yfirst  $yc
set convrad [expr {3.1415926/180.0}]

.c create oval [expr {$xc-3}] [expr {$yc-3}] \
               [expr {$xc+3}] [expr {$yc+3}] -fill black

for { set i 1 } { $i <= 5 } { incr i } {
   set a       [expr {144*$i*$convrad}]
   set xsecond [expr {$xc+$r*cos($a)}]
   set ysecond [expr {$yc-$r*sin($a)}]
   .c create line  $xfirst $yfirst $xsecond $ysecond -fill black -width 2
   .c create line  $xc     $yc     $xsecond $ysecond -fill black
   set xtext   [expr {$xc+(10+$r)*cos($a)}]
   set ytext   [expr {$yc-(10+$r)*sin($a)}]
   .c create text $xtext $ytext -text [string index " BCDEA" $i]
   set xfirst $xsecond
   set yfirst $ysecond
}

The angle between the thin line that runs from the centre to A and the one that runs from the centre to D is 360/5 = 72 degrees. The angle between the line to A and the line to B is twice as large. So that explains the angle 144 degrees we used in our little program.

Try this yourself: a seven-pointed star - you can actually make two different ones by skipping one or two neighbouring points. You better draw it on paper first (that is how I do this myself too :).

Rotation

The last example that I want to show you: rotating a rectangle. You can draw a rectangle like this:

   .c create rectangle 200 200 250 220

But you can not rotate it. So, instead of drawing it as a rectangle, we will draw it as a polygon:

   .c create polygon {200 200 250 200 250 220 220 200}

For the four corners of this rectangle we are going to calculate new coordinates as follows:

The angle over which to rotate is a degrees
The centre of rotation is (xc,yc)
If we rotate around the origin (0,0), the formulae are straightforward.
We can take advantange of this: first move everything over the vector (-xc,-yc) (the centre of rotation becomes the origin). Then rotate the four corners and move everything again over (xc,yc) to get the final result.

Believe or not, the end result is (in world coordinates - remember the pixel y coordinate that runs from top-bottom?):

   set arad [expr {$convrad*$a}]
   set xn   [expr {$xc + ($xo-$xc)*cos($arad) - ($yo-$yc)*sin($arad)}]
   set yn   [expr {$yc + ($xo-$xc)*sin($arad) + ($yo-$yc)*cos($arad)}]

If we do this for each corner of the rectangle (or any polygon you want), we can rotate it:

Code for picture:
canvas .c -width 300 -height 170 -bg white
pack   .c -fill both

set rect {200 150 250 150 250 130 200 130}
set xc      100
set yc      150
set a        45

.c create polygon $rect -fill white -outline black
.c create oval [expr {$xc-3}] [expr {$yc-3}] \
               [expr {$xc+3}] [expr {$yc+3}] -fill black
.c create line $xc $yc [lindex $rect 0] [lindex $rect 1]

set newrect {}
set convrad [expr {3.1415926/180.0}]
set arad    [expr {-$convrad*$a}]

foreach {xo yo} $rect {
   set xn   [expr {$xc + ($xo-$xc)*cos($arad) - ($yo-$yc)*sin($arad)}]
   set yn   [expr {$yc + ($xo-$xc)*sin($arad) + ($yo-$yc)*cos($arad)}]

   lappend newrect $xn $yn
}

And here is the code for the picture:

Repeat the above code

The fact that the y coordinate in pixels works upside-down, is handled by defining the rectangle "upside-down" and by multiplying the angle with -1. That way we get the right picture (yes, I had to experiment a bit before I got it right - even after all these years, the upside-downness of the y coordinates still bugs me :()

Posted at Dec 09/2003 07:39 PM:
Julia: I don't understand!!!!

Posted at Dec 16/2003 06:57 AM:
Arjen Markus: Could you be a bit more specific? What do you want to be explained further?