The Shoelace Formula for the Area of a Polygon

Description of the problem

There is a very nice formula attributed to Meister that calculates the area of a simple polygon given as list of points on the plane. If \(P\) is the polygon given by the list of points \((x_1,y_1),\ldots,(x_n,y_n)\) then the area of this polygon is given by \[ \frac{1}{2}\left\| \sum_{i=1}^{n-1} x_iy_{i+1} + x_ny_1 - \sum_{i=1}^{n-1} y_ix_{i+1} - y_nx_1 \right\| \] Today, I am going to implement this as a common lisp function.

Implementation

The implementation is pretty straight-forward:

(defun shoelace (points)
  (labels ((dot (as bs) (reduce #'+ (mapcar #'* as bs)))
           (cycle (as) (append (last as)
                               (reverse (cdr (reverse as))))))
    (let ((xs (mapcar #'car points))
          (ys (mapcar #'cdr points)))
      (* 0.5 (abs (- (dot xs (cycle ys))
                     (dot (cycle xs) ys)))))))

SHOELACE

Let us test it on the unit square:

(shoelace '((0 . 0) (1 . 0) (1 . 1) (0 . 1)))

1.0

and on an equilateral triangle

(= (shoelace (list (cons 0.5 0) (cons -0.5 0) (cons 0 (/ (sqrt 3) 2.0))))
   (/ (sqrt 3) 4.0))

T