三角形内のすべての離散点の決定

Question

問題の入力は、x, yという2つの座標を持つ3つの点A, B, Cによって指定されます。

解決策は、自然座標で三角形内のすべての点の配列でなければなりません。

例：

入力は次のとおりです。 A, B, C

出力は次のようになります。 数字上のすべての名前付きの点

私はすべてを計算しようとしていることに注意してくださいポイントはそれらを数えていないので、this questionはかなり私のものとは異なります。

私は悩みを抱えているもの：

主問題は、すべての3つのセグメントを指定すると、Iので、私のコードビットをかなり拡張することができ、すべてのセグメントの係数a, bを計算するために必要となる、ということです水平線と垂直線のすべての場合をカバーする必要があります。

その後、私が思い付くことができる最高の方法は次のようになります。ポイントmaxにA, B, Cのx分から自然x'esを反復

1. 。
2. 天然からの反復y's最小y点からA, B, Cからmaxまで。
3. 9つの不等式を持つ方程式系を満たすかどうかをチェックする各点については、手動で解くことができるnumpy。不等式の数が多いのは、の2番目のです。一般

私はこれをやって考えることができます任意の方法は、可能なバグの多いコードのたくさんを書くために私が必要となります。また、私が書いた指示が多いほど、使用される多くの重要でない計算方法のためにパフォーマンスが低下します。

もっと簡単な解決策をお探しの場合は、大変お手数です。

Answer 1

間違いなく三角ラスタライズが必要です。

Arbitrary article。三角形の内側にあるように、各走査線の開始点と終了点を修正します。

Answer 2

各点の組（線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