python - 确定三角形内的所有离散点

Question

问题输入由三个点A, B, C指定，每个点有两个坐标x, y。

解决方案应该是具有自然坐标的三角形内所有点的数组。

例子:

输入是:A、B、C

输出是:图中所有命名点

请注意，我正在尝试计算所有的点而不是计算它们所以 this question和我的有很大不同。

我遇到的问题:

主要 问题是，指定所有三个段需要计算所有段的系数 a, b 这可能会扩展我的代码很多，因为我会必须涵盖所有水平线和垂直线的情况。

那么我能想到的最好的方法是:

1. 迭代自然 x'es，从点 A、B、C 的最小 x 到最大值。
2. 从 A、B、C 点的最小 y 到最大值迭代自然 y。
3. 对于每个点，检查它是否满足具有 9 个不等式的方程组，我可以使用 numpy 手动求解。大量的不平等是第二最困难的问题。

一般来说，我能想到的任何方式都需要我编写很多代码，其中可能存在很多错误。此外，我编写的指令越多，性能就越低，因为使用了许多非平凡的计算方法。

如能提供更简单的解决方案，我们将不胜感激。

Answer 1

您可以找到通过每对点的线(线 AB、BC、AC)并检查这些线的哪一侧是三角形的内部。位于所有线的“内侧”侧的点都在三角形内:

def insidetriangle((x1,x2,x3),(y1,y2,y3)):
    import numpy as np
    xs=np.array((x1,x2,x3),dtype=float)
    ys=np.array((y1,y2,y3),dtype=float)

    # The possible range of coordinates that can be returned
    x_range=np.arange(np.min(xs),np.max(xs)+1)
    y_range=np.arange(np.min(ys),np.max(ys)+1)

    # Set the grid of coordinates on which the triangle lies. The centre of the
    # triangle serves as a criterion for what is inside or outside the triangle.
    X,Y=np.meshgrid( x_range,y_range )
    xc=np.mean(xs)
    yc=np.mean(ys)

    # From the array 'triangle', points that lie outside the triangle will be
    # set to 'False'.
    triangle = np.ones(X.shape,dtype=bool)
    for i in range(3):
        ii=(i+1)%3
        if xs[i]==xs[ii]:
            include = X *(xc-xs[i])/abs(xc-xs[i]) > xs[i] *(xc-xs[i])/abs(xc-xs[i])
        else:
            poly=np.poly1d([(ys[ii]-ys[i])/(xs[ii]-xs[i]),ys[i]-xs[i]*(ys[ii]-ys[i])/(xs[ii]-xs[i])])
            include = Y *(yc-poly(xc))/abs(yc-poly(xc)) > poly(X) *(yc-poly(xc))/abs(yc-poly(xc))
        triangle*=include

    # Output: 2 arrays with the x- and y- coordinates of the points inside the
    # triangle.
    return X[triangle],Y[triangle]

在循环中解决了 3 个不等式，生成了 bool 数组，这些数组相乘后仅产生三角形内的点。

编辑:循环可以写得更不言自明:

for i in range(3):
    ii=(i+1)%3
    if xs[i]==xs[ii]:
        if xc>xs:
            include = (X > xs[i])
        else:
            include = (X < xs[i])
    else:
        slope=(ys[ii]-ys[i])/(xs[ii]-xs[i])
        poly=np.poly1d([slope,ys[i]-xs[i]*slope])

        if yc>poly(xc):
            include = (Y > poly(X))
        else:
            include = (Y < poly(X))
    triangle*=include