(49g 50g) Shoelace algorithm

[John Keith]

(08-25-2018 01:51 AM)Thomas Klemm Wrote:  I used these formulas found in Centroid:

\(C_{\mathrm {x} }={\frac {1}{6A}}\sum _{i=0}^{n-1}(x_{i}+x_{i+1})(x_{i}\ y_{i+1}-x_{i+1}\ y_{i})\)

\(C_{\mathrm {y} }={\frac {1}{6A}}\sum _{i=0}^{n-1}(y_{i}+y_{i+1})(x_{i}\ y_{i+1}-x_{i+1}\ y_{i})\)

where \(x_{n}=x_{0}\) and \(y_{n}=y_{0}\).

(xs ys -- x y area)

Code:

« DUP TAIL OVER HEAD + ROT
  DUP TAIL OVER HEAD +
  → y v x u
  « x v * u y * -
    x u ADD OVER * ∑LIST
    OVER y v ADD * ∑LIST
    ROT ∑LIST
  »
  ROT OVER 3 * / SWAP
  ROT OVER 3 * / SWAP
  2 /
»

Example

For the cat from this video:

xs: { 4 0 -2 -6 -1 5 }
ys: { 4 1 5 0 -4 -2 }

The result is:

3:       -.169696969697
2:        .030303030303
1:                   55

Cheers
Thomas

Fantastic! Once again smaller and faster.

My program from Post 1: 534ms, 290 bytes
Your program: 441ms, 194 bytes.

I may try a ListExt version when I have some free time.

By the way, ListExt commands make it easy to convert between the flat list format used by my programs and the two separate lists used by yours.

To covert from { X1 Y1 X2 Y2...Xn Yn } to
{ X1 X2...Xn }
{ Y1 Y2...Yn } :

Code:


\<< DUP SIZE 2. / LDIST EVAL
\>>

To convert in the opposite direction:

Code:


\<< 2. \->LIST LCLLT
\>>