2.6 Geometric shapes

Computer graphics requires that 2D shapes and 3D objects have a numerical description of some sort. Shapes can include polygons, circles, arbitrary curves and surfaces, etc.

Polygonal Shapes

A polygon is constructed from a sequence of vertices (points) as shown in Figure 2.11. A straight line is assumed to link each pair of neighboring vertices; intermediate points on the line are not explicitly stored. There is no convention for starting a chain of vertices, but software will often dictate whether polygons have a clockwise or anti-clockwise vertex sequence.

Figure 2.11: A simple polygon created with four vertices shown in the table.

2.6 Geometric shapes

Let us illustrates how to find the "orientation" of two line segments with three given vertices (points): p1(x1, y1), p2(x2, y2), p3(x3, y3).

Three points p1(x1, y1), p2(x2, y2), p3(x3, y3) define a clockwise, counter-clockwise triangle, or may be aligned (see figure 2.12). These three cases correspond to a positive, negative, or null value of the following determinant:

Figure 2.12: Going from segment (p1, p2) to (p2, p3) do we make a right or a left turn?

2.6 Geometric shapes

The Area of Polygon

The area of a polygonal shape is readily calculated from its chain of coordinates.

For example, given the following list of coordinates: (x0, y0), (x1, y1), (x2, y2), (x3, y3), then the area of the polygon is computed by: Area=1/2[(x0y1-x1y0) + (x1 y2-x2y1) + (x2 y3-x3y2) + (x3 y0-x0y3)]

If you check to see what is happening, you will notice that the calculation sums the results of multiplying an x by the next y, minus the next x by the current y. When the last vertex is selected it is paired with the first vertex to complete the process. The result is then halved to reveal the area.

As a simple test, let's apply the area of the polygon given above to the shape described in Figure 3.9: 1/2[(1 × 1 − 3 × 1) + (3 × 2 − 3 × 1) + (3 × 3 − 1 × 2) + (1 × 1 − 1 × 3)] =1/2[−2 + 3 + 7 − 2] = 3.

Figure 3.9 shows a three-sided polygon (i.e. triangle) with three vertices P0(x0, y0), P1(x1, y1), and P3(x, y3) formed in an anti-clockwise sequence. In figure 2.13, the area of the triangle formed by the vectors: r=(x1-x0) i + (y1-y0) j, and s=(x2-x0) i + (y2-y0) j, is half the magnitude of their cross product

2.6 Geometric shapes

Therefore, The area of the triangle=1/2[(x0y1-x1y0) + (x1 y2-x2y1) + (x2 y0 -x0y2)].

Figure 2.13: The area of the triangle formed by the vectors r and s is half the magnitude of their cross product.
Note that, if the original set of coordinates is clockwise, the area is negative. To illustrate this feature, the original vertices are reversed to a clockwise sequence as follows: 1/2[(1 × 3 − 1 × 1) + (1 × 2 − 3 × 3) + (3 × 1 − 3 × 2) + (3 × 1 − 1 × 1)] =1/2[2 − 7 − 3 + 2] = −3. The minus sign indicates that the vertices are in a clockwise sequence.

2.6 Geometric shapes

Point-in-Triangle Test

We often require to test whether a point is inside, outside or touching a triangle.

One of the methods is related to finding the area of a triangle. Suppose you have 3 points A(x1,y1), B(x2,y2), and C(x3,y3) that represent a triangle. Now suppose you have another point P(x,y) and you want to know if that point is inside the triangle. The procedure for checking whether P is inside or not inside the triangle ABC is given as follows:

	Calculate the area of the given triangle ABC and denote it by M.
	Calculate the area of the triangle PAB and denote it by A1.
	Calculate the area of the triangle PBC and denote it by A2.
	Calculate the area of the triangle PAC and denote it by A3.
	If P lies inside the triangle, then A1 + A2 + A3 must be equal to M.

2.6 Geometric shapes

Point-on-Polygon Test

