[TR] - Geometrical calculations are important to many applications like [GIS] or drawing programs. Perhaps we can collect some good algorithms here. I had a look at http://www.geometryalgorithms.com which is a great source of all kinds of calculations we might need for canvas items.

Let me start with ...
----
'''The area of a polygon'''

 # compute the area of a polygon given its coordinates
 #
 # Argument: coords -> list of coordinates
 #
 # Returns: Area of polygon (taking care of holes inside the polygon)
 #
 proc polygonArea {coords}  {
   # make sure we have a closed set of coords:
   if {[lindex $coords 0] != [lindex $coords end-1] \
    || [lindex $coords 1] != [lindex $coords end]} {
       lappend coords [lindex $coords 0] [lindex $coords 1]
   }
   # append another point for the calculation:
   lappend coords [lindex $coords 2] [lindex $coords 3]
   # area:
   set area 0
   # number of vertices:
   set n [expr {([llength $coords]-4)/2}]
   # build lists with x and y coordinates only:
   foreach {x y} $coords {
      lappend xList $x
      lappend yList $y
   }
   for {set i 1; set j 2; set k 0} {$i <= $n} {incr i; incr j; incr k} {
      set area [expr {$area + ([lindex $xList $i] * ([lindex $yList $j] - [lindex $yList $k]))}]
   }
   return [expr {$area/2.0}]
 }

This procedure may seem slooow but trying it I got the area of a polygon with 2100 vertices in 0.0037 seconds on a 800MHz computer.

The algorithms takes care of holes. Try this polygon (.c is a canvas widget):
  .c create polygon 0 0 100 0 100 100 50 100 50 75 75 75 75 25 25 25 25 75 50 75 50 100 0 100
It has a hole inside (how sad, that independant holes are not suported by Tcl, we can only fake them here). The area is 7500. Without the hole
  .c create polygon 0 0 100 0 100 100 0 100
the procedure returns 10000. So the hole is treated correctly as not belonging to the inside of the polygon.
----
'''The distance between two points'''

This is trivial when you have a cartesian coordinate system. Yust use Phythagoras' law. But in applications with geographical data, the distance must be calculated on a sphere in the simplest case. This is what the following procedure does:
 # calculates the distance between two points on a sphere.
 # The result is the distance on the great circle in Meters
 # x1=longitude 1, y1=latitide 1, x2=longitude2, y2=latitude 2 - all given in decimal degrees
 proc distance {x1 y1 x2 y2} {
    set pi 3.1415926535
    # convert degrees to radians:
    set x1 [expr {$x1 *2*$pi/360.0}]
    set x2 [expr {$x2 *2*$pi/360.0}]
    set y1 [expr {$y1 *2*$pi/360.0}]
    set y2 [expr {$y2 *2*$pi/360.0}]
    # calculate distance:
    set d [expr {acos(sin($y1)*sin($y2)+cos($y1)*cos($y2)*cos($x1-$x2))}]
    # return distance in meters:
    return [expr {20001600/$pi*$d}]
 }
Normally, d will be the distance measured in radians. The last expr is needed to translate the value to meters. It is the same as:
    return [expr {180*60.0/$pi*$d*1852}]
Here, 1852 is the number of meters that go into one nautic mile. By using other factors, you can get the result in other units.
----

See also:
   * [Convex hull]
   * The [Geometry] module in Tcllib
   * [Regular polygons]
----
[Category Mathematics]