How to compute the area of a polygon

If you know the vertices of a polygon, how do you compute its area? This seems like this could be a complicated, with special cases for whether the polygon is convex or maybe other considerations. But as long as the polygon is “simple,” i.e. the sides meet at vertices but otherwise do not intersect each other, then there is a general formula for the area.

The formula

List the vertices starting anywhere and moving counterclockwise around the polygon: (x1y1), (x2y2), …, (xnyn). Then the area is given by the formula below.

A = \frac{1}{2} \begin{vmatrix} x_1 & x_2 & \ldots & x_n & x_1\\ y_1 & y_2 & \ldots & y_n & y_1 \end{vmatrix}

But what does that mean? The notation is meant to be suggestive of a determinant. It’s not literally a determinant because the matrix isn’t square. But you evaluate it in a way analogous to 2 by 2 determinants: add the terms going down and to the right, and subtract the terms going up and to the right. That is,

x1 y2 + x2 y3 + … xn y1y1 x2y2 x3 – … –  yn x1

This formula is sometimes called the shoelace formula because the pattern of multiplications resembles lacing a shoe. It’s also called the surveyor’s formula because it’s obviously useful in surveying.

Numerical implementation

As someone pointed out in the comments, in practice you might want to subtract the minimum x value from all the x coordinates and the minimum y value from all the y coordinates before using the formula. Why’s that?

If you add a constant amount to each vertex, you move your polygon but you don’t change the area. So in theory it makes no difference whether you translate the polygon before computing its area. But in floating point, it can make a difference.

The cardinal rule of floating point arithmetic is to avoid subtracting nearly equal numbers. If you subtract two numbers that agree to k significant figures, you can lose up to k figures of precision. We’ll illustrate this by taking a right triangle with base 2 and height π. The area should remain π as we translate the triangle away from the origin, we lose precision the further out we translate it.

Here’s a Python implementation of the shoelace formula.

    def area(x, y):
        n = len(x)
        s = 0.0
        for i in range(-1, n-1):
            s += x[i]*y[i+1] - y[i]*x[i+1]
        return 0.5*s

If you’re not familiar with Python, a couple things require explanation. First, range(n-1) is a list of integers starting at 0 but less than n-1. Second, the -1 index returns the last element of the array.

Now, watch how the precision of the area degrades as we shift the triangle by powers of 10.

    import numpy as np

    x = np.array([0.0, 0.0, 2.0])
    y = np.array([np.pi, 0.0, 0.0])

    for n in range(0, 10):
        t = 10**n
        print( area(x+t, y+t) )

This produces


Shifting by small amounts doesn’t make a noticeable difference, but we lose between one and two significant figures each time we increase t by a multiple of 10. We only have between 15 and 16 significant figures to start with in a standard floating point number, and so eventually we completely run out of significant figures.

When implementing the shoelace formula, we want to do the opposite of this example: instead of shifting coordinates so that they’re similar in size, we want to shift them toward the origin so that they’re not similar in size.

Related post: The quadratic formula and low-precision arithmetic

Drawing Spirograph curves in Python

I was looking back over an old blog post and noticed some code in the comments that I had overlooked. Tom Pollard gives the following code for drawing Spirograph-like curves.

import matplotlib.pyplot as plt
from numpy import pi, exp, real, imag, linspace

def spiro(t, r1, r2, r3):
    Create Spirograph curves made by one circle of radius r2 rolling 
    around the inside (or outside) of another of radius r1.  The pen
    is a distance r3 from the center of the first circle.
    return r3*exp(1j*t*(r1+r2)/r2) + (r1+r2)*exp(1j*t)

def circle(t, r):
    return r * exp(1j*t)

r1 = 1.0
r2 = 52.0/96.0
r3 = 42.0/96.0

ncycle = 13 # LCM(r1,r2)/r2

