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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.