Seeing the Symmetric Difference

Year: 2020 Authors: Bruce F. Torrence

Core claim

Symmetric difference applied to simple symmetric shape arrangements can generate intricate, aesthetically rich images, and modern software makes these constructions easy to compute.

Topics

symmetric difference, planar regions, geometric symmetry, computational geometry

Domains

set theory, Boolean operations, polygonal curves, discrete geometry, generative art, geometric design, visual patterning, algorithmic aesthetics

Methods

overlaying regions, polygonal approximation, edge intersection computation, triangulation

Media

equilateral triangles, translucent disks, squares, hypotrochoid curve

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2020 Conference Proceedings

Seeing the Symmetric Difference

Bruce F. Torrence

Dept. of Mathematics, Randolph-Macon College, Ashland, Virginia USA; btorrenc@rmc.edu

Abstract

We visually explore the symmetric difference set operation applied to symmetric arrangements of simple planar regions. Fast algorithms for performing this operation on regions bounded by polygonal curves are widely available, making it a practical tool for the mathematically inclined artist.

The Symmetric Difference

Given two sets $A$ and $B$ , their symmetric difference $A\oplus B$ comprises all elements that belong to exactly one of the given sets. More formally: $A\oplus B=(A\cup B)-(A\cap B)$ . This simple operation is commutative and associative, so it may be unambiguously applied to any finite collection of sets. In general, an element belongs to $A_1\oplus A_2\oplus \cdots \oplus A_n$ precisely if it belongs to an odd number of the $A_i$ [3]. Venn diagrams for the symmetric difference of two, three, and four sets are shown in Figure 1.

Figure 1: Venn diagrams for the symmetric difference of two sets, three sets, and four sets.

The complexity of rendering the symmetric difference of a large collection of planar regions can be illustrated by imagining each region as, say, a translucent disk. Overlapping regions become darker as more layers are added, and each subregion is shaded according to how many layers it belongs to. Reducing these numbers of layers modulo two gives the symmetric difference, where 1 indicates a point belongs to the symmetric difference, and 0 indicates that it does not. See Figure 2.

Computation

While it is simple for a vector graphics program to overlay translucent regions, it is quite another matter to identify the boundary curve enclosing each connected subregion of a particular shade. This is precisely what is required for effective computation of the symmetric difference. Recent advances in algorithms for computing the symmetric difference (see, e.g., [1, 2]) have resulted in fast, robust software. Matlab, Mathematica, OpenSCAD, and most CAD programs can now compute symmetric differences of discretized planar regions, that is, regions enclosed by one or more polygonal curves.

Torrence

Figure 2: Left: Seven translucent disks. Middle: Symmetric difference of seven disks. Right: Mathematica’s symmetric difference operator applied to seven disk-shaped regions.

The rightmost image in Figure 2 illustrates how Mathematica’s symmetric difference operator computes the symmetric difference of the seven disks. First, each disk is approximated by a polygon with a few hundred edges. The vertices on the polygonal paths forming the boundaries of the disks are shown (you will need to zoom in on the PDF to see them). The algorithm then computes every point where a pair of edges from two paths cross, and adds these to the collection of vertices. Finally, the solid regions appearing in the symmetric difference are triangulated to fill them out.

Innovation in algorithms for the computation of Boolean set operations has been driven by applications. For example, in fused deposition modeling, the slicing of a model before it is 3D printed breaks the model into horizontal layers. Each layer is a planar region whose outline is the toolpath for the extruder. The difference of the regions in two adjacent layers indicates portions of the print that will be unsupported—there will be an overhang with no material underneath this portion of the print. Slicing software increasingly uses these region differences to automatically flag such potential problem areas. Another application uses aerial photographs to model ice sheets. The symmetric difference can be used to highlight the areas where an ice sheet has changed over time [2].

Symmetric Symmetric Differences

