


Computer Graphics  Applied GeometryIn this section we will discuss some mathematical concepts useful in Computer Graphics. Topics included are: Vectors, Dot Product, Determinants, Vector ProductVectorsWe begin with the mathematical notion of a vector, which should not be confused with the C++ or java Vector object container class. A vector is defined as a directed line segment.
Figure AG1 shows 2 representations of the same vector: a = PQ = b = RSThus, a vector is not altered by a translation (Δ Position). The sum c of the vectors a and b, written c = a + bcan be obtained as the diagonal of a parallelogram, with a, b and c starting at the same point, as shown in figure AG2:
The length of a vector a is denoted by a. A vector with zero length is the Zero Vector, and written as 0. The notation a is used for the vector that has length a and whose direction is opposite to that of a. For any vector a and real number c, the vector ca has length ca. if a = = 0 or c = = 0, then ca=0; otherwise ca has the direction of a if c > 0 and the opposite direction if c < 0. For any vectors u, v, w and real numbers c, k, we have:
Figure AG3 shows 3 unit (length 1) vectors i, j, and k in a 3D space. They are mutually perpendicular and have length 1. Their directions are the positive directions of the coordinate axes. We say that i, j, and k form a triple of orthogonal unit vectors. The coordinate system is righthanded, which means that if a rotation of i in the direction of j through 90 ° corresponds to turning a lid on a jar of peanut butter, then k has the direction in which the screw advances.
We often choose the origin (O) of the coordinate system as the initial point of all vectors. Any vector v can be written as a linear combination of the unit vectors i, j, and k: v = x i + y j + z kThe real numbers x, y and z are the coordinates of the endpoint P of vector v = OP. We often write this vector as:
The numbers x, y, z are sometimes called the elements or components of vector v. The Inner ProductThe inner product or dot product of two vectors a and b is a real number written as a ⋅ b and defined as:
where γ is the angle between a and b. It follows from the first equation that a ⋅ b is also zero if γ = 90 °. Applying this definition to the unit vectors i, j and k, we find
Setting b = a in Equation (AG.1), we have a ⋅ a = a^{2}, so a = √(a ⋅ a)Some important properties of inner products are
The inner product of two vectors u = [ u_{1} u_{2} u_{3} ] and v = [ v_{1} v_{2} v_{3} ] can be computed as u ⋅ v = U_{1}V_{1} + U_{2}V_{2} + U_{3}V_{3}We can prove this by developing the righthand side of the following inequality as the sum of the nine inner products and then applying Equation (AG.2): u ⋅ v = (U_{1}i + U_{2}j + U_{3}k) ⋅ (V_{1}i + V_{2}j + V_{3}k)DeterminantsBefore proceeding with vector products, we will pay some attention to determinants. Suppose we want to solve the following system of two linear equations for x and y:
We can them multiply the first equation by b_{2}, the second by b_{1}, and add them, finding (a_{1}b_{2}  a_{2}b_{1})x = b_{2}c_{1}  b_{1}c_{2}Next, to find y we can multiply the first equation by a_{2}, the second by a_{1}, and add as was done to find x, obtaining: (a_{1}b_{2}  a_{2}b_{1})y = a_{1}c_{2}  a_{2}c_{1}As long as a_{1}b_{2}  a_{2}b_{1} ≠ Zero, we can divide both equations and complete the solution:
The denominator in these expressions is often written in the form: and then called a determinant.. Thus: Using determinants, we can write the solution of Equation (AG.3) as where Note that D_{i} is obtained by replacing the ith column of D with the righthand side of Equation (AG.3) (i=1 or 2). This method of solving a system of linear equations is called Cramer's Rule. It is not restricted to systems of two equations (although it can become very expensive of computer time to apply to large(order >> 2) systems of equations). Determinants with n rows and n columns are said to be of the nth order. We define determinants of the 3rd order by using the equation: where each socalled minor determinant M_{ij} is the 2 x 2 determinant that we obtain by deleting the ith row and the jth column of D. Determinants of higher order are defined similarly. Determinants are very useful in both linear algebra and analytical geometry. They have many interesting properties, some of which are even listed below: (1) The value of a determinant remains the same if its rows are written as columns in the same order. For example: (2) if any two rows (or columns) are interchanged, the value of the determinant if multiplied by 1. For example: (3) If any row or column is multiplied by a factor, the value of the determinant is mulitplied by this factor. For example: (4) If a row is altered by adding any constant mulitple of any other row to it, the value of the determinant remains unaltered. This operation also applies to columns. For example: (5) If a row (or a column) is a linear combination of some other rows (or columns), the determinant is Zero. For example: In many cases, determinant equations expressing geometrical properties are elegant and easy to remember. For example, the equation of the line in R_{2} through the points P_{1}(x_{1}, y_{1}) and P_{2}(x_{2},y_{2}) can be written: This can be understood by observing, first, that Equation (AG.5) is a special notation for a linear equation in x and y, and consequently represents a straight line in R_{2}, and second, that the coordinates of both P_{1} and P_{2} satisfy this equation, for if we write them in the first row, we have two identical rows. Similarly, the plane in R_{3} through three points P_{1}(x_{1},y_{1},z_{1}), P_{2}(x_{2},y_{2},z_{2}), P_{3}(x_{3},y_{3},z_{3}) has the equation: which is much easier to remember than one written in the conventional way. Vector ProductThe vector product or cross product of two vectors a and b is written a × band is a vector v with the following properties:
if a == cb for some scalar c, then v = 0. v = ab sin γwhere γ is the angle between a and b, and the direction of v is perpendicular to both a and b and is such that a, b and v in that order, form a righthanded triple. This means that if a is rotated through an angle γ < 180 ° in the direction of b, then v has the direction of the advancement of the lid to a jar of peanut butter if turned the same way. Note that the length v is equal to the area of a parallelogram of which the vectors a and b can act as edges, as Figure AG4 shows
The following properties of vector products follow from this definition:
In general, a × (b × c) ≠ (a × b) × c. if we apply our definition of vector product to the unit vector, i, j, k (refer to Figure AG3) we have:
Using these vector products in the expansion of:
we obtain
which can be written as: We rewrite this in an easy to remember form: This is a mnemonic aid rather than a true determinant, since the elements of the first row are vectors instead of numbers.
If a and b are neighboring sides of a parallelogram, as shown in Figure AG.4, the area of the parallelogram is the length
of the vector a × b. This follows from our definition of vector product, according to which a × b = ab sin γ
is the length of the vector a × b. The Orientation of 3 PointsWe will now deal with a subject that will be very useful susequently. Supose we are given an ordered triple (A, B, C) of 3 points in the xyplane and we want to know their orientation; in other words, we want to know whether we turn counterclockwise when visiting these points in the given order. Figure AG5 shows the possibilities, which we also refer to as positive and negative orientation, respectively:
There is a third possibility, namely that the points A, B and C lie on a straight line. We will consider the orientation to be zero in that case. If we plot the points on paper, we see immediately which of these 3 cases applies, but we now want a means to find the orientation by computation, using only the coordinates x_{A}, y_{A}, x_{B}, y_{B}, x_{C}, y_{C}.
Let us define the two vectors a = CA and b = CB, as shown in Figure AG6. Clearly, the orientation of the original points A, B and C is positive if we can turn the vector a counterclockwise through a positive angle less than 180 ° to obtain the direction of the vector b. Since vectors are only determined by their directions and lengths, we may let them start at the origin O instead of at point C, as Figure AG6 shows. Although this orientation problem is essentially 2D, and can be solved using only 2D concepts, as we will see in a moment, it is convenient to use 3D space as well. As usual, the unit vectors i, j, k have the direction of the positive x, y, and z axes. In Figure AG6, we imagine the vector k like i and j starting at O and then pointing toward us. Denoting the endpoints of the translated vectors a and b, starting at O, by (a_{1}, a_{2}, 0) and (b_{1}, b_{2}, 0), we have:
which, when written in determinant form becomes: This expresses the fact that a × b is perpendicular to the xyplane and either in the same direction as
or in the opposite direction, depending on the sign of a_{1}b_{2}  a_{2}b_{1}. If this expression is positive, the relationship between a and b is similar to that of i and j: we can turn a counterclockwise through an angle less than 180 ° to obtain the direction of b, in the same way as we can do this with i to obtain j. In general, we have: An alternative, 2D SolutionIt would be unsatisfactory if we were unable to solve the above orientation problem by using only 2D concepts. To provide such an alternative solution, we use the angles, α between vector a and the positive xaxis and β between b and this axis (See Figure AG6). Then the orientation we are interested in depends on the angle β  α. If this angle liens between 0 and π, the orientation is clearly positive, but it is negative if this angle lies between π and 2π (or between 0 and π). We can express this by saying that the orientation in question depends on the value of sin(β  α) rather than on the angle (β  α) itself. More specifically, the orientation has the same sign as: Since the denominator in this expression is the product of two vector lengths, it is positive, so that we have again found that the orientation of A, B and C and a_{1}b_{2}  a_{2}b_{1} have the same sign. Due to the unfamiliarity of the above trigonometric formula, the more visual 3D approach could be easier to remember. PolygonsA polygon is a sequence of vertices: P_{0}, P_{1}, . . ., P_{n1}, where n > 3, with associated edges. The first order of business is to determine if a vertex is convex, or the interior angle is less than 180 deg;. If all of the vertices are convex, the polygon itself is convex, and one in which we will now analyze. Any vertex whose x or y coordinate is extreme is convex. For example, we can use a vertex whose xcoordinate is not greater than that of any other vertex. If we do not want to exclude the special case of 3 successive vertices lying on the same line, we must pay special attention to the case of three such vertices having the minimum xcoordinate. Therefore, among all vertices with an xcoordinate equal to this minimum value, we choose the lowest one, i.e. the one with the least ycoordinate. The area of a polygonAs we have seen in Figure AG4, the cross product a × b is a vector whose length is equal to the area of a parallelogram of which a and b are two edges. Since this parallelogram is the sum of two triangles of equal area, it follows that for Figure AG6 we have: Note that this is valid only if A, B and C are labeled counterclockwise; if this is not necessarily the case, we have to use the absolute value of a_{1}b_{2}  a_{2}b_{1}.
Since 2 Area(Δ ABC) = (x_{A}  x_{C})(y_{B}  y_{C})  (y_{A}  y_{C})(x_{B}  x_{C}) Point In Triangle TestDetermining the orientation of three points as we have just been discussing is useful in a test to see if a given point P lies within triangle ABC. As Figure AG8 shows, this is the case if the orientation of the triangles ABP, BCP and CAP is the same as that of triangle ABC:
Based on the above discussion we can develop some code that will be useful in future applications: class Tools2D { static float area2(Point2D a, Point2D b, Point2D c) { return (a.x  c.x) * (b.y  c.y)  (a.y  c.y) * (b.x  c.x); } static float area2(Point2D[] pol) { int n = pol.length, j = n  1; float a = 0; for (int i=0; i < n; i++) { // i and j denote neighbor vertices // with i one step ahead of j a += pol[j].x * pol[i].y  pol[j].y * pol[i].x; j = i; } return a; } static boolean ccw(Point2D[] p) { int n = p.length, k = 0; for (int i=1; i The above method, insideTriangle, is reasonably efficient, especially if point P does not lie within triangle ABC. In such cases, the chances are that not all 3 calls to area2 are executed because the first or the second of the 3 tests fails. However, it should be mentioned that there is an entirely different way of solving the problem in question. However, this will employ the use of matrix multiplication and inverse matrices, which will be discussed in short order. Point In Polygon TestThe notion of orientation is also useful when we need to determine whether a given point P lies within a polygon. It will then be convenient if a method is available which accepts both the polygon in question and point P as arguments, and returns true if P lies inside and false if it lies outside the polygon. If P lies on a polygon edge, we do not care: in that case the method may return true or false. The method we will discuss is based on the idea of drawing a horizontal halfline, which starts at P and extends to the right. The number of intersections of this horizontal halfline with polygon edges is odd if P lies within the polygon and even if P lies outside it. Imagine that we move to the right, starting at point P. Then, our state changes from inside to outside and vice versa each time we cross a polygon edge. The total number of changes is therefore odd if P lies within the polygon and even if it lies outside the polygon. It is not necessary to visit all intersections from left to right; the only thing we want to know is whether there are an odd or an even number of intersections on a horizontal line through P and to the right of P. However, we must be careful with some special cases, as shown in Figure AG9:
In this case, we simply ignore the polygon edges, even if they have the same ycoordinate as P, as is the case with edge 45 in this example. If a vertex occurring as a "local maximum or minimum" happens to have the same ycoordinate as P, as is the cases with vertices 8 and 12 in this example, it is essential that this is either ignored or counted twice. We can realize this by using the edge from vertex (i) to vertex(i+1) only if: y_{i} ≤ y_{p} < y_{i+1} or y_{i+1} ≤ y_{p} < y_{i} This implies that the lower endpoint of a nonhorizontal edge is regarded as part of the segment, but the upper endpoint is not. For example, in Figure AG9, vertex 8 (with y_{8} = y_{p}) is not counted at all because it is the upper endpoint of both edge 78 and edge 89. By contrast, vertex 12 (with y_{12} = y_{p}) is the lower endpoint of the edges 1112 and 1213 and thus counted twice. Therefore, in this example, we count the intersections of the halfline through P with the seven edges 23, 34, 56, 67, 1011, 1112, and finally 1213 with no others. Since we are considering only a halfline, we must impose another restriction on the set of edges satisfying the above test, selecting only those whose point of intersection with the halfline lies to the right of P. One way of doing this is by using the method area2 to determine the orientation of a sequence of three points. For example, this orientation is counterclockwise for the triangle 23P in Figure AG9, which implies that P lies to the left of edge 23. It is also counterclockwise for the triangle 76P. In both cases, the lower endpoint of an edge, its upper endpoint and point P, in that order, are counterclockwise. The following method is based on these principles: static boolean insidePolygon(Point p, Point[] pol) { int n = pol.length, j = n  1; boolean b = false; float x = p.x, y = p.y; for (int i=0; i This static method, as well as several others will be added to the Tools2D class. Point On Line TestTesting whether a point P lies on a given line is very simple if this line is given as an equation, say: ax + by = c (AG.7) Then all we need to do is to test whether the coordinates of P satisfy this equation. Due to inexact computations, this test could fail, even though it should succeed. It may, therefore, be wise to be slightly more tolerant, so that we might write: if (Math.abs(a * p.x + b * p.y  h) < eps) // P on the line where eps is some small positive values such as 10^{6}. If the line is not given by an equation but by two points A and B on it, we can use the above test after deriving an equation for the line writing: which gives the followin coefficients for Equation (AG.7):
Instead, we can benefit from the area2 method, with which we are now intimately familiar. After all, if and only if P lies on the line through A and B, the triangle ABP is degenerated and has zero area. We can therefore write: if (Math.abs(Tools2D.area2(a, b, p)) < eps) // P on line AB Again, if we simply test whether the computed area is equal to zero, such atest might fail when it should succeed, due to roundingoff errors. Testing whether a Point Lies on a Line SegmentIf 3 points A, B and P are given, we may want to determine whether P lies on the closed line segment AB. The adjective closed here means that we include the endpoints A and B, so that the question is to be answered affirmatively if P lies between A nd B or coincides with one of these points. We assume that A and B are different points, which implies that x_{A} ≠ x_{B} or y_{A} ≠ y_{B}. if x_{A} ≠ x_{B} we test whether x_{P} lies between x_{A} and x_{B,}; if not, we test whether y_{P} lies between y_{A} and y_{B}, where in both cases the word between includes the points A and B themselves. This test is sufficient if it is given that P lies on the infinite line AB. If that is not given, we also have to perform the above test, which is done in the following method: static boolean onSegment(Point2D a, Point2D b, Point2D p) { double dx = b.x  a.x, dy = b.y  a.y, eps = 0.001 * (dx * dx + dy * dy); return (a.x != b.x && (a.x <= p.x && p.x <= b.x  b.x <= p.x && p.x <= a.x)  a.x == b.x && (a.y <= p.y && p.y <= b.y  b.y <= p.y && p.y <= a.y)) && Math.abs(Tools2D.area2(a, b, p)) < eps; } The expression following return relies on the operator && having higher precedence than . Since both operators && and  evaluate the second operand only if this is necessary, this test is more efficient than it looks. For example, if x_{A} ≠ x_{B} the test on the line of the form (a.y ≤ ...) is not evaluated at all. The positive constant eps in the above code has been chosen in such a way that the area of triangle ABP is compared with a fraction of another area, for which the square of side AB is used. In this way, the compared areas depend in the same way on both the length of AB and the unit of length that is used. Instead of testing if P lies on the segment AB, we may want to apply a similar test to the projection of P' of P on AB, as Figure AG10 shows:
We can solve this problem by computing the dot product of vectors AB and AP. The dot product AB ⋅ AP is equal to 0 if P' ≡ A (P' coincides with A) and it is equal to AB ⋅ AB = AB^{2} if P' ≡ B. For any value of this dot product between these two values, P lies between A and B. We can write this as follows in a program, where len2 corresponds to AB ⋅ BA, inprod corresponds to AB ⋅ AP, and eps is some small positive value as discussed above for the onSegment method development. // Does P' (P projected on AB) lie on the closed segment AB? static boolean projOnSegment(Point2D a, Point2D b, Point2D p) { double dx = b.x  a.x, dy = b.y  a.y, eps = 0.001 * (dx * dx + dy * dy), len2 = dx * dx + dy * dy, inprod = dx * (p.x  a.x) + dy * (p.y  a.y); return inprod > eps && inprod < len2 + eps; } Distance Between a Point and a LineWe can find the distance between a point P and a line l in several different ways, depending on the way the line is specified. If two points A and B of the line are given, we can find the distance between a point P and the (infinite) line l through A and B using the first of the 2 methods defined in area2 defined in the Point In Triangle section above:
If the line l is given as an equation, we assume this to be in the form ax + by = c where (a^{2} + b^{2})^{½} = 1 If the latter condition is not satisfied, we only have to divide a,b and c by the above square root. We can then write the above equation of line l as the dot product: x ⋅ n = c where The normal vector n is perpendicular to line l and has length 1. For any vector x, starting at O, the dot product x ⋅ n is the projection of vector x on n. This also applies if the endpoint of x lies on the line l as shown in Figure AG11(b); in this case we have x ⋅ n = c. We find the desired distance between point P and line l by projecting OP also on n and computing the difference of the two projections: Distance between P and line l = OP ⋅ n  c = ax_{P} + by_{P}c Although the figure in AG11(b) applies to the case where c > 0, this equation is also valid if c is negative or zero, or if O lies between line l and the line through P parallel to l. Both OP ⋅ n and c are scale factors for the same vector n. The absolute value of the algebraic difference of these 2 scale factors is the desired distance between P and l. We will refer to this algebraic difference: OP ⋅ n  c = ax_{P} + by_{P}c as a signed distance in subsequent discussions. Projection of a Point on a LineSuppose that a line l and a point P (not on l) are given and that we want to compute the projection P' of P on l (See Figure AG10). This point P' has 3 interesting properties:
As in the previous section, we discuss 2 solutions: one for a a line l given by 2 points A and B, and the other for l given as the equation x ⋅ n = b. With given points A and B on line l, the situation is as shown in Figure AG10. Recall that the method projectOnSegment tests to see if the projection P' on P on the line through A and B lies between A and B. In that method, we did not actually compute the position of P'. We will now do this, first by introducing the vector u of length 1 and direction AB: Then the length of the projection AP' of AP is equal to: λ = AP ⋅ u which we use to compute: AP' = λu Doing this straightforwardly would require a squareroot operation in the computation of the distance between A and B, used in the computation of u. Fortunately, we can avoid this by rewriting the last equation, using the two preceding ones: The advantage of the last form is that the square of the segment length AB is easier to compute than that length itself. The following method, which returns the projection P' of P on AB, demonstrates this: // Compute P' (P projected on AB): static Point2D projection(Point2D a, Point2D b, Point2D p) { float vx = b.x  a.x, vy = b.y  a.y, len2 = vx * vx + vy * vy, inprod = vx * (p.x  a.x) + vy * (p.y  a.y); return new Point2D(a.x + inprod * vx/len2, a.y + inprod * vy/len2); } Let us now turn to a line l given by its equation, which we again write as x ⋅ n = c where and (a^{2} + b^{2})^{½} = 1 Using the signed distance formula: d = OP ⋅ n  c as introduced at the end of the previous section and illustrated by Figure AG11, we can write the following vector equation to compute the desired projection P' of P on l: This should make the following method clear: // Compute P', the projection of P on line l given as // ax + by = h, where a * a + b * b = 1 static Point2D projection(float a, float b, float h, Point2D p) { float d = p.x * a + p.y * b  h; return new Point2D(p.x  d * a, p.y  d * b); } Triangulation of PolygonsIn many graphics applications it is desirable to divide a polygon into triangles. This triangulation problem can be solved in many ways. We will discuss a comparatively simple algorithm. It accepts a polygon in the form of an array of 2D Point elements containing the polygon vertices in counterclockwise order. The Triangulate method that we will discuss takes such an array as an argument. To store the resulting triangles, it also takes a second argument, an array with elements of type class Triangle, which is defined as follows: // Triangle.Net Class to store a triangle; // vertices in logical coordinates. // Uses: Point2D class Triangle { Point2D a, b, c; Triangle(Point2D a, Point2D b, Point2D c) { this.a = a; this.b = b; this.c = c; } } If the given polygon has n vertices, this triangle array should have length n  2. The algorithm works as follows. Traversing the vertices of the polygon in counterclockwise order, for every 3 successive vertices P, Q and R of which Q is a convex vertex (with an angle less than 180°), we cut the triangle PQR off the polygon if this triangle does not contain any other polygon vertices. For example, starting with polygon ABCDE in Figure AG12, we cannot cut triangle ABC because this contains vertex D. Nor is triangle CDE a good candidate, because D is not a convex vertex. There are no such problems with triangle BCD, so that we will cut this off the polygon, reducing the polygon ABCDE to the simpler one ABDE:
Some code relevant to this discussion is added to our Tools2D class below: // Uses: Point2D and Triangle (discussed above). class Tools2D { static float area2(Point2D a, Point2D b, Point2D c) { return (a.x  c.x) * (b.y  c.y)  (a.y  c.y) * (b.x  c.x); } // ABC is assumed to be counterclockwise static boolean insideTriangle(Point2D a, Point2D b, Point2D c, Point2D p) { return Tools2D.area2(a, b, p) >= 0 && Tools2D.area2(b, c, p) >= 0 && Tools2D.area2(c, a, p) >= 0; } // p contains all n polygon vertices in CCW order. // The resulting triangles will be stored in array tr. // This array tr must have length n  2. static void triangulate(Point2D[] p, Triangle[] tr) { int n = p.length, j = n  1, iA=0, iB, iC; int[] next = new int[n]; for (int i=0; i
We will utilize Visual Studio code complete wherever possible to minimize the chance of syntax errors. In order to maximize the C# code complete editor, which is truly an incredible work of software, the program will be structured so that objects are defined before they are called out. I have developed a Point2D class, that automatically compensates for and will work with either floating point, or integer values. Normally, I am content with the C# restrictions on data types, but in the case where so many conversions are made between integers and floats, as in points, lines, polygons, etc., I decided to let the class do the bookkeeping. The Point2D will be a subclass of Tools2D, to help keep the code complete editor from getting any more cluttered than necessary: The following diagram is the current state of the Tools2D class, which only contains the Point2D subclass at this point. We will be adding to the tools class as necessity warrants:
Let's open up the Point 2D Class Descriptor Region and see what's under the hood:
As expected, just another outline. Hopefully, we can get to a couple thousand lines of undocumented code, with 3letter variable names, so we can start doing some Real Programming:. Let's take a look at the Class Variables and see if there are any real C# statements yet:
The {get; set;} variable descriptor allows the variable to be used as a property, rather than simply a variable. At this point, we are not interested in "preconditioning" these class variables, hence, the empty get/set code. Again, maximizing the utilization of Visual Studio code complete, changing the variable to a property, signals the public nature of the class data. The downside is that all properties will have to be defined in the constructor, as in C++, rather than at declaration time. The variables (properties) xf and yf can be summoned to hold the floating point representation of the underlying data. Similarly, X and Y are used to represent the integer value of the data held in the Point2D class. A look at the different constructors shows several ways in which instantiation of this class can be utilized:
Several Property parameters have been created to allow conversion with standard preexisting Data Types:
Now that we have completed our support classes, we are ready to look at class variables for our specific application:
The Class level variables and their usage is given below:
The constructor outline:
That concludes the Constructor Initialization. Returning to the main class Elements:
We will use the MouseMove event to capture the Client Area current mouse location and display the information:
We will use the MouseClick event to capture the current Mouse location and save it as a new vertex:
We will use the firstPoint flag to decide whether the current click is the first vertex, subsequent vertex locations, or Polygon Complete Event:
If the firstPoint flag indicates a Polygon Complete Event, convert our Point2D list into a PointF array so we can perform a FillPolygon operation:
The program execution attempted to create a Hexagon by use of 6 mouse clicks. The values used for the vertices were at the following locations:
During program execution, the mouse location status bar can be used to assist in placing the vertices at the proper locations. Since the Snap Value was set to 25 pixels, any of the above values within 12 pixels would snap to the correct location. The following is the result of the program execution:
Triangulation of Polygon ExampleOur next step will be take the polygon and translate it into the corresponding Triangles. The reason we choose triangles as this is the primitive type used by the gpu, and it will be imperative, in order to fully utilize the capabilities of the gpu, we at least understand the underlying methodology. I don't know about you, but looking at repeating the same code over and over for the next 20 or so applications that we are about to develop in this section, evokes some feelings of aversion on my part. So, we will start off by extending some of the characteristics and capabilities of the basic System.Windows.Form class as is designated in the following code. As you know, the colon (:) operator preceding Form can be read as inherits or extends for those with Java programming preference. The new class will be called CgForm for Computer Graphics Form:
Basically, this class puts a status bar at the bottom of the form, for date/time & mouse position. A tool tip panel is also included that can be used to give any information to the user that we deem important at runtime:
Since we only have 1 constructor type at this point, it is not necessary to pull the code out of the constructor and put it in an InitComponents method. You are welcome to do so, if you wish, but, I see no need or advantage at this point:
Most of the initial applications will easily fit on a 600 x 600 form. If we base the dimensions of our objects on the form Width or Height parameters, the object size will adjust accordingly, which is we set ResizeRedraw to true:
At this point, most of functionality enhancement is the automatic placement of the status bar at the bottom of the form, so we have a limited number of variables that we will be utilizing:
The next section initializes the StatusPanelParent which is the container for any StatusBarPanels that we wish to be included in that particular status bar. Since I am halfblind I created a new font a little larger than normal, that is visible without my binoculars. The class AvailableFonts is a static class I created by outputting the AvailableFontFamilies class information to a file creating a static class. That way, the Code Complete can give me a listing of the available fonts, without me having to look them up somewhere else (because I am admittedly a bit lazy):
The tool tip status panel can be used at some point in the future in conjunction with the OnMouseOver overRide, to give the user information about the particular control and it's functionality. For now, we are just indicating one of our Shortcuts. Since this is the panel that will most likely need to adjust size based on the varying content length, the AutoSize parameter gets the Spring AutoSizing parameter:
The mouse position status panel will give the mouse location when positioned over our form relative to the control over which the mouse is over. The EventArgs parameter contains the location relative to the specific control over which the mouse is positioned:
The Date and Time Status Panels give the user the current time and date utilizing our enhanced Font:
A timer interval or 100 milliSeconds provides a fairly smooth time update for the 1 second timer. Slowing the update to 2300 milliseconds, will probably be acceptable as well, over 500 mS starts the update to look a little choppy.. 100 mS is usually satisfactory for RealTime updates such as the Mouse Position as well, while not excessively taxing the processor running @ 500 picoSeconds/operation. Don't be looking for the clock to be running much faster than Plank's time constant any time soon, since this is the smallest time period possible(at the macroscopic level in which most of us currently reside): Planck time (t_{p}) ≈ 5.39106 x 10^{44} seconds
While we are on the subject of time (what is time, anyways???). When I used to ask my mother what time was, she would give me an answer like "It's 7:30, you dumdum". Somebody(Connie Fox?) in my Physics class in college said it was "The property of matter that inhibits all events from occuring simultaneously.". I guess I'll go with the 7:30 explanation. I digress... The status panel timer currently only updates the Status Panel Time and Date. Using DateTime.Now gives us the current system RealTime:
If we use the OnMouseMove overRide, we can get the current mouse location from the EventArgs parameter. We store that information in our MouseLocation class level variable, for use by other methods in the class. Note do not confuse this with MousePosition which gives the mouse location in relative screen coordinates:
And finally, we come to the OnClosing Event OverRide. When attempting to exit the program, if a graphics driver request is issued, before program shutdown is complete, an exception occurs. This exception isn't particularly threatening, just annoying, as Windows asks you to acknowledge that you did something terrible like try to draw some graphics with a disposed driver. So, if there is a chance, the driver is disposed, I'd rather not be informed of my infraction. Thus the inclusion of the following override:
The following illustration is the goal of the next application:
Figure Tr15a shows the class outline for the Divide Polygon into Triangles Form App. We can see the change from inheritance from the standard windows form class to the newly created CgForm class discussed above.
Basically, this application expands on the create polygon application in the previous example. After the polygon is created, we will apply the Triangulation method of the Tools2D class, then color each triangle created individually.
The major difference in this Class Variable section is the introduction of the of Point[] vertexPoints array declaration. The purpose of this array is to preload the data into the Vertices variable so that we may simulate the data being entered manually without actually having to perform the tedious operation of entering vertices with mouseclicks. Taking a look at the constructor shows the much needed simplification by moving redundant code generation to the CgForm class:
In order to select the Preload Option, a RightClick option will be added to the OnMouseClick overRide as indicated in the method outline below:
Expansion of the Right Mouse Click region shows the method to preload the Vertices list with the vertexPoints data:
The OnPaint overRide Outline remains unchanged from the example above:
Expansion of the Complete Polygon And Fill Region, however, shows some significant changes to the OnPaint method, even though the base outline remains the same:
Expansion of the Initialize Polygon Divide Variables Region calls out a new Tools2D boolean method: VerticesInCcwDirection. As you may recall, it was decided to declare polygons in CCW order. If the Vertices are not in CCW order, we need to know this, so we can make the necessary adjustments:
A peek at our Tools2D class shows us that a couple of new static methods have unexpectedly snuck into the new class outline. Hopefully, they can provide some useful benefit in our analysis of geometric figures:
Of course, the first one we need to look at is Vertices in CCW Order Test:
What we see going on here is we first find the lowest value vertex, then determine if the 3 vertices define a triangle by calculating area the formed by the lowest vertex and the vertices on either side of the lowest vertex. If a valid triangle is formed (area > 0), we can conclude that the vertices are in the CCW direction. The next method, we need to investigate then, is the Area By 3 Points method:
As we can clearly see, this is just the C# implementation of the Area formula developed above. Returning to the OnPaint OverRide method, we continue by expanding the Create CCW Array of Points from Vertices Region:
This region creates the array directly from the Vertices List of Point2D data Points. If the vertices are not CCW, the order is reversed to correctly line up the vertices for the FillPolygon method. Next we expand the Initialize Polygon Fill Variables Region:
The Initialize Polygon Fill Variables region instantiates a list of Tools2D.Triangle class variable type. This must be another unexpected entry into the Tools2D class. Perhaps we should investigate:
Pretty straightforward, except perhaps for the ToPoints Property. This can be used to create an Array of Point[] variable types for use with the DrawPolygon and FillPolygon graphics device methods. Returning to the OnPaint method, the final step will be to create the Triangle List, and fill the Triangles with some arbitrary color:
The Tools2D.Triangulate method is called to actually make the conversion. If the conversion fails, the method returns a false and we display and empty black screen to signify conversion failure. For completeness, we will need to expand the Tools2D.Triangulate method:
It's never easy!!! Since this is an outline of 4 regions, we have at least 4 more regions to analyze. We will begin by expanding the Method Variables Region:
The NextIndex[] array variable simply points to the next vertex. We begin by presetting the first value to the last vertex. Next, we expand the Create Index to Next Vertex region:
The next region we are interested in is the Vertex to Triangle Conversion Region Outline:
This region initializes the aVertexIndex variable as well as the triangle index counter loop. This loop attempts to create NumberVertices2 Triangles. Expansion of the Loop Variables region gives us:
The Tools2D.Point2D vertices are created to hold each of the triangle vertex positions. A triangleFound variable is created to allow an exit condition for the following while loop. Expansion of the Loop Through Vertices to Find Next Triangle Region Outline gives us:
The while loop is controlled by a flag indicating a triangle was created or the fact that there are no more vertices to check. Expansion of the Get Next 3 Vertices region gives us:
This region sets the vertex index variables and then extracts the vertex data from the Vertices ArrayList variable. Expansion of the Check 3 Vertices 4 Triangle region gives us:
A test is done to ensure that the vertices are in the CCW direction by the Area By 3 Points static method. If the vertices are oriented properly we continue to the next step performed in the Test Each Vertex region:
The vertexIndex is incremented until the last vertex(aVertex) has been verified. A call to the static method Inside Triangle is called to ensure the vertex under test actually lies within the specified region. Expansion of the Inside Triangle Test Method Region gives us:
If the point under test creates a valid triangle with each of the container triangle vertices, we can be confident the point under question lies in the region (or on the border of) the area specified by the container triangle. Exiting the Test Each Vertex loop sends us into the Add Triangle to List if Valid Region. Expansion of the Add Triangle Region gives us:
If the index variable is pointing to the aVertex data point, we have confirmed that the triangle has been validated and may be added to the Triangle ArrayList. After all triangles have been added to the Triangle ArrayList we enter the Return Success or Failure Region. Expansion gives us:
If the correct number of triangles have been made, a successful conversion has taken place. The results of this final test are given as a return value from the Tools2D.Triangulate static method. If triangulation properly executed, we display the Triangulated regions. Otherwise, an empty black screen is displayed, thus concluding the Divide Polygon into Triangles methodology. Line To Point Distance ExampleThe next example deals with determining the shortest path from a point to a line or line segment, determining the coordinates of intersection and calculating the distance. The following diagram is an example of the program output:
A quick view of the TrinaglePointRelation class outline shows 4 major areas of interest: Class Variables, Constructor, MouseClick OverRide, & OnPaint OverRide:
We begin our analysis with expansion of the Class Variables region:
As in the previous example, we are presetting the Triangle class with the vertexPoints Point[] array. The vertexPoints will be preloaded into the Vertices ArrayList and sent to the testTriangle constructor. testPoint will be used to contain the location of mouse when the user initiates a LeftClick event. Expansion of the Constructor region gives us:
We see a Form Title, Vertices instantiation, and instructions to the user to RightClick the mouse, to trigger a Preload event, which will be displayed in the Status Panel docked at the bottom of the form. Expansion of the Mouse Click OverRide region gives us:
Unsurprisingly, the mouseRightClick preloads the Vertices and instantiates a testTriangle object. Invalidate will trigger the OnPaint event. A LeftMouseClick will save the current MouseLocation value in the testPoint data point, set the drawTestPoint flag, and trigger an OnPaint event. This indicates the majority of the work will be done or called out from the OnPaint overRide. Expansion of the OnPaint OverRide region gives us:
Thanks to the Visual Studio Region Code Collapsing option, this method appears deceivingly simple. There are only 3 sections(regions) of interest: Initialize Graphics Device, Draw Lines Between Vertices, & Draw Lines Between Point and Segments. But wait, there's more... Expansion of the Initialize Graphics Device gives us:
In this region, we capture the Graphics Paint Event Argument and save it in the g variable. We then proceed to clear the form with White Paint. This concludes the detailed analysis of the Initialize Graphics Device region. Expansion of the Draw Lines Between Vertices region gives us:
What's This???? One stinking line of code? Are you serious? Where are the 600 lines of vague, ambiguous, cryptic code that we real programmers have come to know and love? Just imagine how busy we could be: tiptapping the keyboard for hours on end, cursing, swearing and hours of debugging!!! If you try and pull this one line statement on the boss, he is likely to fire you over your inability to get any meaningful work done. Oh wait.... he did. Boy, is he clever!!!! No one is going to pull a fast one on this fella... I digress. Actually, there are a few lines of code behind this one statement. It's just that I quickly tire of redundant code, and I just moved the mess up into the class, and created a method which then executes those 600 lines of cryptic code...NOT. Expansion of the Triangle Draw Method Outline gives us:
The Draw method contains 2 regions of interest:
Expansion of the Method Variables region gives us:
The pen for drawing the triangle edges is fixed in this example, but by making it a property, you can change line color, or pen width, if the application demands that capability. The item of real interest here, however, is the VertexPrintLocations method call used to set the printPoints property value. Turning our attention to the parent class Tools2D parent class, expansion of VertexPrintLocations gives us:
The focus of this method is quite straightforward:
Expansion of the Method Variables region gives us:
The only container required for this method will be an Array List containing the coordinates of the vertex labels. Expansion of the Determine Location Label for Each Vertex gives us:
Looping through each of the vertices, we see 4 operations that are performed on each of the vertices:
Expansion of the Preset Arbitrary Test Points region gives us:
What we are doing here is simply creating a set of points on one side of each vertex, and then testing for line presence. With this information we know which direction the Vertex is pointing and can place the label accordingly. Expansion of the Test for Vertex Pointing Right region give us:
Now that we know which way the vertex is pointing, we can set the xCoordinate accordingly. Next, we need to determine if the ycomponent of the vertex is pointing up or down. Expansion of the Test for Vertex Pointing Up gives us:
Once the direction of all the lines approaching the vertex are known, we have enough information to place our label accordingly. The Vertex Points Left region is simply the corollary to the Vertex Points Right Region, therefore, we do not need to analyze that section at this time. Expansion of the Add Vertex Label Coordinates gives us:
As we can see, the new coordinate is added to the Array List, and the completed list is returned as a parameter to the calling routine. This concludes analysis of the Determining Vertex Label Coordinates method. Returning the the Triangle Draw method. Expansion of the Draw Each Vertex & Label region gives us:
What we are doing here is:
This concludes analysis of the Triangle Class  Draw Method. We now return attention to the OnPaint OverRide method. Expansion of the Draw Lines Between Point and Segments region gives us:
This section of code gets executed only when the user RightClicks some point on the form, as indicated by the drawTestPoint flag. This section has 4 subRegions, which are:
Expansion of Draw Test Point gives us:
This region is responsible for:
The code to draw a cross from the previous example was consolidated and added as a classlevel method for the Point2D class. Expansion of the Draw Cross At Point method outline of the Point2D class gives us:
The regions in this method required to complete this operation are:
Expansion of the Set up Cross Endpoints region gives us:
The crossLength variable has been added as a property to the Point2D Class. Expansion of the Draw Cross region gives us:
The crossColor Color variable has been added to the Point2D class as a property as well. Expansion of the Print Label region gives us:
A quick method to access an arbitrary font is by using the ActiveForm property of a class that has inherited the Form characteristics. Returning to the OnPaint OverRide method, we continue by expanding the Display Inside or Outside Triangle region:
Based on the boolean result of the ContainsPoint method of the Triangle class, the relative position of the mouseclick is updated in the Tool Tip Status Bar, inherent to the CgForm class we created in a previous example. The Contains Point method was added to the Triangle class since it was detailed in a previous example. Therefore, we will now briefly turn our attention to that method:
The idea here is rather simple. We have defined a valid triangle as one in which all the vertices are in CCW order. If the triangle is valid, the area will be nonnegative. If the point under question lies outside the border of the valid triangle, then, at some point, the vertices will not be in CCW order, and will return a negative value. Apparently, we have not yet discussed the AreaBy3Points method of the Tools2D class. For those of you interested, we will now turn our attention briefly to that minor neglected matter:
In the discussion above The area of a Polygon, we deduced the following formula for the area of an arbitrary triangle: Area(Δ ABC) = (X_{A}  X_{C})(Y_{B}  Y_{C})  (Y_{A}Y_{C})(X_{B}  X_{C}) AreaBy3Points is simply the implementation of that formula. We now return to the OnPaint method and expand the Display Test Point Coordinate Info region:
This section of code displays the point coordinate information on the form, as well as the header for the following segment information. Expansion of the Display PointSegment Info region gives us:
The Display PointSegment Info region is divided into 4 subregions:
These operations are performed on each line segment. Expansion of the Define and Draw LinePoint Intersection region gives us:
An object of type Tools2D.LineSegment is created so that we can call the ProjectionOf method to calculate the shortest line segment between the line and Point2D object passed as a parameter. Expansion of the LineSegment.ProjectionOf method gives us:
The segment length is calculated, the inner product is then calculated and inserted into the constructor for a new Point2D object, to give us the point on the line closest to the point sent as a parameter. The coordinates are then returned to the calling routine. A more detailed description is given in the Lines section above. Now that we have the coordinates of all the intersection points, we are ready to start labeling the vertices. Expansion of the Calculate Labels for Vertices region gives us:
The responsibility of this region is to calculate the vertices used in creation of the line segment, and then accordingly create a label for that line segment. The char variables hold the Segment Start & Segment End vertex labels, respectively. Expansion of the Calculate Distance of Line region gives us:
As we can see, this is the implementation of the standard distance formula: Distance = (X^{2} + Y^{2})^{½} The final task in our analysis is the Display Distance and Coordinates region. Expansion gives us:

