Version 6 of Geometry

Updated 2002-01-09 11:08:11

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

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).

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
  • polyline - a set of connected linesegments, therefore defined by two or more points. (actually a linesegment is two-point polyline)
  • 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.

Category Mathematics 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:

  • 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.

Category Graphics