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.
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)))))))SHOELACELet us test it on the unit square:
(shoelace '((0 . 0) (1 . 0) (1 . 1) (0 . 1)))1.0and 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