鞋带公式的最快方法

Question

我做了一个用鞋带的方法计算多边形面积的函数。

这是完美的工作，但现在我想知道是否有更快的方法来获得相同的结果。我想知道这一点，因为这个函数必须更快地处理具有大量坐标的多边形。

我的函数：

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.

我的多边形：

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

结果：

22.

有什么想法吗？

我试着用Numpy :它是最快的，但你必须先转换你的坐标。

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

Answer 1

对我来说，最快的方法是使用numpy，您必须将(x，y)坐标的numpy数组作为一个参数发送到shoelace方法中：

import numpy as np
def shoelace(x_y):
    x_y = np.array(x_y)
    x_y = x_y.reshape(-1,2)

    x = x_y[:,0]
    y = x_y[:,1]

    S1 = np.sum(x*np.roll(y,-1))
    S2 = np.sum(y*np.roll(x,-1))

    area = .5*np.absolute(S1 - S2)

    return area

Answer 2

这是一个使用1/2乘法的版本：https://stackoverflow.com/a/717367/763269

如果需要更好的性能，可以考虑在Python C扩展中实现。C可以比Python快得多，特别是对于数学运算--有时是100-1000倍。

Answer 3

另一种有趣的方法(虽然速度较慢)

m = np.vstack([x,y])
result = 0.5 * np.abs(np.linalg.det(as_strided(m, (m.shape[1]-1, 2, 2), (m.itemsize, m.itemsize*m.shape[1], m.itemsize))).sum())