Silicis Technologies Silicis Technologies

Silicis Technologies



Autonomous Air and Land Based Robotics



Home


Elementary Concepts


Applied Geometry


Geometric Transformations


Perspective




































Computer Graphics - Applied Geometry

In this section we will discuss some mathematical concepts useful in Computer Graphics. Topics included are:

Vectors, Dot Product, Determinants, Vector Product

Vectors

We 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 AG-1: Two Equal Vectors


Figure AG-1 shows 2 representations of the same vector:

a = PQ = b = RS

Thus, a vector is not altered by a translation (Δ Position). The sum c of the vectors a and b, written

c = a + b

can be obtained as the diagonal of a parallelogram, with a, b and c starting at the same point, as shown in figure AG-2:

Figure AG-2: Vector Addition


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 |c||a|. 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:

u + v = v + u

(u + v) + w = u + (v + w)

u + 0 = u

u + (-u) = 0

c (u + v) = cu + cv

(c + k)u = cu + ku

1u = u

0u = u

Figure AG-3 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 right-handed, 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.

Figure AG-3: Right-Handed Coordinate System


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 k

The real numbers x, y and z are the coordinates of the endpoint P of vector v = OP. We often write this vector as:

v = [ x y z ]    or    v = (x, y, z)

The numbers x, y, z are sometimes called the elements or components of vector v.

The Inner Product

The inner product or dot product of two vectors a and b is a real number written as a ⋅ b and defined as:

a ⋅ b = |a||b| cos γ if a ≠ 0   and   b ≠ 0 (AG.1)
a ⋅ b = 0 if a = 0   or   b = 0

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

i ⋅ i     =     j ⋅ j    =     k ⋅ k     =     1
i ⋅ j     =     j ⋅ i     =     j ⋅ k     =     k ⋅ j     =   0     (AG.2)

Setting b = a in Equation (AG.1), we have a ⋅ a = |a|2, so

|a| = √(|a ⋅ a|)

Some important properties of inner products are

c(ku ⋅ v) = ck(u ⋅ v)

(cu + kv) ⋅ w = cu ⋅ w + kv ⋅ w

u ⋅ v   =   v ⋅ u

u ⋅ u   =   0   only if   u   = =  0

The inner product of two vectors u = [ u1 u2 u3 ] and v = [ v1 v2 v3 ] can be computed as

u ⋅ v = U1V1 + U2V2 + U3V3

We can prove this by developing the right-hand side of the following inequality as the sum of the nine inner products and then applying Equation (AG.2):

u ⋅ v = (U1i + U2j + U3k) ⋅ (V1i + V2j + V3k)

Determinants

Before 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:

{ a1x + b1y = c1    (AG.3)
a2x + b2y = c2

We can them multiply the first equation by b2, the second by -b1, and add them, finding

(a1b2 - a2b1)x = b2c1 - b1c2

Next, to find y we can multiply the first equation by -a2, the second by a1, and add as was done to find x, obtaining:

(a1b2 - a2b1)y = a1c2 - a2c1

As long as a1b2 - a2b1 ≠ Zero, we can divide both equations and complete the solution:

x = b2c1 - b1c2         y = a1c22 - a2c1
a1b2 - a2b1 a1b2 - a2b1

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 Di is obtained by replacing the ith column of D with the right-hand 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 so-called minor determinant Mij 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 R2 through the points P1(x1, y1) and P2(x2,y2) 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 R2, and second, that the coordinates of both P1 and P2 satisfy this equation, for if we write them in the first row, we have two identical rows. Similarly, the plane in R3 through three points P1(x1,y1,z1), P2(x2,y2,z2), P3(x3,y3,z3) has the equation:

which is much easier to remember than one written in the conventional way.

Vector Product

The vector product or cross product of two vectors a and b is written

a × b

and is a vector v with the following properties:

if a == cb for some scalar c, then v = 0.
Otherwise the length of v is equal to

|v| = |a||b| 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 right-handed 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 AG-4 shows

Figure AG-4: Vector Product a x b


The following properties of vector products follow from this definition:

(ka) × b = k(a × b)       for any real number k
a × (b + c) = a × b + a × c
a × b = -b × a

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 AG-3) we have:

i × i = 0 j × j = 0 k × k = 0
i × j = k j × k = i k × i = j
j × i = - k k × j = - i i × k = - j

Using these vector products in the expansion of:

a × b = (a1i + a2j + a3k) × (b1i + b2j + b3k)

we obtain

a × b = ( a2b3 - a3b2)i + ( a3b1 - a1b3)j + ( a1b2 - 12b1)k

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| = |a||b| sin γ is the length of the vector a × b.

The Orientation of 3 Points

We 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 xy-plane and we want to know their orientation; in other words, we want to know whether we turn counter-clockwise when visiting these points in the given order. Figure AG-5 shows the possibilities, which we also refer to as positive and negative orientation, respectively:

Figure AG-5: Counterclockwise && Clockwise Orientation of A,B,C


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 xA, yA, xB, yB, xC, yC.

Figure AG-6: Using Vectors a and b instead of triangle edges CA and CB


Let us define the two vectors a = CA and b = CB, as shown in Figure AG-6. Clearly, the orientation of the original points A, B and C is positive if we can turn the vector a counter-clockwise 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 AG-6 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 AG-6, 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 (a1, a2, 0) and (b1, b2, 0), we have:

a = a1 i + a2 j + 0k
b = b1 i + b2 j + 0k

which, when written in determinant form becomes:

This expresses the fact that a × b is perpendicular to the xy-plane and either in the same direction as

k = i × j

or in the opposite direction, depending on the sign of a1b2 - a2b1. If this expression is positive, the relationship between a and b is similar to that of i and j: we can turn a counter-clockwise 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 Solution

It 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 x-axis and β between b and this axis (See Figure AG-6). 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 a1b2 - a2b1 have the same sign. Due to the unfamiliarity of the above trigonometric formula, the more visual 3D approach could be easier to remember.



Polygons

A polygon is a sequence of vertices: P0, P1, . . ., Pn-1, 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 x-coordinate 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 x-coordinate. Therefore, among all vertices with an x-coordinate equal to this minimum value, we choose the lowest one, i.e. the one with the least y-coordinate.

The area of a polygon

As we have seen in Figure AG-4, 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 AG-6 we have:

Note that this is valid only if A, B and C are labeled counter-clockwise; if this is not necessarily the case, we have to use the absolute value of a1b2 - a2b1.

Since

a1 = xA - xC

a2 = yA - yC

b1 = xB - xC

b2 = yB - xC,

we can also write:

2 Area(Δ ABC) = (xA - xC)(yB - yC) - (yA - yC)(xB - xC)



Point In Triangle Test

Determining 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 AG-8 shows, this is the case if the orientation of the triangles ABP, BCP and CAP is the same as that of triangle ABC:

Figure AG-8: Orientation used to test if P lies within 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= 0 && 
		Tools2D.area2(b, c, p) >= 0 && 
		Tools2D.area2(c, a, p) >= 0; 
}

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 Test

The 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 half-line, which starts at P and extends to the right. The number of intersections of this horizontal half-line 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 AG-9:

Figure AG-9: Polygon and half-line starting at P


In this case, we simply ignore the polygon edges, even if they have the same y-coordinate as P, as is the case with edge 4-5 in this example. If a vertex occurring as a "local maximum or minimum" happens to have the same y-coordinate 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:

yiyp < yi+1   or   yi+1yp < yi

This implies that the lower endpoint of a non-horizontal edge is regarded as part of the segment, but the upper endpoint is not. For example, in Figure AG-9, vertex 8 (with y8 = yp) is not counted at all because it is the upper endpoint of both edge 7-8 and edge 8-9. By contrast, vertex 12 (with y12 = yp) is the lower endpoint of the edges 11-12 and 12-13 and thus counted twice. Therefore, in this example, we count the intersections of the half-line through P with the seven edges 2-3, 3-4, 5-6, 6-7, 10-11, 11-12, and finally 12-13 with no others.

Since we are considering only a half-line, we must impose another restriction on the set of edges satisfying the above test, selecting only those whose point of intersection with the half-line 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 counter-clockwise for the triangle 2-3-P in Figure AG-9, which implies that P lies to the left of edge 2-3. It is also counter-clockwise for the triangle 7-6-P. In both cases, the lower endpoint of an edge, its upper endpoint and point P, in that order, are counter-clockwise. 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 0) || 
		(pol[i].y <= y && y < pol[j].y && Tools2D.area2(pol[i], pol[j], p) > 0)) 
		b = !b; 
		j = i; 
	} 
	return b; 
}

This static method, as well as several others will be added to the Tools2D class.

Point On Line Test

Testing 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):

a = yA - yB
b = xB - xA
c = xByA - xAyB

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 rounding-off errors.

