Pixels in a Triangle

Date: 08/02/99 at 09:14:15
From: Berkant Barla Cambazoglu
Subject: Triangle pixel intersection

I basically want to find the number of pixels inside a 2D triangle. 
The triangle may have nodes with floating point coordinate values, but 
the points returned as answer must have integer-valued coordinates.

There are some exact solutions: we may scan convert the triangle, or 
perform an inside-outside test over the triangle using the line 
equations of the edges forming the triangle. However, these methods 
are too slow, and they are unnecessary for this particular problem. 
I don't want the coordinates of the pixels; what I seek is just the 
total number of pixels inside the triangle.

An approximation to this problem would be to calculate the area of the 
triangle and assume that it is the same with the number of pixels 
inside the triangle. However, in this method some triangles can get 
much higher values than the actual value. For example, even a triangle 
has no pixels inside, it is always assigned a positive value instead 
of 0.

I will be glad if you can offer me a smart solution. Thanks for your 
help.

Date: 08/02/99 at 13:03:26
From: Doctor Peterson
Subject: Re: Triangle pixel intersection

Hi, Berkant.

This sounds like it might be a good place to apply Pick's Theorem, 
which you can read about here:

  http://mathforum.org/dr.math/problems/lindsay2.8.96.html   
  http://mathforum.org/dr.math/problems/sen8.27.98.html   

This says that the area of a triangle (or any polygon) whose vertices 
are lattice points (in your situation, this is the same as saying they 
are on pixels - integer coordinates) is I+B/2-1, where I is the 
number of lattice points (pixels) inside the polygon, and B is the 
number of lattice points on the boundary. You want to find I, so 
you'll need to find the area and B. Of course, your vertices don't 
necessarily have integer coordinates, but it will probably work if you 
round to find the corner pixel.

So what's B? The number of lattice points exactly on the line from 
(x1,y1) to (x2,y2), including one of its endpoints, will be the GCD of 
(x1-x2) and (y1-y2). Add these and you'll have B.

So my formula for I, given three vertices (x1,y1), (x2,y2), and 
(x3,y3) rounded to integers, would be

   I = A + 1 - [gcd(x1-x2, y1-y2) + gcd(x2-x3, y2-y3)
       + gcd(x3-x1, y3-y1)]/2

In case you're not familiar with it, you can get the area (again after 
rounding the coordinates) this way:

  A = [(x1-x2)(y1+y2) + (x2-x3)(y2+y3) + (x3-x1)(y3+y1)]/2
    = [x1 y2 - x2 y1 + x2 y3 - x3 y2 + x3 y1 - x1 y3]/2

which is the same as using a determinant, as explained here:

  http://mathforum.org/dr.math/problems/goldner6.9.98.html    
  http://mathforum.org/dr.math/problems/chiaravalli12.14.98.html   

Let's test this with a triangle that will contain no pixels:

    (0,0) (15,15) (15,16)

The area is

    A = [0*15 - 15*0 + 15*16 - 15*15 + 15*0 - 0*16]/2 = 7.5

    gcd(-15,-15) = 15
    gcd(0,-1)    =  1
    gcd(15,16)   =  1

    I = 7.5 + 1 - (15+1+1)/2 = 8.5 - 8.5 = 0

which is correct.

I'm a little uncertain about how this will work out in practice, 
because if you're working with lines drawn on a computer, the 
algorithm that draws the lines will count many pixels that are 
actually inside as being part of the edge, in order to be able to draw 
it without gaps. On the other hand, if you're looking for exactly the 
pixels within the actual triangle defined by non-integer vertices, 
you'll gain or lose points when you round the coordinates. Whether 
this is acceptable depends on the details of your application.

Please let me know whether or not this helps.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/