t = linspace(0, ncycle*2*pi, 1000)
plt.plot(real(spiro(t, r1, r2, r3)), imag(spiro(t, r1, r2, r3)))
plt.plot(real(circle(t, r1)), imag(circle(t, r1)))
fig = plt.gcf()

Tom points out that with the r parameters above, this produces the default curve on Nathan Friend’s Inspirograph app.

Related: Exponential sum of the day

Paul Klee meets Perry the Platypus

I was playing around with something in Mathematica and one of the images that came out of it surprised me.

filter contour plot

It’s a contour plot for the system function of a low pass filter.

    H[z_] := 0.05634*(1 + 1/z)*(1 - 1.0166/z + 1/z^2) /
            ((1 - 0.683/z)*(1 - 1.4461/z + 0.7957/z^2))
    ContourPlot[ Arg[H[Exp[I (x + I y)]]], 
                 {x, -1, 1}, {y, -1, 1}, 
                 ColorFunction -> "StarryNightColors"]

It looks sorta like a cross between Paul Klee’s painting Senecio

Senecio by Paul Klee, 1922

and Perry the Platypus from Phineas and Ferb.

Perry the Platypus from Phineas and Ferb

Area of a triangle and its projections

Let S be the area of triangle T in three-dimensional space. Let AB, and C be area of the projections of T to the xyyz, and xz planes respectively. Then


There’s an elegant proof of this theorem here using differential forms. Below I’ll sketch a less elegant but more elementary proof.

You could prove the identity above by using the fact that the area of a triangle spanned by two vectors is half the length of their cross product. Suppose ab, and c are the locations of the three corners of T. Then

S2 = v2/2,


v = (a – b) × (c – b)

and by v2 we mean the dot product of v with itself.

Write out the components of v2 and you get three squared terms. Notice that when you set the x components to zero, i.e. project onto the yz plane, the first of the three terms is unchanged and the other two are zero. In other words, the first of the three terms of v2 is A2. A similar argument shows that the other two terms are B2 and C2.


ASCII art diagrams

“Technology is additive.” — Kevin Kelly

Old technologies never die. Instead, their range of application shrinks. Or maybe it grows when conditions change.

ASCII art, drawing pictures with fixed-width plain text characters, is no longer how many people want to produce diagrams. Just fire up Adobe Illustrator and you get incomparably more resolution of expression.

And yet there are times when ASCII art comes in handy. You can, for example, paste it into source code files. Someone more familiar with Emacs than Illustrator may be able to produce a simple diagram in the former faster than the latter. And it can be relatively easy to programmatically produce a large number of ASCII art diagrams, depending on the nature of the diagrams.

It’s also possible to use ASCII art as a way to specify nicely rendered images. I’ll show how to do that with ditaa below.

Here’s an ASCII version of the conjugate prior diagram I made some time ago:


                          |             |
                          | Exponential |
                          |             |
                          lambda |                                                          
+-------------+           +-------------+           +-------------+
|             |   tau     |             |   lambda  |             |
|  Lognormal  |---------->|    Gamma    |<----------| Poisson     |
|             |           |             |---+       |             |
+-------------+           +-------------+   |       +-------------+
      |                         ^ ^         | beta
      |                   tau   | |         | 
      | tau                     | +---------+
      |                   +-------------+ 
      +------------------>|             |
                          |     Normal  |
                          |             |----+
                          +-------------+    | 
                                     ^       | mu
                                     |       |

And here’s the image produced by ditaa processing the ASCII diagram above:

Conjugate prior diagram produced by ditaa

Update: See my next post on how to create ASCII art diagrams and their graphic version from ditaa using Emacs org mode.

Update: When I first made the diagram above, I tried using Greek letters, e.g. using β rather than “beta,” but this didn’t work. I thought “OK, I suppose it’s not really ASCII art if you use non-ASCII characters.” But someone told me Unicode characters worked for him, so I tried again when I wrote the follow up post and it worked.

My first attempt, from a Windows laptop, calling ditaa from the command line, did not work. My second attempt, running inside org-mode from a Windows desktop, did work. My third attempt, running from Emacs on Linux also worked.