Testing whether a point is inside a polygon is a basic operation in computer graphics applications, for example polygon filling on raster devices. Consider a 2D surface with bounding rectangle coordinates xmin, xmax, ymin, and ymax, with a polygon made up of N vertices (xi,yi) where i ranges from 0 to N-1. The last vertex (xN,yN) is assumed to be the same as the first vertex (x0,y0), that is, the polygon is closed. Given a test point p with coordinates (px,py), then if p is not inside min-max box, it is not inside the polygon.

This means that the following condition is achieved: (pxxmax or : pyymax). Otherwise, compute the intersections of y=py with the edges of the polygon to determine the status of a point p consider a horizontal ray emanating from (px,py) and to the right.

If the number of times this ray intersects the line segments making up the polygon is even then the point is outside the polygon. Whereas if the number of intersections is odd then the point (px,py) lies inside the polygon.

2.6 Geometric shapes

Point-on-Line Test

The parametric representation of a line with two given points (x0,y0,z0), (x1,y1,z1) is given as: x=(x1-x0)u +x0, y=(y1-y0)u +y0, z=(z1-z0)u +z0, where u

The above equation is useful to analyze the geometric relationships between points and lines. Given a line with two end points p0, and p1, a test point q is either on or off a given line. If it is on the line, it is either between the end points, q1, on the backward extension of the line, q2, or on the forward extension, q3 (see figure (2.14).

Figure 2.14: Point and line relationships.

2.6 Geometric shapes

Rewrite the above equation in terms of u to obtain: Ux=(x-x0/x1-x0), Uy=(y-y0/y1-y0), Uz=(z-z0/z1-z0). The subscript on u identifies the source of its computed value. Now, given, the coordinates of any point q=(x,y,z), compute Ux, Uy, Uz. If and only if, Ux= Uy= Uz, then point q is on the line; otherwise it is off the line.

Distance between a Point and a Line

The distance from a point to a line is the shortest distance from a point to a line in Euclidean geometry.

Knowing the shortest distance from a point to a line can be useful in a few situations (e.g. the shortest distance to reach a road). In the case of a line in the plane given by the equation ax + by + c = 0, where a, b and c are real constants with a and b not both zero, the distance from the line to a point p0=(x0, y0, z0) is:

Triangulation of Polygons

Computing the triangulation of a polygon is a fundamental algorithm in computational geometry.

2.6 Geometric shapes

In computer graphics, polygon triangulation algorithms are widely used for tessellating curved geometries. Methods of triangulation include greedy algorithms, convex hull differences, and horizontal decompositions. Polygon triangulation is the decomposition of a polygonal area (simple polygon) P into a set of triangles i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P. Every triangulation of a polygon P of n vertices uses n-3 diagonals and consists of n − 2 triangles.

Boundaries of Filled Regions

A raster display can show regions of pixels filled with a solid, pattern or texture colors (see figure 2.15). By a region we mean a collection of pixels lying "next to" one another in some fashion or being associated with each other by some common property.

The most widely used method in graphics defines a region as the interior of a polygon.

Figure 2.15: Several regions with different color filling (solid, pattern, and texture)

2.6 Geometric shapes

Raster-based filling of polygons algorithm is one of the approaches to filling regions. Suppose that the region to be filled is a polygon "Y" described by a set of vertices pi=(xi,yi), for i=11, …, n, that specifies the sequence of Y's vertices. To fill Y, we progress through the frame buffer scan line by scan line, filling in the appropriate portions of each line.

The proper portions are determined by finding the intersections of the scan line with all the edges of Y. The following pseudo-code suggests the filling process for a given point P (see figure 2.16):

For each scan line L
{
Find intersections of L with all edges of Y, then count the number of times the line crosses an edge:
If the number of crossings is odd, P is inside
If the number of crossings is even, P is outside }

Figure 2.16: Raster-based filling of polygons algorithm with scan lines in (a) and an example in (b)

2.6 Geometric shapes

For example, in figure 2.17, the scan line at y=3 intersects the four edges e2, e3, e4, and e5. The four X-values of the intersection are sorted to yield the sequence 1, 2, 7, and 9. Then two runs are filled: the first from column 1 to 2 and the second from column 7 to 9.

Figure 2.17: Filling proper portions of a scan line