(49g 50g) Shoelace algorithm

[John Keith]

EDIT: These programs have been largely obsoleted by Thomas Klemm's programs in post numbers 5 and 11
respectively. I am leaving them here for illustrative purposes only.

---

Inspired by Thomas Klemm's elegant RPL implementation of the shoelace method for calculating the area of a polygon, I am listing my version here. Though it is longer and not nearly as elegant, it is over 2.5 times faster.

My program differs in that it takes a list of coordinates of the form
{ X1 Y1 X2 Y2...Xn Yn }
instead of a list of two-element vectors.

Code:


\<< DUP 1. 2. SUB + 4.
  \<< NSUB 2. MOD { UNROT * UNROT * SWAP - } { DROP2 DROP2 } IFTE
  \>> DOSUBS \GSLIST ABS 2 /
\>>

The following extended version calculates the area and centroid (aka barycenter) of a polygon. The results are returned as a list of the form
{ Area X Y }.

Code:


\<< DUP 1. 2. SUB + DUP 4.
  \<< NSUB 2. MOD { UNROT * UNROT * SWAP - } { DROP2 DROP2 } IFTE
  \>> DOSUBS OVER 4.
  \<< NSUB 2. MOD { DROP NIP + } { DROP2 DROP2 } IFTE
  \>> DOSUBS OVER * \GSLIST SWAP ROT 4.
  \<< NSUB 2. MOD { NIP ROT DROP + } { DROP2 DROP2 } IFTE
  \>> DOSUBS OVER * \GSLIST SWAP \GSLIST 2 / DUP ABS EVAL 4. ROLLD 6 * INV DUP ROT * EVAL UNROT * EVAL SWAP 3. \->LIST
\>>

Both programs will return exact integer or rational results if the input coordinates are exact and the program is run in exact mode. If this is not desirable, the integer(s) in the last lines of the programs can be changed to reals, and the EVALs in the last line of the second program can be eliminated. This will make the programs run slightly faster.