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

问题输入由三个点A, B, C指定，每个点具有两个坐标x, y。确定三角形内的所有离散点

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

例子：

输入是： A, B, C

输出是： 上图中所有指定地点

请注意，我试图计算出所有点不算他们，所以this question与我的相差很大。

什么我遇到的麻烦：

主要问题是，指定所有三个部分需要计算系数为a, b可能相当多的延长我的代码，因为我所有的段将不得不涵盖所有水平和垂直线条的情况。

然后，我能想出的最好的方法是：

迭代通过自然x'es从最小点A, B, C到最大的x。
通过自然y's从最小点y点A, B, C到最大值。
对于每个点检查是否满足9个不等式的方程组，我可以手动解决使用numpy。最大的不平等是第二个最难的问题。

通常，任何方法可以让我觉得这样做会需要我来写的代码很多有很多可能的错误。另外，我写的指令越多，性能就越低，因为使用了许多不重要的计算方法。

任何帮助简单的解决方案将不胜感激。

来源

2016-05-12 ZbyszekKr

谷歌“测试，如果点在三角”。有很多资源。你不必解决9个不平等。 –

我不确定它是否有效，但我相信你可以计算出三个高度。这对第1点和第2点没有帮助，但它会将不平等数量最小化为三。因为要位于三角形内，与点A的距离必须小于h_a等等 – Glostas

一些想法'http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-2d -triangle' – Marichyasana

你绝对需要三角形光栅化。

Arbitrary article。您可以更正每条扫描线的起点和终点，以确保它们位于三角形内。

来源

2016-05-12 09:09:58 MBo

是的。只需检查扫描线的第一个和最后一个点（例如，使用纯整数版本的“PointInTriangle”测试） – MBo

您可以通过每对点（线AB，BC，AC）找到线，并检查这些线的哪一侧是三角形的内侧。摆在所有线路上的“inside'侧的点是在三角形内：

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不等式解决了循环，导致相乘，得到三角形内仅点布尔阵列。

编辑：回路可以写更多的不言自明的一点是：

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

来源

2016-05-12 21:39:02 Haminaa

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

回答

相关问题