Speedest way to Shoelace formula

问题:

I have made a function who calculate area polygon with Shoelace way.

That's works perfectly but right now I wonder if there is not a faster way to have the same result. I want to know that because this function must work faster with polygon with a lot of coordinates.

My function :

def shoelace_formula(polygonBoundary, absoluteValue = True):
    nbCoordinates = len(polygonBoundary)
    nbSegment = nbCoordinates - 1

    l = [(polygonBoundary[i+1][0] - polygonBoundary[i][0]) * (polygonBoundary[i+1][1] + polygonBoundary[i][1]) for i in xrange(nbSegment)]

    if absoluteValue:
        return abs(sum(l) / 2.)
    else:
        return sum(l) / 2.

My polygon :

polygonBoundary = ((5, 0), (6, 4), (4, 5), (1, 5), (1, 0))

Result :

22.

Any ideas?

I try with Numpy : It's speedest but you have to convert your coordinates first.

import numpy as np
x, y = zip(*polygonBoundary)

def shoelace_formula_3(x, y, absoluteValue = True):

    result = 0.5 * np.array(np.dot(x, np.roll(y, 1)) - np.dot(y, np.roll(x, 1)))
    if absoluteValue:
        return abs(result)
    else:
        return result

回答1:

Here's a version that uses 1/2 as many multiplications: https://stackoverflow.com/a/717367/763269

If you need even greater performance, you could consider doing this in a Python C extension. C can be dramatically faster than Python, especially for math operations -- sometimes 100-1000x.

回答2:

Try simplest way, raw shoelace formula for triangles and polygons:

def shoelace_formula(x1, y1, x2, y2, x3, y3, x4, y4, x5, y5):
      return abs(0.5 * (x1*y2 + x2*y3 + x3*y4 + x4*y5 + x5*y1
                        - x2*y1 - x3*y2 - x4*y3 - x5*y4 - y1*y5))

print(shoelace_formula(5, 0, 6, 4, 4, 5, 1, 5, 1, 0))