ditaa diagram using Unicode symbols

* * *

For daily tips on using Unix, follow @UnixToolTip on Twitter.

UnixToolTip twitter icon

Nicholas Higham on Mathematics in Color

This is reprint of Nick Higham’s post of the same title from the Princeton University Press blog, used with permission.


Color is a fascinating subject. Important early contributions to our understanding of it came from physicists and mathematicians such as Newton, Young, Grassmann, Maxwell, and Helmholtz. Today, the science of color measurement and description is well established and we rely on it in our daily lives, from when we view images on a computer screen to when we order paint, wallpaper, or a car, of a specified color.

For practical purposes color space, as perceived by humans, is three-dimensional, because our retinas have three different types of cones, which have peak sensitivities at wavelengths corresponding roughly to red, green, and blue. It’s therefore possible to use linear algebra in three dimensions to analyze various aspects of color.


A good example of the use of linear algebra is to understand metamerism, which is the phenomenon whereby two objects can appear to have the same color but are actually giving off light having different spectral decompositions. This is something we are usually unaware of, but it is welcome in that color output systems (such as televisions and computer monitors) rely on it.

Mathematically, the response of the cones on the retina to light can be modeled as a matrix-vector product Af, where A is a 3-by-n matrix and f is an n-vector that contains samples of the spectral distribution of the light hitting the retina. The parameter n is a discretization parameter that is typically about 80 in practice. Metamerism corresponds to the fact that Af1 = Af2  is possible for different vectors f1 and f2. This equation is equivalent to saying that Ag = 0 for a nonzero vector gf1 – f2, or, in other words, that a matrix with fewer rows than columns has a nontrivial null space.

Metamerism is not always welcome. If you have ever printed your photographs on an inkjet printer you may have observed that a print that looked fine when viewed indoors under tungsten lighting can have a color cast when viewed in daylight.

LAB Space: Separating Color from Luminosity

In digital imaging the term channel refers to the grayscale image representing the values of the pixels in one of the coordinates, most often R, G, or B (for red, green, and blue) in an RGB image. It is sometimes said that an image has ten channels. The number ten is arrived at by combining coordinates from the representation of an image in three different color spaces. RGB supplies three channels, a space called LAB (pronounced “ell-A-B”) provides another three channels, and the last four channels are from CMYK (cyan, magenta, yellow, black), the color space in which all printing is done.

LAB is a rather esoteric color space that separates luminosity (or lightness, the L coordinate) from color (the A and B coordinates). In recent years photographers have realized that LAB can be very useful for image manipulations, allowing certain things to be done much more easily than in RGB. This usage is an example of a technique used all the time by mathematicians: if we can’t solve a problem in a given form then we transform it into another representation of the problem that we can solve.

As an example of the power of LAB space, consider this image of aeroplanes at Schiphol airport.


Original image.

Suppose that KLM are considering changing their livery from blue to pink. How can the image be edited to illustrate how the new livery would look? “Painting in” the new color over the old using the brush tool in image editing software would be a painstaking task (note the many windows to paint around and the darker blue in the shadow area under the tail). The next image was produced in
just a few seconds.


Image converted to LAB space and A channel flipped.

How was it done? The image was converted from RGB to LAB space (which is a nonlinear transformation) and then the coordinates of the A channel were replaced by their negatives. Why did this work? The A channel represents color on a green–magenta axis (and the B channel on a blue–yellow axis). Apart from the blue fuselage, most pixels have a small A component, so reversing the sign of this component doesn’t make much difference to them. But for the blue, which has a negative A component, this flipping of the A channel adds just enough magenta to make the planes pink.

You may recall from earlier this year the infamous photo of a dress that generated a huge amount of interest on the web because some viewers perceived the dress as being blue and black while others saw it as white and gold. A recent paper What Can We Learn from a Dress with Ambiguous Colors? analyzes both the photo and the original dress using LAB coordinates. One reason for using LAB in this context is its device independence, which contrasts with RGB, for which the coordinates have no universally agreed meaning.

