Getting the list of locations in the triangle as x, y positions

Question

Say I have a triangle defined by three integer vertices (x1, y1), (x2, y2) and (x3, y3). Which algorithm can I use to return a complete list of ALL (x, y) integer pairs that lie inside the triangle.

Answer 1

The following algorithm should be suitable:

• Sort the vertices of the triangle by the x coordinate in ascending order. Now we have two segments (1-2 and 2-3) on one side (above or below) and one segment from the other (1-3).

• Calculate the coefficients of the equations of the lines (which contain the segments):

  A * x + B * y + C = 0 A = y2 - y1 B = x1 - x2 C = x2 * y1 - x1 * y2 

  There (x1, y1) and (x2, y2) are two points of the line.

• For each of the ranges [x1, x2), (x2, x3] and x2 (a special case) of iteration over integer points in the ranges, and for each x we ​​do the following:

  • Find the upper bound as y_top = (- A1 * x - C1) div B1.
  • Find the lower bound as y_bottom = (- A2 * y - C2 - 1) div B2 + 1.
  • Add to the result all the points between (x, y_bottom) and (x, y_top).

This algorithm is designed for not strictly internal vertices. For strictly internal vertices, the elements 3.1 and 3.2 are slightly different.

Answer 2

The proper name for this problem is triangle rasterization .

This is a well-researched issue and there are many ways to do this. Two popular methods:

• Scan line by line scan.

  Each scan line requires some basic geometry to recalculate the beginning and end of the line. See the Bresenham line drawing algorithm .

• Check each pixel in the bounding box to see if it is in a triangle.

  This is usually done using barycentric .

Most people believe that method 1) is more effective, since you do not spend time testing pixels that may be outside the triangle, about half of all pixels in the bounding box. However, 2) it has a great advantage - it can be run in parallel much easier, and therefore for hardware, as a rule, much faster. 2) also easier to code.

The original article for describing how to use method 2) was written by Juan Pineda in 1988 and is called the “Parallel Algorithm for the Rasterization Polygon”.

For triangles, this is conceptually very simple (if you study barycentric coordinates). If you convert each pixel to the barycentric coordinates of a triangle, alpha, beta and gamma, then a simple test is that alpha, beta and gamma should be between 0 and 1.

Answer 3

I assume that you have a list of pairs that you want to check (if this is not what your problem is about, please clearly indicate your question). You must first save the pairs in a quad or kd tree structure in order to have a set of candidates that is small enough. If you have few points, this is probably not a hassle (but it won’t scale well if you don’t).

You can also narrow the candidates further by checking against the bounding box for your triangle.

Then, for each candidate pair (x, y) allow in a, b, c system

 a + b + c = 1 a x1 + b x2 + c x3 = x a y2 + b y2 + c y3 = y 

(I let you do this) and the point is inside the triangle if a b and c all positive.

Answer 4

I like ray casting, well described in this Wikipedia article . Used in my project for the same purpose. This method scales to other polygons, including concave. Not sure about the performance, but it's easy to code, so you can try it yourself (I had no performance issues in my project)