Testing whether a Point Lies on a Line Segment

If 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 xAxB or yAyB. if xAxB we test whether xP lies between xA and xB,; if not, we test whether yP lies between yA and yB, 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 xAxB 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 AG-10 shows:

Figure AG-10: Projection P' of P on line AB between A and B


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 = AB2 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 Line

We 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:

Figure AG-11: Distance Between Point P and Line l


If the line l is given as an equation, we assume this to be in the form

ax + by = c

where

(a2 + b2)½ = 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 AG-11(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|   =   |axP + byP-c|

Although the figure in AG-11(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   =   axP + byP-c

as a signed distance in subsequent discussions.



Projection of a Point on a Line

Suppose 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 AG-10). This point P' has 3 interesting properties:

  1. P' is the point on l that is closest to P.
  2. The length of PP' is the distance between P and l (computed in the previous section).
  3. PP' and l are perpendicular

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 AG-10. 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 square-root 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

(a2 + b2)½ = 1

Using the signed distance formula:

d = OP ⋅ n - c

as introduced at the end of the previous section and illustrated by Figure AG-11, 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 Polygons

In 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 counter-clockwise 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 counter-clockwise 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 AG-12, 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:

Figure AG-12: Cutting Off Triangles


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 counter-clockwise
	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= 0) 
				{
					j = next[iC]; 
					while (j != iA && !insideTriangle(a, b, c, p[j])) 
						j = next[j]; 

					 // Triangle ABC contains no other vertex:

					if (j == iA) 
					{ tr[k] = new Triangle(a, b, c); next[iA] = iC; triaFound = true; } 
				} 
				iA = next[iA]; 
			} 

			if (count == n) 
			{ 
				System.out.println("Not a simple polygon" + 
				" or vertex sequence not counter-clockwise."); 
				System.exit(1);
			}
		}
	}

	static float distance2(Point2D p, Point2D q) 
	{ 
		float dx = p.x - q.x, dy = p.y - q.y; 
		return dx * dx + dy * dy; 
	} 
}

Now we will begin to develop a .Net program that allows us to create a polygon with N-Vertices by simply clicking the mouse a few times on the screen. The following is our application compressed with the #region statements condensing the code below:

Figure CP-1: Create Polygons Class Outline

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 book-keeping. The Point2D will be a sub-class 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:

Figure CP-2: Tools2D Class Outline

Let's open up the Point 2D Class Descriptor Region and see what's under the hood:

Figure CP-3: Point2D Class Outline

As expected, just another outline. Hopefully, we can get to a couple thousand lines of undocumented code, with 3-letter 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:

Figure CP-4: Point2D Class Variables

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:

Figure CP-5: Point2D Constructors

Several Property parameters have been created to allow conversion with standard pre-existing Data Types:

Figure CP-6: Size and Point Data Type Converters



Now that we have completed our support classes, we are ready to look at class variables for our specific application:



Figure CP-7: Class Variables - Create Polygon Class

The Class level variables and their usage is given below:

Variable Declaration Usage
programEnding: flag used to inhibit redrawing the screen after the program shutdown process has initiated - otherwise an exception will occur for attempting to use the disposed graphics device.
firstPoint: flag used to indicate the next vertex entered will be the primary vertex.
tools2D Class declaration which will give us access to our custom geometric manipulation code.
Vertices Storage location for each mouse click location.
x0 x coordinate of primary vertex.
y0 y coordinate of primary vertex.
yMin minimum vertical hysteresis allowed to decide if current mouse click is a new vertex or a polygon complete request.
xMin in conjunction with minimum vertical hysteresis is used to decide whether the most recent mouse click is a new vertex or a notification that the polygon is complete.
snapValue vertical and horizontal snap to grid value
MouseLocation Current Mouse Location relative to Client Workspace
statusPanelParent Container for StatusBarPanel controls listed below.
MouseLocationStatusPanel Panel Displaying Current Client Mouse Location
DateStatusPanel Panel Displaying Current Date
TimeStatusPanel Panel Displaying current time
StatusPanelTimer Timer used to update current time and Date

Figure CP-7a: Variable Declaration & Usage



The constructor outline:

Figure CP-8: Constructor Outline



Figure CP-9: Initialize Class Level Variables



Figure CP-10: Initialize Parent Form



Figure CP-11: Initialize Status Panel Parent



Figure CP-12: Initialize Mouse Location Status Panel



Figure CP-13: Initialize Current Date Status Panel