Nicholas J. Higham is the Richardson Professor of Applied Mathematics at The University of Manchester, and editor of The Princeton Companion to Applied Mathematics. His article Color Spaces and Digital Imaging in The Princeton Companion to Applied Mathematics gives an introduction to the mathematics of color and the representation and manipulation of digital images. In particular, it emphasizes the role of linear algebra in modeling color and gives more detail on LAB space.

Related posts:

Pretty squiggles

Here’s an image that came out of something I was working on this morning. I thought it might make an interesting border somewhere.

The blue line is sin(x), the green line 0.7 sin(φ x), and the red line is their sum. Here φ is the golden ratio (1 + √5)/2. Even though the blue and green curves are both periodic, their sum is not because the ratio of their frequencies is irrational. So you could make this image as long as you’d like and the red curve would never exactly repeat.

R without Hadley Wickham

Tim Hopper asked on Twitter today:

#rstats programming without @hadleywickham’s libraries is like ________ without _________.

Some of the replies were:

  • (skydiving, a parachute)
  • (gouging your own eyes out, NULL)
  • (dentistry, anesthesia)
  • (shaving, a razor)
  • (Internet shopping, credit card)

Clearly there’s a lot of love out there for Hadley Wickham’s R packages. I’m familiar with his ggplot2 graphics package, and it’s quite impressive. I need to look at his other packages as well.

Related: Help integrating R into your environment

Interview with Michael Hammel, author of The Artist’s Guide to GIMP

Michael J. Hammel is the author of The Artist’s Guide to GIMP, a book I reviewed three weeks ago. The following interview is based on my correspondence with Michael.

JC: The bio on your book says that you are an embedded software developer. Is GIMP something you use for fun or is it related to your work? Was it related to your work before?

MH: I use it once in awhile at work but not often. GIMP started as something related to what I worked on when it first came out (graphics software for Unix systems). But I’ve never been paid to be an artist. At one point I looked at trying to use what I knew about it to leverage my way into Pixar or Dreamworks. But that never panned out and my interest in that kind of animation has peeked and ebbed, mostly because I decided I didn’t want to live in California (too expensive).

JC: How did you become involved in the development of GIMP?

