Post Reply 
(49g 50g) Shoelace algorithm
08-23-2018, 02:20 PM (This post was last modified: 08-26-2018 09:23 PM by John Keith.)
Post: #1
(49g 50g) Shoelace algorithm
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.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
(49g 50g) Shoelace algorithm - John Keith - 08-23-2018 02:20 PM



User(s) browsing this thread: 1 Guest(s)