Figure CP-14: Initialize Current Time Status Panel



Figure CP-15: Initialize Current Date/Time Timer



That concludes the Constructor Initialization. Returning to the main class Elements:



Figure CP-16: Date-Time Timer Tick Event



We will use the MouseMove event to capture the Client Area current mouse location and display the information:



Figure CP-17: Mouse Move OverRide



We will use the MouseClick event to capture the current Mouse location and save it as a new vertex:



Figure CP-18: Mouse Click OverRide Method Outline



Figure CP-19: MouseClick OverRide - Snap Vertex Location to Nearest Grid Intersection



We will use the firstPoint flag to decide whether the current click is the first vertex, subsequent vertex locations, or Polygon Complete Event:



Figure CP-20: MouseClick OverRide - Decide Vertex Type and Save in Vertex Array(List)



Figure CP-21: On Paint OverRide Event Handler Outline



Figure CP-22: On Paint OverRide - Initialize Graphics Device



Figure CP-23: On Paint OverRide - Small Square Around Primary Vertex



Figure CP-24: On Paint OverRide - Draw Lines Between Vertices



If the firstPoint flag indicates a Polygon Complete Event, convert our Point2D list into a PointF array so we can perform a FillPolygon operation:



Figure CP-25: On Paint OverRide - Complete Polygon and Fill



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:

200, 100
300, 100
375, 175
300, 250
200, 250
125, 175
200, 100 (signal used to indicate (polygonComplete)

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:

Figure CP-26: Create Polygon With Mouse Click Sample Output



Triangulation of Polygon Example

Our 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:


Figure Tr-1: CgForm Class Descriptor Outline



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:

Figure Tr-2: CgForm Class Level Variables



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:

Figure Tr-3: CgForm Constructor Outline



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:

Figure Tr-4: CgForm Form Variable Initialization



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:

Figure Tr-5: CgForm Class Level Variable Initialization



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 half-blind 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):

Figure Tr-6: CgForm StatusPanelParent Variable Initialization



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:

Figure Tr-7: CgForm Tool Tip Status Panel Variable Initialization



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:

Figure Tr-8: CgForm Mouse Location Status Panel Variable Initialization



The Date and Time Status Panels give the user the current time and date utilizing our enhanced Font:

Figure Tr-9: CgForm Date Status Panel Variable Initialization



Figure Tr-10: CgForm Time Status Panel Variable Initialization



A timer interval or 100 milliSeconds provides a fairly smooth time update for the 1 second timer. Slowing the update to 2-300 milliseconds, will probably be acceptable as well, over 500 mS starts the update to look a little choppy.. 100 mS is usually satisfactory for Real-Time 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 (tp) ≈ 5.39106 x 10-44 seconds

Figure Tr-11: CgForm Date/Time Timer Variable Initialization



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 dum-dum". 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 Real-Time:

Figure Tr-12: CgForm Date/Time Timer Tick Event



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:

Figure Tr-13: CgForm OnMouseMove Event OverRide



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:

Figure Tr-14: CgForm OnClosing Event OverRide



The following illustration is the goal of the next application:

Figure Tr-15: Hexagon Divided Into Triangles



Figure Tr-15a 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.

Figure Tr-15a: Hexagon Divided Into Triangles Class Outline



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.

Figure Tr-16: Triangulation Application Class Variables



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 mouse-clicks.

Taking a look at the constructor shows the much needed simplification by moving redundant code generation to the CgForm class:

Figure Tr-17: Divide Polygon Into Triangles Constructor



In order to select the Preload Option, a Right-Click option will be added to the OnMouseClick overRide as indicated in the method outline below:

Figure Tr-18: Divide Polygon Into Triangles On Mouse Click OverRide Outline



Expansion of the Right Mouse Click region shows the method to preload the Vertices list with the vertexPoints data:

Figure Tr-19: On Mouse Click OverRide Right-Click Region Expansion



The OnPaint overRide Outline remains unchanged from the example above:

Figure Tr-20: OnPaint OverRide Method Outline



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:

Figure Tr-21: OnPaint OverRide Method Complete Polygon and Fill Region Outline



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:

Figure Tr-22: Initialize Polygon Divide Variables Declaration Region



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:

Figure Tr-23: Tools2D Class Outline



Of course, the first one we need to look at is Vertices in CCW Order Test:

Figure Tr-24: Tools2D Class - Vertices In CCW Direction



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:

Figure Tr-25: Tools2D Class - Area By 3 Points



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:

Figure Tr-26: OnPaint - Create CCW Array of Points



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:

Figure Tr-27: OnPaint - Initialize Polygon Fill Variables



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:

Figure Tr-28: Tools2D - Triangle Class Descriptor



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:

Figure Tr-29: OnPaint - Create Triangles and Display Region



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:

Figure Tr-30: Tools2D - Triangulation Method Outline



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:

Figure Tr-31: Tools2D - Triangulation Method Variables



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:

Figure Tr-32: Tools2D - Create Next Vertex Index Region



The next region we are interested in is the Vertex to Triangle Conversion Region Outline:

Figure Tr-33: Tools2D - 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 NumberVertices-2 Triangles. Expansion of the Loop Variables region gives us:

Figure Tr-34: Tools2D - Vertex to Triangle Conversion Loop Variables



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:

Figure Tr-35: Tools2D - Loop Through Vertices Region Outline



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:

Figure Tr-36: Tools2D - Get Next 3 Vertices Region



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:

Figure Tr-37: Tools2D - Check 3 Vertices For Valid Triangle Region Outline



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:

Figure Tr-38: Tools2D - 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:

Figure Tr-39: Tools2D - Inside Triangle Test Method



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:

Figure Tr-40: Tools2D - Add Triangle to List Region



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:

Figure Tr-41: Tools2D - Triangle Conversion - Return Success or Failure Region



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 Example

The 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:

Figure Tpr-1:Triangle - Point Relation Sample Output



A quick view of the TrinaglePointRelation class outline shows 4 major areas of interest: Class Variables, Constructor, Mouse-Click OverRide, & OnPaint OverRide:

Figure Tpr-2:Triangle - Point Relation Class Outline



We begin our analysis with expansion of the Class Variables region:

Figure Tpr-3:Triangle - Point Relation Class Variables



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 Left-Click event.

Expansion of the Constructor region gives us:

Figure Tpr-4:Triangle - Point Relation Class Variables



We see a Form Title, Vertices instantiation, and instructions to the user to Right-Click 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:

Figure Tpr-5:Triangle - Point Relation Mouse Click OverRide



Unsurprisingly, the mouse-Right-Click preloads the Vertices and instantiates a testTriangle object. Invalidate will trigger the OnPaint event. A Left-Mouse-Click 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:

Figure Tpr-6:Triangle - Point Relation OnPaint OverRide



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:

Figure Tpr-7:Triangle - Point Relation --> OnPaint OverRide --> Initialize Graphics Device



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:

Figure Tpr-8:Triangle - Point Relation --> OnPaint OverRide --> Draw Triangle



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: tip-tapping 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:

Figure Tpr-9:Tools2D Triangle Class Draw Method Outline



The Draw method contains 2 regions of interest:

  • Declare Variables

  • Draw Each Vertex & Label

Expansion of the Method Variables region gives us:

Figure Tpr-10:Tools2D Triangle Class Draw Method Variables



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:

Figure Tpr-11:Tools2D Vertex Print Locations Outline



The focus of this method is quite straightforward:

  • Declare Variables

  • Determine Location Label for Each Vertex

Expansion of the Method Variables region gives us:

Figure Tpr-12:Tools2D Vertex Print Locations Variables



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:

Figure Tpr-13:Tools2D Vertex Print Locations Determine Location Label for Each Vertex



Looping through each of the vertices, we see 4 operations that are performed on each of the vertices:

  • Preset Arbitrary Test Points

  • Test For Vertex Pointing Right

  • Vertex Pointing Left

  • Add Vertex Label Coordinates to Array List

Expansion of the Preset Arbitrary Test Points region gives us:

Figure Tpr-14:Tools2D Vertex Print Locations Determine Location Label for Each Vertex Preset Arbitrary Test Points



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:

Figure Tpr-15:Tools2D Vertex Print Locations Determine Location Label for Each Vertex Test For Vertex Pointing Right



Now that we know which way the vertex is pointing, we can set the x-Coordinate accordingly. Next, we need to determine if the y-component of the vertex is pointing up or down.

Expansion of the Test for Vertex Pointing Up gives us:

Figure Tpr-16:Tools2D Vertex Print Locations Determine Location Label for Each Vertex
      Test For Vertex Pointing Right Test For Vertex Pointing Up



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:

Figure Tpr-17:Tools2D Vertex Print Locations Determine Location Label for Each Vertex
      Add Vertex Label Coordinates



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:

Figure Tpr-18:Tools2D Triangle Class Draw Method Draw Each Vertex & Label



What we are doing here is:

  • Drawing a line from firstVertex to nextVertex

  • Creating a Letter Label corresponding to the vertex number

  • Placing the Letter Label at the proper position

  • prepare for next vertex

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:

Figure Tpr-19:Triangle-PointRelation OnPaint OverRide Draw Lines Between Point and Segments



This section of code gets executed only when the user Right-Clicks some point on the form, as indicated by the drawTestPoint flag. This section has 4 subRegions, which are:

  • Drawing a Cross and Label where the user clicked the mouse

  • Deciding if the mouse was clicked inside or outside of our Triangle

  • Displaying the coordinates of the mouse click

  • Displaying information between the mouse click point and the closest point on each line segment

Expansion of Draw Test Point gives us:

Figure Tpr-20:Triangle-PointRelation OnPaint OverRide
      Draw Lines Between Point and Segments Draw Test Point



This region is responsible for:

  • Resetting the drawTestPoint flag

  • Creating the Line Drawing Pen

  • Drawing a cross where the user clicked the mouse on the form

The code to draw a cross from the previous example was consolidated and added as a class-level method for the Point2D class. Expansion of the Draw Cross At Point method outline of the Point2D class gives us:

Figure Tpr-21:Tools2D Point2D Draw Cross At Point



The regions in this method required to complete this operation are:

  • Setting up the Cross Endpoints

  • Drawing the Cross on the Form

  • Printing the Label for the point being designated by the cross

Expansion of the Set up Cross Endpoints region gives us:

Figure Tpr-22:Tools2D Point2D Draw Cross At Point Set up Cross Endpoints



The crossLength variable has been added as a property to the Point2D Class. Expansion of the Draw Cross region gives us:

Figure Tpr-23:Tools2D Point2D Draw Cross At Point Draw Cross



The crossColor Color variable has been added to the Point2D class as a property as well. Expansion of the Print Label region gives us:

Figure Tpr-24:Tools2D Point2D Draw Cross At Point Print Label



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:

Figure Tpr-25: Triangle-PointRelationOnPaint OverRide
      Draw Lines Between Point and Segments Display Inside or Outside Triangle



Based on the boolean result of the ContainsPoint method of the Triangle class, the relative position of the mouse-click 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:

Figure Tpr-26: Tools2DTriangle Class Contains Point 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 non-negative. 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:

Figure Tpr-27: Tools2DArea By 3 Points Method



In the discussion above The area of a Polygon, we deduced the following formula for the area of an arbitrary triangle:

Area(Δ ABC) = (XA - XC)(YB - YC) - (YA-YC)(XB - XC)

AreaBy3Points is simply the implementation of that formula.

We now return to the OnPaint method and expand the Display Test Point Coordinate Info region:

Figure Tpr-28: Triangle-PointRelation OnPaint OverRide
      Draw Lines Between Point and Segments Display Test Point Coordinate Info



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 Point-Segment Info region gives us:

Figure Tpr-29: Triangle-PointRelation OnPaint OverRide
      Draw Lines Between Point and Segments Display Point-Segment Info



The Display Point-Segment Info region is divided into 4 subregions:

  • Defining and Drawing Line Point Intersection

  • Calculate Labels (A, B, C...) for vertices

  • Calculate Length of Projection Line

  • Display Projection Line Length and Intersection Coordinates

These operations are performed on each line segment. Expansion of the Define and Draw Line-Point Intersection region gives us:

Figure Tpr-30: Triangle-PointRelation OnPaint OverRide
      Draw Lines Between Point and Segments Display Point-Segment Info
      Define And Draw Line-Point Intersection



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:

Figure Tpr-31: Tools2D LineSegment Projection Of Point On Line



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:

Figure Tpr-32: Triangle-PointRelation OnPaint OverRide
      Draw Lines Between Point and Segments Display Point-Segment Info
      Define And Draw Line-Point Intersection



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:

Figure Tpr-33: Triangle-PointRelation OnPaint OverRide
      Draw Lines Between Point and Segments Display Point-Segment Info
      Calculate Distance of Line

As we can see, this is the implementation of the standard distance formula:

Distance = (X2 + Y2)½

The final task in our analysis is the Display Distance and Coordinates region. Expansion gives us:

Figure Tpr-34: Triangle-PointRelation OnPaint OverRide
      Draw Lines Between Point and Segments Display Point-Segment Info
      Display Distance and Coordinates