Of Operators and Ribbons

Bruno Autin

CERN, 1211 Genve 23 (Switzerland)
autin@cernvm.cern.ch

Abstract

List processing in the Mathematica programming language can be viewed as an apllication of the theory of sets where sets take the form of lists. The operators play then a fundamental role in list creation, in the reduction of a set of lists to a single one and in transforming the elements of a list by mapping or the name of lists by application. The power and elegance of this style of programming may sometimes be hard to grasp because of the needed effort of abstraction. Geometry is conceptually as abstract as any other field of mathematics but, at least, figures can be seen whereas numbers and symbols are left to imagination. Operations such as inner and outer products which are usually confined to the field of tensor calculus are demystified and used in the entirely different context of lines and grids. The construction of ribbons as an example of list manipulation is discussed in detail and is concluded by an animation of patterns produced by interlacing ribbons of variable widths.

Introduction

One of the most appealing aspects of Mathematica [1] lies in the way operators are manipulated as objects independent of the arguments that they are supposed to act upon. It is however hard in practice to convince new users to think of a function as made of two distinct elements, say f and x when they have been educated in grouping f and x in a single entity f(x); we call this habit the f(x) syndrom. What is proposed in this paper is to help converting the new and perhaps also the advanced user to the manipulation of operators by illustrating the method with geometric examples. 
In the Euclidean approach to geometry, the basic objects are the point, the straight line, the circle, the open line made of a sequence of concatenated segments, the polygon and the conics. In the program Descartes-Geometry [2], those objects are, with scalars, the only possible output from any command of the program and the only, with Mathematica graphics directives, to be understood by the general purpose drawing command Draw which is to geometric objects what Plot is to scalar functions. The associated operators are written in capital letters to avoid any interference with Mathematica operators of same name.
The discussion is focused towards a few very general Mathematica operators. Generators of lists are first studied by comparing Array and Outer and creating grids of points. List generation is an inflationist process; other processes reduce a set of lists to a single list or a single new object; in this context, the connection between Thread and Inner is shown and exploited to generalize Inner to more than two lists; the interest of Thread is emphasized by assigning the attribute Listable to several geometric operators and the generalized Inner used to create 3D lines. The transformation of lists with reordering of the elements is applied to the design of polygonal ribbons and the various steps of the geometric construction are integrated with FoldList for a later animation. Last,  patterns of interlacing ribbons are proposed as an aesthetical entertainment.

The operators of Descartes-Geometry

The basic operators that will be considered are POINT, STRAIGHT, LINE and POLYGON. Their definition cannot escape the f(x) syndrom. We shall see later how to give them attributes which generalize their action to lists.
POINT is a rewriting of the Mathematica graphics primitive Point but instead of acting on a list of two coordinates, the argument is a sequence of two or three coordinates: POINT[x,y] or POINT[x,y,z] . 
STRAIGHT expects three arguments: the coefficients u, v, w of the cartesian equation 
u x + v y + w = 0 of a straight line. It often results  from a Euclidean definition: straight line passing through two points (StraightByPoints) or parallel to another straight line (StraightParallel).
LINE and POLYGON are operators attached to line and polygon made of an arbitrary sequence of segments: 
            LINE[POINT[x1,y1],POINT[x2,y2],...],       
            POLYGON[POINT[x1,y1],POINT[x2,y2],...]. 
Draw draws all the geometric objects interleaved with any Mathematica graphics directive. The file which contains the geometry program Geometry2D.m is located in the subdirectory Descartes of the Mathematica directory Packages, it is thus called with

<<Geometry2.0.m

List generators

List generation is discussed with Array and Outer. Array generates an array of objects by applying an operator to dummy iterators which vary in the range ((1,m),(1,n)) for a 2D array of dimensions m*n:

pt1= Array[POINT,{5,5}]

Here the points have integer coordinates and the increment of the iterators is 1. Another way of getting the same array is given by

