python - 计算许多三角形的符号面积

Question

我需要计算 signed area二维中的许多三角形，由形状为 (2, 3, n) 的 numpy 数组给出(x/y 坐标，三角形中的节点，三角形的数量)。我正在寻找一种快速完成它的方法，到目前为止我能想到的最好方法是

import numpy
import perfplot


def six(p):
    return (
        +p[0][2] * p[1][0]
        + p[0][0] * p[1][1]
        + p[0][1] * p[1][2]
        - p[0][2] * p[1][1]
        - p[0][0] * p[1][2]
        - p[0][1] * p[1][0]
    ) / 2


def mix(p):
    return (
        +p[0][2] * (p[1][0] - p[1][1])
        + p[0][0] * (p[1][1] - p[1][2])
        + p[0][1] * (p[1][2] - p[1][0])
    ) / 2


def mix2(p):
    p1 = p[1] - p[1][[1, 2, 0]]
    return (+p[0][2] * p1[0] + p[0][0] * p1[1] + p[0][1] * p1[2]) / 2


def cross(p):
    e1 = p[:, 1] - p[:, 0]
    e2 = p[:, 2] - p[:, 0]
    return (e1[0] * e2[1] - e1[1] * e2[0]) / 2


def einsum(p):
    return (
        +numpy.einsum("ij,ij->j", p[0][[2, 0, 1]], p[1][[0, 1, 2]])
        - numpy.einsum("ij,ij->j", p[0][[2, 0, 1]], p[1][[1, 2, 0]])
    ) / 2


def einsum2(p):
    return numpy.einsum("ij,ij->j", p[0][[2, 0, 1]], p[1] - p[1][[1, 2, 0]]) / 2


def einsum3(p):
    return (
        numpy.einsum(
            "ij,ij->j", numpy.roll(p[0], 1, axis=0), p[1] - numpy.roll(p[1], 2, axis=0)
        )
        / 2
    )


perfplot.save(
    "out.png",
    setup=lambda n: numpy.random.rand(2, 3, n),
    kernels=[six, mix, mix2, cross, einsum, einsum2, einsum3],
    n_range=[2 ** k for k in range(19)],
)

关于如何使其更高效的任何提示？

Answer 1

我认为问题不在于计算，而在于数据在内存中的组织方式。如果您不需要保留原始数据，您可以尝试使用 inplace 函数来尽量减少内存中临时对象的数量:

def mymix(p):

    p[0][1] -= p[0][0] # x1 = x1 - x0
    p[0][2] -= p[0][0] # x2 = x2 - x0
    p[1][1] -= p[1][0] # y1 = y1 - y0
    p[1][2] -= p[1][0] # y2 = y2 - y0

    p[0][1] *= p[1][2] # x1 = (x1-x0) * (y2-y0)
    p[0][2] *= p[1][1] # x2 = (x2-x0) * (y1-y0)

    p[0][1] -= p[0][2] # r = (x1-x0) * (y2-y0) - (x2-x0) * (y1-y0)
    p[0][1] /= 2

    return p[0][1]