Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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/
```
Associated Topics:
High School Geometry
High School Practical Geometry
High School Triangles and Other Polygons

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search