Outer[POINT,Range[5],Range[5]]

where Range[5] is the list of the five first integers. The operator Outer has a specific interest when the lists are arbitrary

abs={3.92218, 2.15235,0.31039, 0.0260667, 4.08392};
ord={2.58202, 4.32055, 0.685766, 1.9535, 3.80322};
pt2=Outer[POINT,abs,ord]

Extension to spaces of dimension higher than 2 is staightforward both in Array by increasing the number of dummy iterators and in Outer by letting the operator act on an arbitrary number of lists. By mapping the application of LINE to pt1 and pt2, we can see the order of generation of the points and observe that the grouping is made by concatenation of the points of same abscissa.

lin1=Map[LINE@@#&,pt1]
lin2=Map[LINE@@#&,pt2]

The two sets of points connected by lines are represented in Fig.1. In order to compare the elements built with Array and Outer, the list {pt2,lin2} is translated by 6 units to the right by applying the translation operator Shift[POINT[6,0]] to it. This technique is more efficient than using GraphicsArray. It also illustrates a functional operator (Shift), i.e. an operator which depends on a variable (the translation vector).

Draw[Blue,lin1,PointSize[.015],pt1,
     Red,Shift[POINT[6,0]]/@{lin2,pt2}]

-  a  -                                                                  -  b -
 Fig.1: Points generated with Array (a) and Outer (b)

Contraction operators

The contraction operators collect several input lists into a single list (Thread) or a single new object (Inner).

Thread

Thread bridges the elements of same position in two or more lists of same length with a given operator

pt3=Thread[POINT[abs,ord]];
Draw[PointSize[.015],Red,pt3]

Fig.2 Illustration of Thread

In fact, some of the lists may be replaced by a scalar in which case Thread considers the scalar as a list of identical elements equal to the scalar.
The object POINT has been defined with two scalar arguments: the abscissa and the ordinate. The definition can be extended to list arguments by assigning the operator the attribute Listable which makes the Thread operation automatic each time the arguments are lists.

SetAttributes[POINT,Listable]
POINT[abs,ord]

This property of listability is so useful that we attribute it  right away to the operators which will be used in ribbon design:

SetAttributes[#,Listable]&/@
{proj,StraightByPoints,StraightParallel,Intersections};

Inner

Inner is usually presented as the generalization of the scalar product where the first  and second operators play the role of Times and Plus respectively and the classical example is the divergence of a function. Here, we show how it is connected to Thread and treat the example of a line passing through a sequence of points .

lin3=Inner[LINE,abs,ord,POINT];
Draw[Red,PointSize[.015],pt3,lin3]

Fig. 3 Illustration of Inner

It is clear that Inner can be decomposed into two operations: the creation of the list pt3 and the replacement of the head List by LINE.

lin3bis=LINE@@Thread[POINT[abs,ord]]

Seen from this viewpoint, Inner can be generalized to more than two lists since Thread accepts an arbitrary number of  arguments.

Unprotect[Inner]
Inner[op1_Symbol,lists__,op2_Symbol]:=
 op1@@Thread[op2[lists]]
Protect[Inner]

Let us create a list of the altitudes of the points

alt={3.86499, 0.452121, 0.0697197, 4.02283, 4.79287};

and construct an inner product with three lists

lin4=Inner[LINE,abs,ord,alt,POINT]

The Descartes-Geometry3D program is only available in β-version and permits the following command

Draw[Thickness[.015],lin4]

Fig.4 Illustration of a generalized form of Inner

The previous example has been chosen to illustrate a generalized Inner product; it is however somewhat academic since lin4 could have been defined as

lin4bis=LINE@@POINT[abs,ord,alt]

since POINT is "listable".

RotateLeft, RotateRight, Reverse and the waltz of parallel lines recorded in FoldList

The construction of ribbons will serve as an example of manipulation of lists with RotateLeft, RotateRight, Reverse and Join. Then all the phases of the construction will be integrated in FoldList to restitute the film of the various operations.

RotateLeft and RotateRight

The name of the operators RotateLeft  or RotateRight is well chosen when one imagines the elements of a list on a circle; the image of a list is however more a vertical line than a circle and one may have some trouble to see the correspondence between the list and the rotated list especially at the ends

- a -                                                 - b -
   
Fig.5 Effect of RotateLeft (a) and RotateRight (b) on a same list

Parallel polygons

When all the segments of a polygon P are parallel to and at a distance d from all the segments of a polygon P0, P is parallel to P0 and at the distance d from it. All the parallels will be constructed with the Descartes-Geometry command StraightParallel[m,d] which returns the straight line passing through the point m and parallel to the straight line d.  
The first step consists of creating a function which generates the point m whose projection is A1(a1,b1) onto the segment A1A2, the coordinates of A2 being (a2,b2) and the distance from m to A1 being d. It is not hard to show that the function proj defines such points m

proj[POINT[a1_,b1_],POINT[a2_,b2_],d_]=
POINT@@(
 {a1    ,b1   }+
 {-b2+b1,a2-a1}d/Sqrt[(a2-a1)^2+(b2-b1)^2]
       );

The polygon P0 is made of a sequence of points which can be converted to a list called l1.

l0=Inner[POLYGON,{0,1,1/2},{0,0,1},POINT]
l1=List@@l0

To get all the representations of the straight lines defined by two consecutive points of P0 it is convenient to define a second list l2 deduced from l1 by application of RotateLeft and the two lists will automatically be "threaded" with the Descartes-Geometry operator StraightByPoints which has been made listable.

l2=RotateLeft[l1];
l3=StraightByPoints[l1,l2]

To define the list of the points m, the same procedure is valid but a peculiarity is to be noted: the third argument is a scalar, not a list.

l4=proj[l1,l2,.1]

The parallel straight lines are then given by

l5=StraightParallel[l4,l3]

The points of the parallel polygon P are the intersections of two consecutive of the previous straight lines. The list l5 is then replicated with RotateRight and the threading mechanism is continued with the Descartes-Geometry "listable" operator Intersections.

l6=RotateRight[l5];
l7=Intersections[l5,l6]

One option would be to apply POLYGON to l7 and the parallel polygon would be completed. A second, more sohisticated option which leads to a further exploration of list manipulation, consists of defining a ribbon. A first polygon is obtained by joining l1 to the Reverse of l7 and applying POLYGON to the result

p1=POLYGON@@Join[l1,Reverse[l7]]

This polygon alone would be an open ribbon; to close the ribbon, we add the quadrangle formed by the first point of P0, the first point of P, the last point of P and the last point of P0.

p2=POLYGON[First[l1],First[l7],Last[l7],Last[l1]];
rib=Join[p1,p2]

Note that Join is applied to POLYGON and not to List objects. At this point, it is necessary to summarize the various steps of the construction of a ribbon.

Illustrating a construction with FoldList

We have met inflationist and contraction operators, FoldList is an integration operator which creates a list whose each element differs from the previous one by one characteristic specified by a generating operator. The application to the animation of a geometric construction is of obvious interest. The generating operator is then Show and the list that Show will fold is made of graphics produced by Draw. Here, the first element is the triangle l0 and the following elements are the points m (l4), the points of P (l7), the first (p1) and second (p2) polygon of the ribbon.

graph1=
FoldList[Show,
Draw[Red,PointSize[.02],l0,DisplayFunction->Identity],
Draw[Red,PointSize[.02],#,
     Fill->True,
     DisplayFunction->Identity]&/@{l4,l7,p1,p2}
]

Graphics are not displayed to avoid confusion between those produced by Draw and those resulting from the folding which are unveiled and enhanced by addition of a background in the next command

Show[GraphicsArray[graph1],Background->Yellow]

Fig.6 Construction of a triangular ribbon

The list of graphics which has been produced is ready for animation.

Interlacing ribbons

Ribbons can generate a great variety of patterns depending on the complexity of the original polygon and of its width. All the statements defined in the previous section can be collected in a single function

Ribbon[POLYGON[u__],d_]:=
Block[{l1={u},l2,l3,l4,l5,l6,l7,p1,p2},
l2=RotateLeft[l1];
l3=StraightByPoints[l1,l2];
l4=proj[l1,l2,d];
l5=StraightParallel[l4,l3];
l6=RotateRight[l5];
l7=Intersections[l5,l6];
p1=POLYGON@@Join[l1,Reverse[l7]];
p2=POLYGON[First[l1],First[l7],Last[l7],Last[l1]];
Join[p1,p2]]

Descartes-Geometry has a command RegularPolygon which returns a list of convex or stellated regular polygons built on two points. The reason for the list lies in the possible degeneracy of stellated polygons into simpler polygons; a stellated hexagon is identical to two triangles for example. Let us play with a stellated heptagon built on the points (0,0) and (1,0) and whose vertices (1,4,7,3,6,2,5) are joined sequentially. In the RegularPolygon command, the first two arguments are the base points, the third argument is the number of sides and the last one  is the stellation order s (s-1 is the number of vertices skipped in the concatenation).

hepta=Sequence@@(
RegularPolygon[POINT[0,0],POINT[1,0],7,3]//N//Chop)

We got rid of the head List by applying Sequence. The numerical evaluation is necessary to speed up the calculations and Chop reduces to zero tiny numbers related to numerical approximation. The next command creates a film of twenty graphs which show the evolution of the ribbon pattern with an increasing widths. The film is presented on the diskette. To condense all the views in a graphics array, Shift could be used but, as an alternative, it is shown how an array can be partitioned (Partition) in sub-lists of five views to be inserted into GraphicsArray.

graph2=
Array[Draw[Hue[.15],Ribbon[hepta,-#/40],
           Fill->True,Background->Hue[.92,1,.9]]&,
      20]
Show[GraphicsArray[Partition[graph2,5]]]

Fig.7 Color patterns of interlacing ribbons with increasing widths

What has been done for color graphics is repeated for black and white graphics:

graph3=
Array[Draw[Ribbon[hepta,-#/40],Fill->True]&,20]
Show[GraphicsArray[Partition[graph3,5]]]

Fig.8 Black and white patterns of interlacing ribbons with increasing widths

In contrast with Mathematica, a polygon is not automatically painted in Descartes-Geometry. In the present case, the mosaic character of the patterns can only be rendered if the option Fill->True is specified and because the intersection of two painted polygons has the color of the background. What has been done for the heptagon can be repeated with any polygon whether it be regular or not. The interlacing ribbons were used with a great virtuosity by the Celts and the Arabs to produce sophisticated decorations. Now, with tools such as Mathematica and Descartes-Geometry, a new realm is open to imagination in the field of those wonderful techniques that were mosaic, miniature decoration, paving or marquetry.

References

[1] R.Maeder, Programming with Mathematica, 2-nd edition, AddisonWesley (1991)
[2] D.Monasse, Descartes-Geometry, Mathsoft Overseas, Geneva (1992)

Biography

Bruno Autin is a senior physicist at CERN, the European Laboratory for Particle Physics located near Geneva (Switzerland). He pioneered the symbolic computing methods in particle accelerators when he designed the lattice of the Antiproton Accumulator in 1977, a machine which became famous with the discovery of the intermediate bosons (Nobel prize awarded to C. Rubbia and S. Van der Meer in 1984). In 1988, during a sabbatical year at the Lawrence Berkeley Laboratory, he discovered Mathematica and used it extensively in his work on new lepton and hadron colliders. Back at CERN, he animates a forum of application of symbolic techniques in accelerator physics. With Denis Monasse and Sophie PerrŽard, he is coauthor of a book on Mathematica and Geometry to be released in  the fall of 1993.