minimicro-sysdisk icon indicating copy to clipboard operation
minimicro-sysdisk copied to clipboard

mathUtil.polyArea does not produce accurate results

Open JoeStrout opened this issue 2 years ago • 1 comments

This came up as part of Advent of Code 2023, Day 18.

Given this polygon:

[[461938, 1], [461938, -56406], [818609, -56406], [818609, -919646],
 [1186329, -919646], [1186329, -1186328], [609066, -1186328], [609066, -356353], 
[497057, -356353], [497057, -1186328], [5411, -1186328], [5411, -500254], [0, -500254], [0, 1]]

...we get different answers using the built-in mathUtil.polyArea than we do with custom code implementing the Shoelace algorithm:

MathUtil.polyArea:  952408211456
Custom polygonArea: 952408144115

And the custom code's answer is correct. Here's the code for that:

polygonArea = function(verts)
    area = 0.0
    n = verts.len
    j = n - 1
    for i in range(0,n-1)
        area += (verts[j][0] + verts[i][0]) * (verts[j][1] - verts[i][1])
        j = i
    end for
    return abs(area / 2.0)
end function

JoeStrout avatar Dec 18 '23 15:12 JoeStrout

There are some hints that mathUtil.polyPerimeter may have issues, too. Better test thoroughly.

JoeStrout avatar Dec 18 '23 16:12 JoeStrout