Shoelace is actually just a sum over cross products, because the area of a triangle is half the area of a parallelogram. This point is poorly stated on Wikipedia and Mathworld, too bad. Compare: https://en.wikipedia.org/wiki/Shoelace_formula http://mathworld.wolfram.com/PolygonArea.html The term grouping of the Mathworld formula is better, but this article could use at least one more picture, say of a convex polygon, with a chosen central point, thus triangulated, and affixed on the exterior with reflected triangular "shadows". Then the geometric interpretation in terms of half parallelograms would be easier to see. Re: Heron's formula, I don't know why you would want to involve function sqrt=S. Also, the cross product involves less arithmetic, compare 4*M + 5*A + 1*S with 3*M + 1*A, per triangle. But perhaps in a total perspective, the most ruthless, fastest moving, super competitive, numerical algorithm could evolve to use Heron's formula instead? I did not try to optimize very much, but have doubts about Heron's formula. Anyways, sorting and levelling seems more the bottleneck. --Brad On Fri, Aug 9, 2019 at 1:28 AM Tomas Rokicki <rokicki@gmail.com> wrote:
Maybe he's sorting correctly but then implementing shoelace on the sorted order subcorrectly?