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.
See also: