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:
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. [L1 ]. I remember that someone presented a Tensor package at the last Tcl conference (OSCON'2001 San Diego [Refer to wiki page of this one]. 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":
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 {...}}Some notes:
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
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:
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:
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).
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:
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.
Category Graphics - Category Mathematics