Our interest in the symmetric difference is driven not by such practical applications, but rather by the geometric beauty and complexity inherent in the operation when applied to a symmetric arrangement of simple shapes—a symmetric symmetric difference. For instance, Figure 3 shows the symmetric difference of an arrangement of five equilateral triangles, each obtained from the next by rotation through $2\pi /5$ about a common point. The intricacy of the resulting figure belies the simplicity of its construction.

Of course, we could arrange copies of any figure uniformly around a circle and take their symmetric difference. So let us take, say, three copies of the entire five-triangle structure shown in Figure 3, each copy obtained from the next by rotation through $2\pi /3$ about a common point. The symmetric difference of the three sets is really just the symmetric difference of a particular arrangement of $3\times 5=15$ identical equilateral triangles. This is an immediate consequence of associativity. Figure 4 shows the kaleidoscopic result under three different choices for the center of rotation.

Figure 5 shows the symmetric difference of 10 copies of the structure in Figure 3 rotated about a common point, making it a symmetric difference of an arrangement of 50 identical equilateral triangles.

Another method for creating a symmetric arrangement of simple figures begins with a parametric curve, such as the seven-lobed hypotrochoid shown in the center of Figure 6. The domain for this curve is evenly

Seeing the Symmetric Difference

Figure 3: Symmetric difference of five equilateral triangles. One of the five triangles is outlined on the right; the others are obtained by rotating it through multiples of $2\pi /5$ about the indicated point.

Figure 4: Each image shows the symmetric difference of 15 identical equilateral triangles. Three copies of the structure in Figure 3 are rotated through $2\pi /3$ , with three different centers of rotation.

Figure 5: Left: Symmetric difference of 50 identical equilateral triangles. The structure in Figure 3 is rotated through multiples of $2\pi /10$ about a common point. Right: Close-up of center.

Torrence

partitioned into many small subintervals. The center of a square is then placed on the curve at each of the points determined by the partition, so that one diagonal of the square is tangent to the curve. We then take the symmetric difference of all of these squares.

We chose to place 63 squares along the curve to produce the image on the left in Figure 6, while 28 squares were used to produce the image shown on the right. These choices, together with the size of each square, are purely aesthetic. The size of the squares used for these images is shown in the center panel. Noting that $7\times 9=63$ , each lobe of the curve on the left gets 9 squares. Each lobe of the curve on the right gets 4 squares. Whenever the total number of squares is a multiple of 7, a square will be placed at each of the points on the curve farthest from its center; if the total number of squares is an even multiple of seven, a square will also be placed precisely at each of the seven points on the curve closest to its center (an example of each type of square is shown in the center of Figure 6). Thus the parity of the number of squares placed on each lobe has a tangible visual effect on the central region of the resulting image.

Figure 6: A symmetric difference of 63 squares (left) and 28 squares (right). Squares are placed with their centers on the seven-lobed curve (middle) with one diagonal tangent to the curve.

Summary and Conclusions

Simple arrangements of simple shapes, when viewed through the lens of the symmetric difference operator, can reveal intricate symmetries and stunning patterns. Our examples illustrate just a few of the myriad possibilities for creating imagery with this tool. Fast, robust, and accurate implementations of the symmetric difference operation make its use easier than ever.

References

[1] M. Gaspar. “A procedure for computing the symmetric difference of regions defined by polygonal curves.” Journal of Symbolic Computation, vol. 61–62, 2014, pp. 53–65. https://www.sciencedirect.com/science/article/pii/S0747717113001272. [2] F. Martínez, A. J. Rueda, and F. R. Feito. “A new algorithm for computing Boolean operations on polygons.” Computers & Geosciences, vol. 35, no. 6, 2009, pp. 1177–1185. https://www.sciencedirect.com/science/article/pii/S0098300408002793. [3] C. Woo. “Symmetric difference on a finite number of sets.” Planet Math, 2013. https://planetmath.org/symmetricdifferenceonafinitenumberofsets.