Determining all discrete points inside a triangle

Question

The problem input is specified by three points A, B, C, each with two coordinates x, y.

The solution should be an array of all points inside the the triangle with natural coordinates.

Example:

The input is: A, B, C

The output is: all named point on the figure

Please note that I'm trying to calculate all the points not count them so this question differs from mine quite a bit.

What I'm having trouble with:

Mainly the problem is that, specifying all three segments would require to calculate the coefficients a, b for all segments which could extend my code quite a bit because I would have to cover all the cases of horizontal and vertical lines.

Then the best method I could come up with would be:

1. Iterating through natural x'es from min x of points A, B, C to the max.
2. Iterating through natural y's from min y of points A, B, C to the max.
3. For each point checking whether is satisfies equation system with 9 inequalities, which I could solve manually of use numpy. The high number of inequalities is the second hardest problem.

Generally any way I can think of doing this would require me to write a lot of code with a lot of possible bugs. Also the more instructions I write, the lower the performance gets because of many non-trivial computational methods used.

Any help with a simpler solution would be much appreciated.

Answer 1

You can find the line through each pair of points (lines AB, BC, AC) and check for these lines which side is the inside of the triangle. The points that lie on the 'inside'-side of all lines are inside the triangle:

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 inequalities are solved in the loop, resulting in boolean arrays that are multiplied to yield only the points inside the triangle.

Edit: The loop can be written a little more self-explanatory as:

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

Answer 2

You definitely need triangle rasterization.

Arbitrary article. You would correct starting and ending points of every scanline to ensure they are inside the triangle.