''For '''geometry''' in relation to Tk windows, see [wm geometry], [winfo], and [geometry managers].''
----
[Arjen Markus] This page will describe the geometry package Christian Heide Damm started and that we are now developing in cooperation.
The idea is simple - define points, vectors, planes, lines, line segments and so on via "qualified" lists. Define operations on these lists like, calculate the distance between points, project a line on a plane.
Such a package is useful for applications involving interactive design/drawing, "CAD"-like applications, ...
The page should describe:
* What objects do we want?
* Representation of these objects as lists
* Operations on these objects
''[Lars H], 2008-11-04: Did anything ever come out of this? There doesn't seem to be a link to any code.''
----
[AK]: Conversions of such objects into other formats ? POVRay for example ? Is the stuff 2D or 3D ?
[Arjen Markus] At the moment: we simply want to outline the functionality, but conversions may become a part of that! Thanks for the suggestion. The ideas should not be limited to 2D or 3D, but be (as far as practical) independent of the number of dimensions. (The daring among us can then use it for multidimensional data analysis).
[AK]: Regarding multidimensional data analysis ... There is a linear algebra package out there. By Hume Integration Ltd. [http://www.hume.com/la/index.html]. I remember that someone presented a [Tensor] package at the last Tcl conference ([OSCON 2001] San Diego). Could also tie into [tcllib]/[matrix].
Regarding conversions note that I am working on a module to read and write FIG streams. See http://www.xfig.org/ . I have the basic functionality ready, but want to add a more convenient layer on top.
[Arjen Markus] Interesting, can you send me some specifications?
[AK] Sure, when I am home again.
----
The geometry package should include the following types of "objects":
* ''point'' - characterised only by its coordinates
* ''vector'' - ditto, conceptually quite different from a point object
* ''line'' - a straight, infinite line through a point along some vector
* ''plane'' - a flat surface passing through a point and perpendicular to a certain vector (the normal)
* ''linesegment'' - a straight piece of a line, between two points. [AK]: Note alternate representation by starting point and a length vector.
* ''polyline'' - a set of connected linesegments, therefore defined by two or more points. (actually a linesegment is two-point polyline). [AK]: Alternate representation by starting point and list of vectors from point to next point.
* ''sphere'' - characterised by a point (the centre) and the radius
* ''wireframe'' - a set of linesegments not necessarily connected
* ''pointset'' - a set of points without any ordering
There could be more types, such as a ''prism'' to characterise, say, a rectangular block or a solid body defined by ''faces'' (a ''facetted'' body). The above list is, however, quite enough to get started.
----
The internal representation of, say, a point is very simple: A point is a list like
{POINT {...}}
where "POINT" indicates the type and the second element is a list of coordinates. This second element can contain any number of coordinates, the number defining the dimension of the space in which it exists.
For vectors we then have:
{VECTOR {...}}
and for lines:
{LINE {POINT {...}} {VECTOR {...}}}
A plane is defined likewise:
{PLANE {POINT {...}} {VECTOR {...}}}
''[Lars H], 2008-11-04: Added some right braces which I presume were missing (examples weren't balanced). However, it seems below that the innermost brace groups were later dropped, making it `{POINT 1 2 3}` rather than `{POINT {1 2 3}}`.''
Some notes:
* By using ordinary variables to store these lists, we do not have to worry about cleanup procedures. The geometrical objects exist as long as the variables exist.
* Both planes and lines should preferrably contain a ''normalised'' vector, rather than an arbitrary one. This will make calculations much simpler.
To illustrate the use, consider the following fragment (namespaces have been left out deliberately):
set point1 [point {1 1 1 1}]
set point2 [point {1 2 1 -1}]
set plane1 [plane $point2 [vector {1 0 3 1}]]
puts "Distance between the points: [calculateDistance $point1 $point2]
puts "Distance between point and plane: [calculateDistance $point1 $plane1]
In the calculation of the distance between two points, the euclidean distance is chosen. In the calculation of the distance between the point and the line, the formula below is useful:
distance = | (''p1'' - ''p2'').''v1'' |
where:
''p1'' - the vector from the origin to point1
''p2'' - the vector from the origin to point2
''v1'' - the vector normal to the plane (with length 1, hence normalised)
''x''.''y'' - the inproduct of two vectors
|.| - the absolute value
We can easily calculate the orthogonal projection of the point (point1) on the plane:
''p3'' = ''p1'' - distance * ''v1''
or the reflection of the point:
''p3'' = ''p1'' - 2 * distance * ''v1''
----
'''Special cases: 2D and 3D space'''
For drawing applications, 2D objects will be most important whereas computer aided design applications will focus on 3D objects (or, if so-called homogeneous coordinates are used, 4D objects).
Some methods are specific to 2D or 3D:
* Determining a bounding box is typical for 2D graphics
* Determining the outproduct of two vectors can only be done in 3D
Of course generalisations are possible, but they occur at a price: more parameters are involved (bounding boxes in 3D become bounding blocks or you need three vectors in 4D space to almost uniquely define the perpendicular vector as with a 3D outproduct).
For these special cases, additional methods should be available.
----
[JCW] - The {POINT {...}} etc. notation is gorgeously clean and simple, but how would you deal with representations, other than Tcl lists? Suppose the data is a memory range with consecutive floats (that what C would call an array), how do you deal with it without conversion? If there is always conversion, then this requires far mor memory during use and rules out memory mapped files as mechanism... :o(
Or is there a way to get the best of both worlds? (I'm referring to [VKIT], in which I try to find a middle ground)
[AK]: As a side note this way of constructing type-tagged data is shown in [SICP]. They also have things to say about varying representations of the same thing. Their example are complex numbers in (x,y) and polar representation (angle,length). This is of course also a way to represent vectors.
[Arjen Markus] Well, I have contemplating using the same notation for rational and complex numbers, but it does seem to work best when the amount of associated data is fairly small.
----
The geometry module should include:
* Orthographic projection from 3D to 2D
* Stereographic projection from 3D to 2D (perspective drawing)
This will facilitate drawing real-life objects, such as when you use XFIG to create nice but flat pictures of the real world.
(After a first look at Andreas' work on XFIG, I would say that the package we are designing should be more than adequate to represent the vector objects in drawings. This was the main interest if I am not mistaken of Christian as well).
----
(See also [Playing 3D])
----
[Arjen Markus] On the page [Power set of a list] I mentioned my reasons for being interested in the set of subsets of a given size. I thought it might be one step in solving a problem concerning solids defined like this:
x >= 0
y >= 0
z + x >= 0
x + 2y +3z <= 10
We have four halfspaces (or any number of halfspaces in any number of dimensions), but how can we determine if they together form a finite volume? Clearly, one needs at least N+1 such halfspaces, if N is the dimension of the space we are looking at.
My conjecture for solving this problem is that if we can find a subset of N+1 halfspaces from all the given halfspaces (say M > N) that have the following relation, then the volume defined by all M halfspaces is either empty or it is finite. The condition:
* N of these halfspaces form an (non-orthogonal) basis, where the normal vectors pointing into the halfspaces are the basis vectors.
* The remaining halfspace has a normal vector (same definition for the orientation), such that all coordinates as expressed in the above basis are negative.
This can be seen as something quite reasonable, if you just take three lines in the 2D plane, like x>=0, y>=0 and x+ay>=0 (a varying).
I have not tried to prove it, it is slightly more than a hunch.
----
I could make use of a procedure to change the point of view of the observer in 3d space.
I am using the [Playing 3D] code (sans Easter egg demo) as follows:
I needed some visualization software that I could use to develop terrain algorithms for a large scale real world simulation. My first task was to construct a line segment simplification algorithm which starts with a set of points representing a valley or ridge on a mountain and find the smallest number of these points such that line of sight calculations would still be accurate within a pair of horizontal and vertical tolerances.
I began with the Playing 3d demo, removed the Easter egg code, kept most of the bindings, and added some code to generate random connected line segment test data. Then I run my simplification routine (written in C code and exec'd by TCL to write a text file) and display the results using these 3d routines. By rotating the 2 line segments together in space, I can visually see if my line simplification has any gross errors.
I would like to be able to change the viewpoint of the observer, with a statement like:
3d'observer x y z
but I am not graphics-savvy enough to know how to implement this.
But this would be really cool as a way to generate an animation script which could "fly" around a model.
et
----
2006-03-04
About plane definition by [Arjen Markus]:
''plane'' - a flat surface passing through a point and perpendicular to a certain vector (the normal)
In general case this "plane" object is not 2D-surface but has (N-1) dimension. Where N = point coordinates number (=task dimension). For above example:
To illustrate the use, consider the following fragment (namespaces have been left out deliberately):
set point1 [point {1 1 1 1}]
set point2 [point {1 2 1 -1}]
set plane1 [plane $point2 [vector {1 0 3 1}]]
puts "Distance between the points: [calculateDistance $point1 $point2]
puts "Distance between point and plane: [calculateDistance $point1 $plane1]
#find objects dimensions:
puts "task dimension = [dim]"
% task dimension = 4
puts "points dimension = [$point1 cget -dimension]"
% points dimension = 0
puts "lines dimension = [[line $point2 [vector {1 0 3 1}]] cget -dimension]"
% lines dimension = 1
puts "planes dimension = [[plane $point2 [vector {1 0 3 1}]] cget -dimension]"
% planes dimension = 3
puts "spheres dimension = [[sphere $point1 10] cget -dimension]"
% spheres dimension = 3
const mech
----
[AM] (2 november 2008) While experimenting with [Snit], I came up with the following toy program:
======
# geom_objs.tcl --
# Experiments with geometrical objects and transformations
# Goal:
# Explore the facilities of Snit
#
# Note:
# Geometrical objects are represented as a tagged list,
# e.g. {POINT 1.0 2.0} for a point in 2D space and
# {LINE {POINT 1.0 2.0 3.0} {POINT 2.0 0.0 1.0}}
# for a line in 3D space
#
package require snit
# inproduct --
# Compute the inproduct of two vectors
# Arguments:
# first First vector
# second Second vector
# Result:
# Inproduct
#
proc inproduct {first second} {
set result 0.0
foreach f $first s $second {
set result [expr {$result +$f*$s}]
}
return $result
}
# transform --
# Type defining an (affine) transformation
#
::snit::type transform {
option -transformbefore -default {}
option -affine -default {}
# applyto --
# Method to transform the coordinates
# Arguments:
# objs Single geometrical object or a list of such objects
#
# Result:
# Objects with adjusted coordinates
#
method applyto {objs} {
if { $options(-transformbefore) != {} } {
set objs [$options(-transformbefore) applyto $objs]
}
if { [llength [lindex $objs 0]] == 1 } {
set result [$self transform $objs]
} else {
set result {}
foreach obj $objs {
lappend result [$self transform $objs]
}
}
return $result
}
# transform --
# Actually transform the coordinates
#
# Arguments:
# obj Single geometrical object
#
method transform {obj} {
set type [lindex $obj 0]
if { $type == "POINT" } {
set coords [concat [lrange $obj 1 end] 1.0] ;# Homogeneous coordinates!
set newcoords {}
foreach row $options(-affine) {
lappend newcoords [::inproduct $row $coords]
}
return [concat POINT $newcoords]
} else {
set result $type
foreach point [lrange $obj 1 end] {
lappend result [$self transform $point]
}
return $result
}
}
# after --
# Create a new transformation by applying one after the other
# Arguments:
# other The transformation that is to be applied first
# Result:
# Object representing a combined transformation
#
method after {other} {
set new [transform %AUTO%]
$new configure -transformbefore $other -affine $options(-affine)
return $new
}
# translate --
# Set the transformation to be a translation
# Arguments:
# x Displace over x
# y Displace over y
# z Displace over z
# Result:
# None
#
method translate {x y z} {
set options(-affine) [list [list 1.0 0.0 0.0 $x] \
[list 0.0 1.0 0.0 $y] \
[list 0.0 0.0 1.0 $z]]
}
}
# main --
# A small test
#
set p0 [list POINT 0.0 0.0 0.0]
set p1 [list POINT 1.0 1.0 1.0]
set p2 [list POINT 0.0 -1.0 -1.0]
set line [list LINE $p1 $p2]
set trans1 [transform %AUTO%]
set trans2 [transform %AUTO%]
$trans1 translate 0.0 0.0 1.0 ;# In z-direction
$trans2 translate 0.0 1.0 0.0 ;# In y-direction
set combined [$trans1 after $trans2]
puts "Successive translations: "
puts "Origin is translated to: [$trans1 applyto [$trans2 applyto $p0]]"
puts "Combined transformation: "
puts "Origin is translated to: [$combined applyto $p0]"
puts "Combined transformation on line: $line"
puts "Result: [$combined applyto $line]"
======
https://github.com/nico-robert/tomato%|%tomato math::geometry%|% is an geometry 3D library with basics functions for working in 3D
space...
<<categories>> Graphics | Mathematics