MH: When GIMP was born, back around 1995 or so, I was working for a company that provided commercial X servers for Unix systems (Xi Graphics, started by Thomas Roell who wrote the original reference implementation of an X server for 386 systems, aka X386, which begot XFree86 which begot I packaged Motif as part of my work. A guy I worked with noticed GIMP’s Motif version and pointed me at it. I wrote a plugin for John Beale’s sparkle code (the original Sparkle plugin). I’ve been working with GIMP ever since.

JC: Are you still a developer for GIMP or primarily a user?

MH: A user. I haven’t provided any useful code development to the project in quite sometime.

JC: What’s it like to be a developer on GIMP?

MH: Take this with a grain of salt. It’s a follower’s view from the outside, without being involved with the developers directly.

GIMP’s developer community is somewhat different than other open source communities that I’ve been involved with. GIMP’s leadership is de facto, but not necessarily structured. Many other projects have defined leaders with defined tasks. GIMP’s development is a little more oriented towards scratching your own itch: pick something that that you want to improve and start working on it. The only tough part (at least for some) is understanding and adhering to the main developers coding styles and rules, which are not (to my knowledge) written down.

My only complaint with this style is it tends to allow long term development cycles. End users can’t rely on when new features might be available. While the developers want do things “the right way”, that means that users have been waiting a very long time, for example, for deep paint support. There is a tradeoff for how you do development. Remember that the developers are volunteers, so there is no valid reason for complaining if you, as a user, aren’t getting what you want when you want it. If it bothers you, step in and help out. Otherwise, do as I do: be content with their development process.

JC: What advice would you give people who want to learn image editing?

MH: I learned how to use GIMP by reading Photoshop texts. Image editing is a common set of processes. Think about what you want to do if you weren’t using software. You’re house needs a new color? You mask off the window boarders and roof line and start painting. Same thing in image editing. Only difference: it’s easier to try different colors. Image editing is all about selections and masks. I’m not talking about creating the next Marvel comic, I mean editing existing images. Once you identify what needs to be changed using a selection and mask, you can do all kinds of things: copy and distort, recolor, refocus, etc.

Making comics or custom drawings requires real artistic talent to create a rough design on paper, then import (via scanner or digital camera) into GIMP for cleanup and coloring.

Personally, I prefer taking photos and mixing them together to create a scene that otherwise wouldn’t exist. There is a small example of this in the book. A photo of a city skyline as it exists and a munged version I created to make the city look decayed and falling apart. Beats me what people think of that image, but the creative process that went into it was very relaxing.

JC: What advice would you give people who want to learn GIMP in particular?

MH: Buy my book. Seriously. You learn both at the same time: what is image editing and how do you do it with GIMP. GIMP is just like any other desktop software. You learn where the menus are and what the various windows provide. The rest of your time is learning process — creating a workflow to produce a specific image type or style.

JC: What other software do you use/recommend for creating graphics?

MH: I use simple viewers like Geeqie for browsing images, but if you’re into photography you’ll nee something like f-spot. Photographers, who are nuts about image quality, should learn ufraw. Those interested in 3D or animation should take a look at Blender.

JC: Do you want to say anything about your work with embedded development?

MH: It’s my primary focus in life these days. I’m working on creating a custom media-focused Linux distribution (which I call BeagleBox) for the BeagleBoard C4 (and later the xm). I’d like to get my hands on the Raspberry Pi but wasn’t able to place an order when they first went on sale.

Embedded work is the future for Linux. The desktop for non-techies might change to tablets or such, but Linux will be in everything: your fridge, your TV, your car, your electrical system, your water and sewage systems, your phone, you’re neighbors who are flying robotic UAVs to peek in your windows. Everything.

My day job is building a radar system for UAVs (the big ones) that use embedded Linux to run out of flash. But the direction of interest is smaller devices, little boards with processors and memory in one, like the Pi or BeagleBoard, that can sense the environment and communicate to the rest of the household, with one of those devices used to display all the info on a big wall, removing the need for specialized devices just for the purpose of display.

Anyway, I’m really into making my own custom distribution based on Crosstool-NG (for cross compiling), u-boot (bootloader), Buildroot/Busybox (for root filesystems) and of course Linux.

Related posts:

See this post for links to other interviews here and a couple people who have interviewed me.

The Artist’s Guide to GIMP

Learning how to edit images has been on my to-do list for a long time. I do some very basic editing with Paint.NET, but I keep meaning to learn to use GIMP.

I heard years ago that GIMP is terribly complicated and that I should learn Photoshop instead. I tried Photoshop—not extensively, but I spent some time with it—and I tried GIMP. My conclusion was that image editing is complicated. Image editing software is complicated, but not unnecessarily so. If you expect image processing to be as easy as word processing, as I suppose I implicitly did, your expectations are unrealistic.

The only way I’m going to learn image editing is by doing it. But a book can help, and I expect The Artist’s Guide to GIMP will help more than other GIMP resources I’ve read. That’s because this book puts a little more emphasis on problem solving strategies and techniques and a little less emphasis on software features. As Michael Hammel says in the introduction,

This is a book about process, not buttons or menu paths. … Don’t get bogged down in the mechanics of the tool. Focus on the task at hand. I’ll point you to the GIMP components necessary to finish the job.

The first chapter is about tools more than process, but I suppose some of that is inevitable at first. The rest of the book really is more about process. And there’s plenty of information about buttons and menu paths, but the book is organized by task and process comes before tool details. This is what I want from a book. I can read online documentation, but that documentation won’t tell me what I ought to be looking up. I look to books to get me started in the right direction.