CONVEX HULL CONSTRUCTION IN TWO AND THREE DIMENSIONS
by
Melody C. Gillespie
B.S., University of Colorado, 1995
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
1996
This thesis for the Master of Science
degree by
Melody C. Gillespie
has been approved
by
Date
Gillespie, Melody C. (M.S., Computer Science)
Convex Hull Construction in Two and Three Dimensions
Thesis directed by Assistant Professor Jay Rothman
ABSTRACT
This thesis presents an introduction to the concept of two and three dimensional
convex hull construction. The thesis is composed of two primary components.
The first is an introduction through text and illustrations to the fundamental
concepts, uses, and algorithms of two and three dimensional convex hull
construction. The performance of these algorithms is also discussed. The second is
an implementation of several of these algorithms in a program that visually
demonstrates how the algorithms progress. The complete source listings of the
program are included. Of specific interest are the three dimensional algorithms
which are much more complex and interesting than those of only two dimensions.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed
Dr. Jay Rothr__
111
CONTENTS
Chapter
1 Introduction .......................................................1
1.1 Applications ................................................1
1.2 Definitions................................................. 2
1.3 Predicate Left ..............................................7
2 Hull Construction Algorithms in Two Dimensions .....................9
2.1 Naive Algorithm..............................................9
2.2 Gift Wrapping Algorithm........:...........................10
2.3 QuickHull Algorithm ........................................14
2.4 Graham's Algorithm .........................................17
2.5 Incremental Algorithm ......................................19
2.6 Divide and Conquer .........................................22
3 Hull Construction Algorithms in Three Dimensions ..................25
3.1 Gift Wrapping Algorithm.....................................25
3.2 Divide and Conquer .........................................31
3.3 Incremental or BeneathBeyond Algorithm ....................36
4 Lower Bounds ......................................................39
4.1 Two Dimensions..............................................39
4.2 Three Dimensions............................................40
5 Future Study.......................................................41
Appendix A Code........................................................42
A.1 thessapp.h ....................................................42
A.2 thessapp.cpp...................................................45
A.3 point.h........................................................50
A. 4 point, cpp....................................................51
A. 5 poly.h .......................................................54
A. 6 poly, cpp.....................................................56
A. 7 polytope.h....................................................66
IV
A. 8 polytope, cpp...................................................67
A.9 edge.h...........................................................71
A. 10 edge.cpp ......................................................72
A. 11 vector.h.......................................................74
A. 12 vector, cpp....................................................75
A. 13 matrix, h......................................................78
A. 14 matrix, cpp....................................................79
A. 15 graphics.h.....................................................81
A. 16 graphics.cpp ..................................................83
A. 17 math2.h........................................................95
A.18 math2.cpp......................................................101
A. 19 random.h......................................................114
A.20 random, cpp....................................................116
A.21 timer.h........................................................120
A. 22 timer, cpp....................................................121
A.23 fileread.h................................................... 122
A.24 fileread.cpp...................................................123
A.25 hull.h.........................................................124
A.26 hull.cpp.......................................................125
A.27 gw2d.h ........................................................129
A.28 gw2d.cpp ......................................................130
A.29 grahams.h......................................................133
A.30 grahams.cpp ...................................................134
A.31 quick.h .......................................................138
A.32 quick.cpp......................................................139
A.33 inc2d.h .......................................................143
A.34 inc2d.cpp......................................................144
A.35 gw3d.h ........................................................150
A.36 gw3d.cpp ......................................................151
A.37 cube.h.........................................................166
A.38 cube.cpp ......................................................167
A. 3 9 icoshed.dat .................................................171
A.40 cube.dat.......................................................172
References ................................................................173
v
1
Introduction
One of the fundamental problems in computational geometry is the construction of
the convex hull. Intuitively, the construction of two and three dimensional hulls is
easy to visualize. In two dimensions, it is easy to envision it as wrapping a string
around the outside of a set of finite points. For three dimensions, the example of
wrapping up a package is often used (in fact, an algorithm presented in this paper
is called the gift wrapping algorithm). However, as with most mathematical
concepts, intuition is not enough, and before presenting the fundamentals of hull
construction, some definitions and background material will be provided.
1.1 Applications
The convex hull has been well studied for many years. Computing convex hulls is
as basic to the field of computational geometry as sorting algorithms are in other
applications. Convex hulls are important in their own right, but are also a
necessary component of more complex algorithms. A few examples where hull
construction plays an important role follow.
Collision Avoidance
Hull construction is often used in the field of robotic motion. The problem of
determining if a robot will collide with an object can be quite complex when the
boundaries of the robot and the object are nonconvex. The difficulty of this
problem can be reduced when the convex hulls of both the robot and the object are
considered. Two objects will not intersect if their convex hulls do not.
Fitting Ranges with a Line
In 1981, Joseph ORourke [21] discovered that finding a straight line that fits
between a collection of data ranges is equivalent to finding the convex hull of a
polygon constructed from a set of intersecting halfplanes.
Computer Graphics
Constructing convex hulls is basic to the field of computer graphics. Convex hulls
provide a convenient way to determine the boundaries of curves and surfaces in
space. A convex hull can be used as a bounding volume when an object is to be
ray traced.
1
Bounding Box
Finding the smallest box/rectangle that will enclose an object depends on its
convex hull. If the convex hull is planar, at least one edge of the hull will lie on
the rectangle. In three dimensions, at least one face of the hull will lie on the box
[22],
Shape Analysis
Currently, there is a great deal of activity in the field of shape analysis and
representation which deals with the issues of analyzing and representing two and
threedimensional shapes for computer vision. Many applications use the convex
hull of an object to help classify the object [22].
1.2 Definitions
This paper is specifically on convex hull construction in two and three dimensions.
However, hull construction can be done in any dimension. Where appropriate, the
following definitions are given in terms of ^dimensional space Rd. If applicable,
specific examples for R2 and R3 are given within each definition
Convex Set
A set S is convex if for each pair of points x and y in S, it is true that the entire line
segment xf also lies in S. Figure 1.1 shows examples of convex and nonconvex
sets.
Convex Combination
The convex combination of points p,, p2, p3, , pk is the set of points of the form
apj + + aph with at> 0 for all / and aI + + ak = 1. Thus, the combination of
two points Pi and p2, would define the line segment p^p2. This is true of all other
point combinations the convex combination of three points defines a triangle,
and the convex combination of four points defines a tetrahedron [22].
2
Convex Hull
A convex hull of a set S is denoted by conv(S). There are several equivalent ways
to define a convex hull. A few examples are given here and more can be found in
[18], [22], [28],
1. For any subset S of Rd, the convex hull conv($ is the set of all convex
combinations of points from S.
2. The convex hull of a set S <= Rd is the intersection of all convex sets in Rd
containing S. Clearly the set S is convex if and only if conv(S) = S.
3. The convex hull conv(S) of a finite set of d+\ points ph p2, pn+! in Rd
is called a ddimensional simplex if the d 1 face has d vertices. Thus in
two dimensions where d= 2, a triangle is a 2dimensional simplex and in
three dimensions (d= 3), a tetrahedron which has 4 points would be a 3
dimensional simplex.
4. The convex hull of a set of points S in d dimensions is the union of all
possible ^dimension simplexes contained in S. A two dimensional
example is shown in Figure 1.2, where a 2dimensional simplex is a
triangle. Clearly, all possible triangles of S would define conv(S).
5. The convex hull of a set of points S is the intersection of all halfspaces that
contain S. In two dimensions, a halfspace is equivalent to all the points on
one side of a line. In three dimensions, a halfspace would be all points on
one side of a plane. Figure 1.3 shows an example of a convex hull defined
by halfspaces in two dimensions.
3
6. Given an arbitrary finite set of points S in Md, the convex hull of S is the
smallest convex set containing S in the sense that the convex hull will be a
subset of any set containing S.
7. The convex hull of a set of points S in two dimensions is the convex
polygon with the smallest area that can enclose S. In three dimensions, the
convex hull would be the smallest convex tetrahedron that encloses S.
Note: Although the convex hull is actually a solid, the term convex hull is also
interchangeably used for its boundary, because once the boundary has been
described, the convex hull is determined as well. In this paper, we will describe
and refer to a convex hull by points on its boundary.
Polygon
A polygon is a closed curve on a region of a plane bounded by a finite number of
line segments. The line segments are edges and the points of intersection of these
edges are vertices. In a simple polygon, no nonconsecutive edges intersect.
Figure 1.4 shows an example of both a simple and nonsimple polygon. For the
purposes of this paper, we will only consider simple polygons.
4
Clearly, if all of the interior angles are less than or equal to 180, the polygon is a
convex polygon. Figure 1.5 shows an example of both a convex and a nonconvex
polygon.
Polyhedron
A polyhedron is a three dimensional region bounded by plane polygonal surfaces
(often called faces or facets). Obviously, a polyhedron is convex if and only if no
plane containing a face cuts any other faces of the polyhedron. A tetrahedron
(shown in Figure 1.6) is an example of a convex polyhedron.
Figure 1.7 shows an example of a polyhedron which is not convex since the plane
H, which contains the face f, cuts the face f2. Intuitively, a nonconvex polygon or
polyhedron can be thought of as having dents.
5
Polytope
The convex hull of a finite set of set of points in Rd is also called a convex
polytope. A polytope in Rd is called ^/dimensional.
Simplicial Polytope
If a (Apolytope has the property that every face has exactly d vertices, then it is
called a simplicial polytope. For example, in three dimensions, a simplicial
polytope has faces that are all triangles and in a 2polytope (a polygon), the faces
are line segments.
Interior Point
For any x G Md and <5> 0, the open ball B(x, 8) with center x and radius 8 is
defined by B(x, 8) = {y Rd: d(x, y) < 8}, where d(x, y) denotes the distance
between x and y. A point x is an interior point of the set S if there exists a 8 > 0
such that the open ball B(x, 8) <=S.
Extreme Point
A point x in a convex set S is an extreme point if there exists no nondegenerate line
segment in S that contains x in its relative interior.
Profile
The set of all extreme points of a convex set S is called the profile of S.
6
Boundary Point
A boundary point is defined as a point which is not an interior point. There are two
types of boundary points extreme and nonextreme. A nonextreme boundary
point lies on the line segment between two neighboring extreme points. Figure 1.8
shows the differences between boundary points, interior points, and extreme
points.
1.3 Predicate Left
ORourke [22] defined the predicate left which has many useful applications in
convex hull construction. Figure 1.9 shows an example of a set of points and an
edge connecting a pair of these points. The line segment, jfp2, is connected to
both p3 and p4. If we were standing on p^p2 facing towards p2, point p3 would be
on our left and pointy would be on our right.
7
Whether a given point p is to the left or right of a directed line segment l can be
determined by computing a determinant related to the area of the triangle formed
by / and p. This is done by using a determinant.
Signed Area (A) =
*1 y\
*2 y2
x3 y3
i
i
i
2
OiT2 y\*3 *lT3+ *2^3 *3T2)
(Equation 1.1)
It is the sign of the area that indicates whether a point is to the right or left of a
directed edge. If the points forming the triangle are in a counterclockwise
direction (in Figure 1.9, points p},p2, and p3 are counterclockwise) than the area of
the triangle will be positive. If the points forming the triangle are clockwise in
direction (e.g., points php2, and p4), then the area will be negative. In the case
where the points are collinear, the area will be zero. Thus, if a point is left of an
edge, the area will be positive, and if a point is right of an edge, the area will be
negative.
8
2 Hull Construction Algorithms in Two Dimensions
2.1 Naive Algorithm
ORourke [22] calls the following algorithm naive because it uses the most direct,
intuitive method for computing the convex hull of a set; however it is very
inefficient. It will be used as a method to compare the effectiveness of the other
algorithms that will be discussed later, as well as a means to introduce some
important concepts that will be used throughout this paper.
After examination, we can see that given any two extreme points p, and p2 that
form an edge of the hull, and the line segment p^i, where pt is any other point in S,
the angle between the two line segments is always smaller than or equal tot:. This
is illustrated in Figure 2.1 Further inspection of Figure 2.1 shows that when a hull
boundary is traversed in a counterclockwise direction, all points in S will be to the
left of each directed edge of the hull.
P4
V
Ps
Pi P2
Figure 2.1
Using this information, we can develop an algorithm which will determine for each
pair of points in S whether all other points in S are to the left of this pair. If so, this
pair would be an edge of the hull boundary.
9
The pseudocode for the naive algorithm is shown below:
function naive hull construction (S)
for i = 1 to n
{
for (j = 1 to n) and (j i)
{
allAreLeft = true
for (k = 1 to n) and (k *i) and (k j)
if not Left(pi, pjt pk)
then allAreLeft = false
if allAreLeft = false
then hullPts.Add (pit p^
}
}
return hullPts
Obviously with three nested for loops, this algorithm requires a run time of 0(n3).
For anything but a very small number of points this will be unacceptable. In the
next section, the gift wrapping algorithm is studied and we will show how the
naive algorithm can be improved.
2.2 Gift Wrapping Algorithm
In 1970 Chand and Kapur [5] devised this method to construct hulls in any
dimension. We will describe how it is used to construct hulls in three dimensions
in Section 3.2. For the two dimensional case, we will initially assume that our
points set S has no collinear points.
In the naive algorithm, if an extreme edge was found, it was added to the convex
hull and the program then went on to test the next combination. However, since
the extreme edges are linked, the end of one line segment is the beginning of
another.
Chand and Kapur used this observation to improve the naive algorithm. They
noted that the point that has the largest internal angle with respect to the last edge
would be the next vertex in the hull. In Figure 2.2 pfpx is an extreme edge of a
convex hull. The point pj forms the largest internal angle with pfpx and is the next
point on the hull.
10
Suppose we are given an edge known to be on the hull. We need to compute the
internal angle between this edge and all the points that have not yet been included
in the hull. The point that forms the largest internal angle will be the next one
included in the hull. Thus, only the points that have not been included in the hull
need be compared.
The final puzzle is how to choose the first edge of the hull. Figure 2.3 shows how
the initial edge can be formed from the lowest point p0 (a point obviously on the
hull) and a point a not in S that is to p0's left and at the same level. Point as
coordinates can be constructed as follows:
a.x=p0.xl a.y = p0.y
The line segment, ap0, is not included in the hull, and thereforep0 will not initially
be included in the hull points. This is convenient because the test for encountering
p0 the second time can be used to determine when the algorithm is finished.
Initially, we assumed that S has no collinear points; however, if there is a
possibility that a collinear case may exist, some extra computations must be done.
11
Figure 2.4 shows a case where a collinear condition exists. The internal angle is
equal for both points pj and p2. The distance from the last point of the edge should
be calculated for both points and the point with the largest distance will be the one
included in the hull. The extra computations will not always add extra time to the
process since the interior point in a collinear condition can be removed from
further consideration after it is discovered.
12
The giftwrapping algorithm can be outlined roughly as follows:
function 2D giftwrapping hull construction (S)
bottomPt = S.MinYQ
endPt = bottomPt
startPt.x = endPt.x 1
startPt.y = endPLy
done = false
while not done
{
loc = 0
theta = 0
for i = 1 ton
{
angle = InteriorAngle(startPt, endPt, p)
if {angle > theta) and (angle # 0)
then
{
loc = i
theta = angle
}
}
if leftmostPt = ploc
then done = true
startPt = endPt
endPt = ploc
hullPts. Add(phJ
S.Remove(phc)
}
return hullPts
The pseudocode shows that there are two loops an outer while loop and an inner
for loop. The outer loop runs until the algorithm is finished, or once for each edge
in the hull. The algorithm can be said to run in 0(dn) time, where d is the number
of edges in the hull. Thus if all the points in S are in the hull, the giftwrapping
method runs in 0(n2) time. However, if the number of edges is small compared to
the number of points, the run time of the algorithm improves. The giftwrapping
method is thus output sensitive.
13
2.3 QuickHull Algorithm
In 1977, Akl and Toussaint [1] developed the QuickHull algorithm for constructing
two dimensional convex hulls. The algorithm is called QuickHull because of its
similarity to the Quicksort algorithm. Again, we will initially assume that the set
of points S has no collinear points.
Akl and Toussaint noticed that if a quadrilateral was constructed from the highest,
lowest, leftmost, and rightmost points of a set of points S, that all the points in the
interior of this quadrilateral could be removed from consideration as extreme
points. Figure 2.5 shows an example of this idea. For a large number of points,
this step eliminates at least half of the points in S from further calculations [1],
The balance of the algorithm works by using a divide and conquer method to find
the remaining extreme points. Suppose that a line segment, j^p2, was given where
the end points, p, and p2, were known extreme points on the hull. Figure 2.6
shows such a case. If we study the points of S to the right of the line segment
P^P2, we can see that pointp3 has the longest perpendicular distance from the line
segment, and will be a point on the hull.
14
I t h t jj
P: ' Pi
Figure 2.6
The point with the largest perpendicular distance can be determined using the area
formula introduced in Equation 1.1. The triangle with the largest area will also be
the triangle that contains the point with the largest perpendicular distance. Figure
2.7 shows the polygonal chain after p3 has been added to the initial line segment.
If the points to the right of the line segments p^p3 were labeled A and the points to
the right of the line segment p^p2 were labeled B, then A and B and their respective
line segments could be treated in the same manner as S above. This would
continue recursively until there are no more points to the right of a line segment
and part of a convex hull will have been constructed.
15
Combining this technique with the construction of the quadrilateral described
initially, Akl and Toussaint developed the QuickHull algorithm. For each of the
four line segments in the quadrilateral, the recursive function QuickHull is called.
The pseudocode for QuickHull is as follows:
function QuickHull(pj, P2> S)
if n = 0
then
return newPoly(p,, p2)
p3 = PointFarthestFromEdge(p1, p2, S)
if p3 = null
then
return newPoly(pI, p2)
for i = 1 to n
{
if Area (ph p3, pj<0
then poly A. Add (pj
else if Area (p3, p2, pj < 0
then polyB. Add (pj
}
return Concatenale(QuickHull(p1, p3, polyA), QuickHull(p3, p2, polyB))
QuickHulls performance is an improvement over the Gift Wrapping algorithm.
Finding the four points of the quadrilateral requires 0(n) running time since all
points must be considered once. Like its namesake, Quicksort, QuickHull runs
best when the division into A and B is as even as possible. When the number of
points in A and B is equal (the best case), QuickHull requires 0(n log n) run time.
If A and B are as uneven as possible (the worst case) then QuickHull requires 0(n2)
operations.
Thus, the performance of QuickHull ranges between 0(n log n) and 0(n2).
Finding an algorithm which is 0(n log n) in the best and worst cases would be
desirable. The lower bound for constructing convex hulls will be discussed later in
Section 4.
16
2.4 Graham's Algorithm
R.L. Graham [13] developed this algorithm in 1972 and in 1978 S.G. Akl and G.T.
Toussaint [1] and K.R. Anderson [2] independently proposed some simplifications.
The algorithm we present here includes those simplifications.
Given a set of finite points S where no three points in S are collinear, Grahams
algorithm (sometimes called Grahams scan) starts with a known point on the hull
p0. It is convenient to use the lowest point in the set asp0(the point with the
minimum y coordinate) since this point certainly lies on the hull.
The remaining set of points in S are then sorted in terms of increasing vectoral
(polar) angle of the line segment, p^pi. Figure 2.8 shows an example of line
segments, p^px and p^p2, and their respective vectoral angles ds and d2.
The sorted points are then processed. The first and second points of the list are
added to the hull points. The hull will be correct for the points processed so far (po,
Pi, p2) This is a characteristic of this algorithm at any time the hull will be
correct given the points processed at that time.
As each point p, in the sorted list is considered, if pt is to the left of the last edge of
the hull, then it is added to the hull points and the next point is considered.
However, if it is to the right of the last edge of the hull, the algorithm must back
track and remove the last point added to the hull. The position of pf relative to the
last edge of the hull is then reevaluated.
Points will be removed from the end of the hull as long as pt is to the right of the
last edge of the hull. When p, is to the left of the last edge, it is added to the hull
17
and the next point in the list is considered. For a large n, backtracking can be quite
frequent.
Figure 2.9 shows an example where backtracking will be necessary. The pointp4
is being considered. Since p4 lies to the right of p^p3, p3 will be removed from the
hull in progress. However,p4 is still right of p^p2, sop2 will also be removed from
the hull as well. Since p4 is to the left of p^px, p4 will now be added to the current
hull and the next point will be considered. The algorithm is finished when all the
points in the list have been processed.
18
The pseudocode for Grahams algorithm follows:
function Grahams scan (S)
p0 = lowestPt
S = SortPointsAccordingToAngle(pg, S)
for i = 1 to n
{
if LefiOfLast Hull Edge (PJ
then hullPts.Add(pi)
else
{
while not LeftOfLastHullEdgefpi) do hullPts. Remove(p/IJu,lPlsi)
hullPts.Add(pi)
}
}
return hullpts
Sorting the points requires 0(n log n) operations, while the processing of the all
points requires a run time of 0(n) since each point is considered only once. Thus,
Grahams algorithm runs in 0(n log n) time.
2.5 Incremental Algorithm
It is difficult to know to whom to attribute this algorithm. According to Pach [23],
the incremental algorithm (or insertion hull) grew out of discussions among
researchers at a DIMACS workshop in 1989. Certainly, it is mentioned frequently
in computational geometry texts [17][20] [22] [23] [25].
The incremental algorithm finds the convex hull of a finite set of points S by
processing the points one and a time and inserting them, when appropriate, in to
the convex hull of the points already processed. Therefore, if S = {ph p2, p3,...,
p} where n is the number of points in S, andp, is the point now being processed,
then the current hull will be the correct hull for pointsph p2, p3, ..., Thus, as
in Grahams Algorithm, at any particular time, the hull is correct for the points that
have been processed.
The incremental algorithm is also an online algorithm. This means that because
no preprocessing of S needs to be done before the hull is constructed (unlike
Grahams algorithm, where the points are first sorted), this algorithm can be used
in realtime situations where the points must be processed as they are received.
19
Initially, the hull will be composed of the first three points of S'. As each point p{ is
then processed, if it is inside or on the boundary, then no changes need to be made
to the hull. If Pi is outside of the current hull, then it needs to be incorporated into
the hull.
This is done by first finding the support lines of the current hull through p,. A
supporting line of a convex hull is defined as the line which passes through at least
one vertex of the hull with the rest of the hull lying entirely to one side of the line.
Figure 2.10 shows two supporting lines of the convex hull through />,. For ease of
reference, the two support lines will be called the left support line and the right
support line as they would appear if we were standing on pt and facing the hull.
The supporting vertices of the left and right support lines (in Figure 2.10 these are
p2 and p5) can be found by using the boolean predicate left [22], Notice that if we
traverse the hull in a counterclockwise manner that pt is right of edge p^p2 and left
of edge P2P3 The point is also left of point p^p5 and right of point p^px. Points
p2 and p5 are the only points on the hull which have intersecting edges that have
different values of left with regards to p{. This procedure can be used to test for
tangency and will be used several times in this paper.
After the supporting vertices have been determined, any points which lie between
the supporting vertices on the near side of the p, (in Figure 2.10 this would be p}),
must be removed and pt inserted into the hull.
20
The pseudocode for the incremental algorithm follows:
function 2D incremental hull construction (S)
hullPts.Add (pi, p2, p3)
for i = 1 to n
{
isInHull = true
for j = 1 to jhullPts/ 1
{
if not Left (hullPtsjj], hullPts[j+l], pj
then isInHull = false
}
if IsInHull = false
then RecomputeHull (pj
)
return hullPts
To determine whether a point is inside the hull, each point in the hull must be
queried. This requires 0(n) operations for each point or 0(n2) for S. Finding the
supporting vertices is essentially a search and can be done in 0(n log n) time.
Thus, because of the necessity of determining if the point is inside the hull, this
algorithm runs in 0(n2) time.
This performance can be improved if S can be sorted before the hull is constructed.
If S is sorted in terms of increasing x coordinates, the process of determining if p,
lies inside the hull can be eliminated since p, will never lie inside the hull. Figure
2.11 shows a set of points that have been sorted with respect to their x coordinates.
Point p4 can be added to the hull without testing if it lies in the current hull. Since
its x coordinate is larger than all the points that make up the hull, there is no
possibility it could lie in the hull. This is true for the all points in the set.
21
Of course, sorting S can not be done if it is necessary that the incremental
algorithm be used as an online algorithm.
2.6 Divide and Conquer
The divideandconquer algorithm was developed by Preparate and Hong [24] in
1977. It has an elegant design and is easy to understand; it is also a complex
algorithm to implement. Divide and conquer can be also be used to construct
convex hulls in three dimensions. The three dimensional version will be discussed
in Section 3.1.
Divide and conquer starts with a finite set of points S with no collinear points and
no two points are on the same vertical line.
The basic idea of the divideandconquer algorithm is to recursively divide S into
smaller and smaller sets until there are only three (or less) points per set. If n = 3,
the hull is a triangle. These micro hulls are then merged together to form the
final convex hull. Merging A and B means the determination of the convex hull
conv(A, B) of A and B.
To divide S, it is first sorted with respect to the x coordinate of the points. S is then
recursively divided in half. Because no points have the same x coordinate, this
ensures that the generated point sets are separate.
After S has been divided into n sets, the hulls are merged. This is done by using
bridges. Figure 2.12 shows an example of two hulls to be merged and the upper
and lower bridges for the pair. Notice that the upper bridge is a support line
(introduced in Section 2.5) for both hulls. This is also the case for the lower
bridge.
22
The conventional way to find the upper bridge is to first find the rightmost point of
the left convex hull, lph (in Figure 2.12 this would be lp3) and the leftmost point of
the right convex hull, rpp (in Figure 2.12 this would be rps). Both points are then
tested for tangency (see Section 2.5). If the point on the left hull is not tangent (in
Figure 2.12, it is not), the index value, is increased by one. If the the point on
the right hull is not tangent (in Figure 2.12, again, it is not), then the index value, j,
is decreased by one.
Thus, the algorithm walks the points located between the two hulls until the
upper bridge is found. This same procedure is followed to locate the lower bridge.
After the bridges are found, the points that lie on the inside of the bridges are
removed from the hulls (in Figure 2.12 this would be points lp3, lp2, rp5, rp6), and
the hull are merged.
Divideandconquer algorithm is as follows:
Sort S by the x component of its points.
Recursively divide S into S, = fa, p[/in) and S2 = {pL/2njÂ¥ p) until /SJ <=
4. Construct conv(SJ and convfSJ.
Recursively implement merge algorithm on conv(SJ and conv(S2) to obtain
conv(S).
23
The performance of divide and conquer can be determined as follows. The initial
sorting of S by the x coordinate of its points requires 0(n log n) operations.
During the merging operation, finding the leftmost and rightmost point, requires
0(n) operations. Finding the upper and lower bridge can also be done is linear
time, since for each bridge, a point is only considered one (worst case). Thus
divide and conquer requires 0(n log n) operations.
24
3
Hull Construction Algorithms in Three Dimensions
Algorithms for constructing hulls in three dimensions are much more complex than
the two dimensional variety. As Day [6] points out, if the algorithm is not
implemented carefully, run time can be much more than that determined during the
analysis of the algorithm.
All algorithms in the section are discussed with the expectation that the hulls
constructed will be simplicial. For three dimensions this means that all faces on
the hull will have only three points. Thus the point set, S, must not have a coplanar
condition.
3.1 Gift Wrapping Algorithm
This algorithm was developed by Chand and Kapur in 1970 [5] and works in
arbitrary dimensions. The two dimensional method was discussed in Section 2.2.
In three dimensions, the gift wrapping algorithm was the primary method for
generating threedimensional hulls for several years.
In the two dimensional gift wrapping algorithm, the hull was constructed by
determining which new edge formed the smallest vectoral angle with the last
known edge of the hull. In three dimensions, a similar paradigm is followed.
Chand and Kapur observed that in three dimensions, an edge of a convex hull is
the intersection for precisely two faces. They were able to prove this in any
arbitrary dimension [5].
Using this observation, they realized that if a starting face f on the hull could be
found (how this is done will be discussed later), an edge e off could then be
chosen to work from. Each point in the set (not already contained in f) would be
tested. A point would be found which, when combined with e, constructed a face
that formed the largest angle with/ This face would lie on the hull and would be
the second face containing e. This is tantamount to rotating a plane about e until a
point is encountered.
25
Figure 3.1 shows how the algorithm works. Let Hbe the plane that contains the
known face/and e be an edge off Let H, be the plane which contains the new
face constructed from e and any arbitrary point pr The plane Ht which forms the
largest internal angle with //will be the plane that contains the next face of the
hull. An edge on the new face is chosen as the new e, Hj becomes H, and the
algorithm begins a new iteration.
To compute the angle between H and Hh the normals to each plane must be found.
Figure 3.2 shows two intersecting faces. The internal angle of these two faces is
the angle between the planes that contain them and can be computed by
determining the angle between the normals of these planes.
26
2 i
(0, 0.5,0.866) 60 (0,0.5,0.866)
(1, 0.5,0.866)# \ / (1,0.5,0.866)
\f.\ hi
\ rj y
f ^ This edge is
(1,0,0) along the x axis
Figure 3.2
The equation to determine the normal to a plane is given by:
h = (F,*F2) + (V2XV3) + (F3xFl) (Equation 3.1)
Where V,, V2, and V3 are vectors formed from any three points on the face and
where V, x V2 is the notation representing the cross product of vectors V, and V2.
Using Equation 3.1, and taking the points from the outside of each face in a
counterclockwise direction ((1,0,0), (1,0.5,0.866),(0,0.5,0.866)) for f and
((0,0.5,0.866), (1,0.5, 0.866), (1,0,0)) for f2 the normal are [0, 0.866, 0.5] and
[0, 0.866, 0.5] respectively.
To determine the angle between the computed normals, the following equation can
be used:
0 = 71
arccos
(Equation 3.2)
Where ny and n2 are the normals of the planes, is the dot product of nx and
2, and j is the magnitude of n,.
Using Equation 3.2, the angle between thef and f2 is 60.
27
Note that if the points were taken in a clockwise order, only the signs of the normals
would change; the computed angle would stay the same. However, it is important
that the points representing the faces be kept in a consistent order either
counterclockwise or clockwise and the normals also be computed using this
order. If this is not done, then the angle between the faces will be incorrect. Using
Figure 3.2 again, if the points off were taken in a counterclockwise direction from
the outside of the face as previously, but the points of f2 were taken in a clockwise
direction from the outside of the face ((1,0,0),(1,0.5,0.866),(0,0.5,0.866)) f2's
normal would now be [0,0.866,0.5]. Using Equation 3.2 the angle between these
normals is 120.
After a new face is determined, a next edge to work from must be found. Because
each edge has two intersecting faces, if only one face has been determined for an
edge, then that edge can be chosen as the next edge to use.
Figure 3.3 shows two intersecting faces f and f2. The points in f taken in a
counterclockwise order are a,b,c and the points in f2 in counterclockwise order are
a,c,d. Therefore, the points in the common edge are in reverse order for the two
face. Thus, when an edge is chosen to work from, the points in the edge must be
switched in order before being added to the new face being constructed.
The fact that each edge has only two intersecting faces can be used as a method to
determine when the algorithm is finished. This process is most easily implemented
if two structures are created to hold edges. For ease of reference these can be
labeled as usedOnce and usedTwice.
When a new face is found, each edge on that face is processed. If the edge has
never be used before, it is stored in usedOnce, where it can be used one more time.
28
If this is the second face found for the edge then it has already been stored in
usedOnce and it is removed from usedOnce and put in usedTwice where it will not
be used again. When there are no more edges in usedOnce the algorithm is done.
The last detail to be considered is how the initial face is found. In some ways this is
the most complex part of the algorithm. First find the point p0 with the smallest jc
coordinate. This point will certainly be on the hull and also lies in a plane H0,
which is a support plane of S. In three dimensions a support plane is equivalent to
a support line in two dimensions. It is defined as the plane which passes through a
point of the hull and the rest of the hull lies entirely to one side of the plane.
H0 contains all the points in space where the x coordinate equals p^x. The normal to
H0 is the vector n0 = (1,0,0). Figure 3.4 shows an example of a set of points S = {p0
> Pi> P2> P3} wherep0 is the point with the least x component and H0 the plane
which contains it. In this, S forms a tetrahedron. To find the second point of the
initial face (p0 is the first point), reflect any point of S which is not p0 on to H0. In
the example p1 was reflected onto H0. The resulting point pr will have coordinates
(p^x, Pl.y, Pl.z).
Pointspr andp0 can now form an edge about which to rotate a plane. In Figure 3.5
the points in S are used to construct a series of faces ) Each of these faces
is formed in a clockwise manner with pointsp0,pr, andpt (wherept an arbitrary
point not equal top0).
29
A clockwise orientation is used because n is directed toward the center of the
perspective hull rather than away from it, and therefore the normals of the faces
need to be directed toward the hull as well. The point that forms the face with the
largest internal angle with H0 will be the second point in the initial face.
After the second point is found, the normal of face (p0, pr, pt) becomes the new n.
The direction of n is then reversed by multiplying it by 1 and n is now orientated
away from the future hull. For ease of reference, using Figure 3.5, let pj be the
second point found of the initial face.
To find the third point, each point in S is used to construct a face (p,, p0, p,) in a
counterclockwise direction, where p, is any arbitrary point not equal to ps or p0. The
normal of each face is then computed using Equation 3.1. The point forming the
face that has a normal with the largest internal angle with n is the third point on the
initial face of the hull.
The performance of the gift wrapping algorithm can be determined by looking at the
pseudocode:
30
function 3D gift wrapping hull construction (S)
face = GenerateFirstFaceQ
hullPts. Add(face)
done = false
while not done do
{
edge = FindNextEdgeToWorkFrom(face)
if noEdgeFound
then done = true
else
{
face = GenerateNexlFace(edge)
hullPts. Add(face)
}
}
return hullPts
There are two main loops in the algorithm the while loop and the loop in the
function GenerateNextFace which iterates through all points in S. Thus the Gift
Wrapping algorithm requires 0(n2) operations. The gift wrapping algorithm was
the primary method to find three dimensional convex hull for many years until the
more efficient divide and conquer method (discussed next) was introduced in 1977.
3.2 Divide and Conquer
The divide and conquer algorithm presented by Preparata and Hong [24] in 1977
which was discussed in Section 2.6 carries over to three dimensions; the concept is
the same as in the two dimensional algorithm but much more complex. To
minimize this additional complexity, assume that each coordinate of a point is
unique. Thus, for two arbitrary pointsp, (xit yt, zj andp} (xJt yjt zf in S, we have
xi y, *yj, zt *Zj. Cases where this is not true will be discussed later.
The set S is first sorted by ^coordinate, and then recursively divided into an upper
subset and lower subset from which a pair of convex hulls are generated. These
hulls are then merged by a technique that is similar to the method used in the gift
wrapping algorithm discussed in Section 3.1. The division step continues until a
subset small enough to easily construct a convex hull is generated (four points can
easily construct a tetrahedron). As in the twodimensional case all the work is done
in the merge portion of the algorithm.
31
Figure 3.6 shows two hulls A and B to be merged. For convenience, these hull are
identical, but this would not normally be the case. The two hulls have been
reflected on to the xyplane creating hulls A' and B'. Restricting the coordinates of
each point to unique values prevents any two points from occupying the same
position on the xyplane.
A bridge can then be found for A' and B' using the same technique described in the
two dimensional case. This bridge is then used to find a support plane for both A
and B. A support plane is defined as the plane which passes through at least one
vertex of the hull while the rest of the hull lies entirely to one side of the plane. The
support plane tt of A and B is constructed to contain the bridge and to run parallel to
the zazis. Figure 3.7 shows the support plane of convex hulls A and B.
32
Figure 3.7
The support plane re is now folded over the edge until a point on either A or B is
encountered. This point pt is the third point of the initial face (ah b}, pt) of a
cylinder of triangular faces that will wrap around both hulls. This cylinder and the
faces that are still visible of A and B constitute the merged hull.
Figure 3.8 shows A and B and the resulting merged hull C. Points have been
labeled to aid in the following description of the merging process which is not
trivial.
As stated above, ti is rotated around the edge and the first point that is
encountered is the next point on the initial face of the band. This point will cause n
to rotate the smallest amount around Both A and B must be searched for a
point which causes the smallest rotation of tt. If at is the rotation of n around a^tx,
for any point on A, and pt is the rotation of n around a^t1, for any point on B, then
the minimum must be compared to the minimum /?, and the point with the
smallest rotation chosen.
Preparata and Shamos made three important observations that improve the
efficiency of finding the faces that make up the band. The first is that only the
neighbors of the current working edge need to be considered in the search. Thus,
looking at Figure 3.8, the neighbors of a, that need to be considered are a2, a3, and
a4 and the neighbors of bI that need to be considered are b2, b3, and b4. For A, the
point that produces the smallest rotation is a2; for B, that point is b2. Of these two
33
possibilites, a2 produces the smallest rotation and is the third point of the face (ah
bIt a2).
A
Figure 3.8
The second important observation is that once a point (and its respective edge) has
been determined not to be the next edge of the face on its respective hull, it can be
discarded from further consideration. This is because the path of the cylinder will
always be a simple circuit on each hull if no coplanar conditions exist. Note that the
existence of a coplanar condition does not indicate that the path will not be a simple
circuit, only that it is a possibility. Thus edges a^aA and a^a3 can be dismissed from
further consideration because a^a2 has been determined to be the next edge on the
band.
The final observation is that while it may seem as if the effort to find the point with
the smallest rotation is wasted on the hull that does not have the overall 'winner',
this is not true. Preparata and Hong determined that if the next point of the hull was
34
on A (the lefthandside hull), then the point with the smallest rotation on B for the
next iteration would be the point counterclockwise of the smallest rotation point on
this iteration around the last point included in the band.
Thus, for the next iteration the point on B which will produce the smallest rotation
of tt will be b4 which is counterclockwise from b2 around b,. A symmetrical rule
exits for the righthandside hull. If the next point on the hull was on B (the right
handside hull), then the point with the smallest rotation on A for the next iteration
would be the point clockwise of the smallest rotation point on this iteration around
the last point included in the band.
After the band of faces has be computed, the hidden face (faces that are no longer
visible) need to be removed. This can be done using what ORourke [22] calls the
shadow boundary. The shadow boundary is a set of edges defined as follows: If
the other hull were an illumination source, an edge which is the intersection of a
face which is illuminated and one in the dark is part of the shadow boundary. The
shadow boundaries are marked with a dark line in Figure 3.8. The shadow
boundary provides a boundary between the hidden faces and the faces that are still
visible after the merge. The faces that would be in the light using the illumination
example above are the faces that need to be removed. Its important to note that not
all hidden faces are guaranteed to be on shadow boundary; some may exist in its
interior as well.
The hidden faces can be found using a depth first search on hidden face along the
shadow boundary. The face is marked with a delete flag, and the search moves to
an adjacent face inside the shadow boundary. This procedure is continued until
there are no more adjacent faces inside the shadow bound to move to. The search
then backtracks until it finds an adjacent face to move to or until it backtracks to the
start.
The performance of the divideandconquer algorithm is not easy to compute.
Clearly, the sort requires 0(n log n) operations. During the merge operation, each
search finds an overall winner or it shows where a winner for that specific hull will
be for the next iteration, so each edge needs to be examined only once (in this case
an edge is directional p^p2 is considered a different edge than p^px). Thus,
finding a face can be accomplished in constant time. The number of faces in the
band is proportional to the number of edges in A and B since each face in the band
contains an edge of either A or B. So, constructing the entire band requires 0(n)
operations. Thus the divideandconquer algorithm requires 0(n log n) operations.
35
Initially, the coordinate values of the points in S were required to be unique. Since
this is not a common characteristic of a point set in reallife, what extra
complications arise when this condition is not met? Since S is initially sorted by
the ^coordinate of the each point, if points can exist with coincident xcoordinates,
this will need to be taken into consideration in the algorithm. Clearly, when the
hulls are projected on the xyplane, if the two extreme points have coincident xy
coordinates, complications will result. This condition is easy to test, but requires
extra calculations. ORourke [22] discovered that if S contains points that are
coplanar, the path of the cylinder around the hulls to be merged may not form a
simple cycle. The hidden faces can still be discarded using a depth first search, but
since there may be more than one set of shadow boundaries, extra calculations must
be used. This extra calculations can substantially decrease the running time of
0(n log n).
3.3 Incremental or BeneathBeyond Algorithm
The incremental or beneathbeyond algorithm is much easier to understand and
implement than the divideandconquer algorithm. Like the twodimensional case
described in Section 2.5, the three dimensional incremental algorithm finds the
convex hull of a finite set of points, S, by processing the points one at a time and
inserting them, when appropriate, into the convex hull of the points already
processed. Therefore, if S = {pjt for j = 1 ton} where n is the number of points in
S, and Pi is the point now being processed, then the current hull will be the correct
hull for pointsp,, p2, p3, ..., />,./ As in the two dimensional case, the three
dimensional incremental algorithm is an online algorithm.
Initially, the hull will be composed of the first four points of S (a tetrahedron). For
each point pt then processed, the position of the point with regard to the current hull
must be determined. This can be done by using the signed volume of a tetrahedron
(see Equation 3.3).
36
Signed Volume =
*1 *1 1
1 *2 ^2 *2 1
6 X3 y% Z3 1
*4 y 4 Z4 1
(Equation 3.3)
The volume is positive if the face (Pi, P2 > P3) forms a counterclockwise circuit
when viewed from the side away from p4, so that the normal of the face points
toward the outside. Thus, \ip4 is within a convex hull, all tetrahedrons formed from
the faces of the hull and p4 will be positive. If p4 lies outside the hull, there will be
at least one tetrahedron constructed from a face and p4 which will have a negative
volume. If a coplanar condition exists, then the volume will be equal to 0.
If the point pi is inside or on the boundary, then no changes need to be made to the
hull. If the Pi is outside of the current hull, then it needs to be incorporated into the
current hull. Figure 3.9 shows an example of a hull before and after the
incorporation of a point.
Figure 3.9
37
Figure 3.9 shows that new faces need to be constructed from the point to the hull
and the hidden faces then need to be removed. In the divide and conquer algorithm
(see Section 3.2), an example of an illumination source was used to help describe
the process. That example is also helpful here. If the point were an illumination
source, then a new face would be constructed from each edge of the shadow
boundary and the point. The faces that need to be removed would be the ones that
were illuminated by the point.
Although this indicates what must be done, it does not indicate how to do it. It's
important to note is that the new faces are tangent to the hull through the edge of the
shadow boundary. In the two dimensional case, the point of tangency on the hull
was where the point to be incorporated into the hull was left of the previous point
on the hull and right of the next point on the hull (or visa versa). A similar
condition exists here.
An edge of tangency (or part of the shadow boundary) is an edge where the point to
be incorporated forms a positive volume with one intersecting face and a negative
volume with the other. For example in Figure 3.9, face A forms a negative volume
with the new point, while face B forms a positive volume. Thus each edge can be
tested to find if it has two faces with varying volumes with regards to the new point.
This also indicates how the hidden faces can be found since all the hidden faces
form negative volumes with the new point.
To determine whether a point is inside the hull, each point in the hull must be
queried. Clearly this testing requires quadratic time as does finding the hidden
faces. Thus, the incremental algorithm requires a run time of 0(n2).
38
4
Lower Bounds
4.1 Two Dimensions
Intuitively, it would seem that since the vertices of the convex hull polygon appear
in order the construction of a planar convex hull is essentially a sorting routine.
This is stated in the following theorem.
Theorem 4.1
Sorting is transformable to finding a planar convex hull; therefore, finding the
ordered convex hull of n points in the plane will run in no better than 0(n log n)
time.
Proof: Preparata and Shamos [25] showed an elegant way to prove the
transformability. Given n real numbers xlt , x, all positive, construct the point
(Xj, x,2), and associate it with the number i. These points all lie on the parabola y =
x2. The convex hull of this set (shown in Figure 4.1) will consist of a list of the
points sorted by xt. One pass through this list will enable the x, values to be read off
in order.
1 i f y = x2 jjJF convex hull / ..
Figure 4.1
39
Thus, 0(n log n) is the best that can be done in constructing a convex hull in two
dimensions.
4.2 Three Dimensions
It would seem that computing the convex hull in three dimensions can be no faster
than in two dimensions. This is in fact true and is stated in the following theorem.
Theorem 4.2
If Cdi(n) is the time needed to construct convd.j(S) and Cd(n) is the time needed to
construct convd(S), then Cd.,(n) < Cd(n) for d > 3.
Proof: LetSdbe a set of n points in Rd where d> 3. Let Sd_, be the set of n (d1)
dimensional points that are constructed by eliminating the last component of each
point of Sd. If convfSJ is projected on to the coordinate system of M d'\ then
conv(Sd.j) will be produced. Thus conv(Sd_J can be found by finding conv(SJ.
Thus, 0(n log n) is the best that can be done in constructing a convex hull in three
dimensions [25],
40
5
Future Study
As Day [6] points out, implementation of a convex hull construction algorithm,
especially a three dimensional algorithm, is not a trivial exercise and obtaining the
lower bound run time can be very difficult. The implementation of the algorithms
for this paper where done in a straightforward manner in order to graphically
demonstrate the procedures. Implementing these algorithms in order to obtain
optimal run time would be interesting work to continue in the future.
41
Appendix A Code
A.1 thessapp.h
//
// Project Thesis
//
II Copyright i 1996. All Rights Reserved.
//
// SUBSYSTEM: Thesis Application
// FILE: thessapp.h
// AUTHOR: Melody C. Gillespie
//
// OVERVIEW
// Class definition for TThesisApp (TApplication).
//
II
#if !defined(thessapp_h) // Sentry, use file only if it's not already included.
# define thessapph
#include
#include "graphics.h"
#include "cube.h"
#include "quick.h"
#include "gw2d.h"
#include "gw3d.h"
#include "grahams.h"
#include "inc2d.h"
#include "thessapp.rh" // Definition of all resources,
class TThesisApp;
// TThesisFiame must be derived to override Paint for Preview and Print.
//.
class TThesisFrame : public TWindow
{
private:
public:
TThesisFrame(TWindow* parent = 0);
~TThesisFrame();
Graphics graphics;
42
int functionCalled;
TThesisApp thesisApp;
void Paint(TDC& dc, bool erase, TRect& clip);
//{ {TThesisAppRSPTBLBEGIN} }
protected:
void Cm2DGiftWrapping();
void CmQuickHull();
void CmGrahams();
void Cm2DIncremental();
void CmCubeQ;
void Cm3DGiftWrapping();
//{ {TThesisAppRSPTBLEND} }
DECLARE_RESPONSE_TABLE(TThesisFrame);
void DemoCube(TDC &dc);
void Demo2DGiftWrapping(TDC &dc);
void DemoQuickHull(TDC &dc);
void DemoGrahams(TDC &dc);
void Demo2DIncremental(TDC &dc);
void Demo3DGiftWrapping(TDC &dc);
};
//
// TThesisApp
class TThesisApp : public TApplication
{
private:
#define CMPAINT 0
#define CMCUBE 1
#define CM2DGIFTWRAPPING 2
#define CMQUICKHULL 3
#define CMGRAHAMS 4
#define CM2DINCREMENTAL 5
#define CM3DGIFTWRAPPING 6
TThesisFrame thesisFrame;
pubhc:
TThesisApp();
virtual ~TThesisApp();
T OpenSaveDialog: :TData FileData;
void OpenFile(const char* fileName = 0);
//{ {TThesisApp VIRTUAL_BEGIN}}
virtual void InitMainWindowQ;
43
//{ {TThesisAppVIRTUALEND} }
void CmHelpAbout();
};
#endif
A.2 thessapp.cpp
//
II Project Thesis
// Copyright i 1996. All Rights Reserved.
II
II SUBSYSTEM: Thesis Application
II FILE: thessapp.cpp
// AUTHOR: Melody C. Gillespie
II
// OVERVIEW
// Source file for implementation of TThesisApp (TApplication).
#include
#include
#include "thessapp.h"
#include "thssedtfh" // Definition of client class.
#include "thssabtd.h" // Definition of about dialog.
// Build a response table for all messages/commands handled
II by the application.
DEFINE RESPONSE TABLE l(TThesisFrame, TWindow)
//{ {TThesisAppRSPTBLBEGIN}}
EV_COMMAND(CM_2D_GIFTWRAPPING, Cm2DGiftWrapping),
EV_COMMAND(CM_QUICKHULL, CmQuickHull),
EV_COMMAND(CM_GRAHAMS, CmGrahams),
EV_COMMAND(CM_2D_INCREMENTAL, Cm2DIncremental),
EV_COMMAND(CM_CUBE, CmCube),
EV_COMMAND(CM_3D_GIFTWRAPPING, Cm3DGiftWrapping),
// { {TThesisAppRSP_TBL_END}}
END_RESPONSE_T ABLE;
// TThesisApp
TThesisApp::TThesisApp(): TApplication("Thesis")
{
// Common file file flags and filters for Open/Save As dialogs. Filename and
// directory are computed in member fimctions CmFileOpen, and CmFileSaveAs.
FileData.Flags = OFN_FILEMUSTEXIST  OFN HIDEREADONLY 
OFNO VERWRITEPROMPT;
FileData.SetFilter("All Files (*.*)* *");
FileData.DefExt = "txt";
}
ThesisApp Destructor
*/
TThesisApp: :~TThesis App()
45
{}
TThesisApp InitMainWindow
*/
void TThesisApp::InitMainWindow()
{
SetMainWindow(new TFrameWindow(0, "Thesis Demo", new TThesisFrame));
GetMainWindow()>AssignMenu(IDM_SDI);
TThesisFrame CmQuickHull
*/
void TThesisFrame: :CmQuickHull()
{
functionCalled = CMQUICKHULL;
Invalidate^,
return;
}
/*
TThesisFrame DemoQuickHull
void TThesisFrame: :DemoQuickHull(TDC& dc)
{
QuickConstructor2D quick(dc, this, graphics);
quick. ShowConstructHull();
functionCalled = CMPAINT;
return;
}
/*
TThesisFrame CmGrahams
void TThesisFrame: :CmGrahams()
{
functionCalled = CMGRAHAMS;
Invalidate^,
return;
}
/*
TThesisFrame DemoGrahams
*/
void TThesisFrame: :DemoGrahams(TDC& dc)
{
GrahamsConstructor grahams(dc, this, graphics);
grahams.ShowConstructHull();
functionCalled = CMPAINT;
return;
}
/*
TThesisFrame Cm2DIncremental
*1
void TThesisFrame: :Cm2DIncremental()
46
{
fiinctionCalled = CM2DINCREMENTAL;
Invalidate();
return;
}
/*
TThesisFrame Demo2DIncremental
*/
void TThesisFrame: :Demo2DIncrementaI(TDC& dc)
{
IncConstructor2D inc(dc, this, graphics);
inc.ShowConstructHull();
fiinctionCalled = CMPAINT;
return;
}
/*
TThesisFrame CmCube
*/
void TThesisFrame: :CmCube()
{
fiinctionCalled = CMCUBE;
Invalidate^
return;
}
TThesisFrame DemoCube
*/
void TThesisFrame: :DemoCube(TDC& dc)
{
Cube cube(dc, this, graphics);
cube. ShowConstnictHullQ;
fiinctionCalled = CMPAINT;
return;
/*
TThesisFrame Cm2DGiftWrapping
*/
void TThesisFrame: :Cm2DGiftWrapping()
{
fiinctionCalled = CM2DGIFTWRAPPING;
Invalidate();
return;
}
/*
TThesisFrame Demo2DGiftWrapping
*/
void TThesisFrame::Demo2DGiftWrapping(TDC& dc)
{
GWConstructor2D gw(dc, this, graphics);
gw. ShowConstructHull();
fimctionCalled = CMPAINT;
47
return;
}
/*
TThesisFrame Cm3DGiftWrapping
*/
void TThesisFrame: :Cm3DGiftWrapping()
{
ftmctionCalled = CM3DGIFTWRAPPING;
Invalidate();
return;
}
/*
TThesisFrame Demo3DGiftWrapping
*/
void TThesisFrame: :Demo3DGiflWrapping(TDC& dc)
{
GWConstructor3D gw(dc, this, graphics);
gw. ShowConstructHull();
ftmctionCalled = CMPAINT;
return;
}
/*
TThesisFrame Constructor
*/
TThesisFrame:: TThesisFrame(TWindow* parent)
{
#if defined(TRACING)
fout.open("tracing.dat", ios::app);
#endif
Init(parent, 0, 0);
ftmctionCalled = 0;
}
/*
TThesisFrame Destructor
TThesisFrame: :~TThesisFrame()
{
#if defined(TRACING)
fout.close();
#endif
}
/*
TThesisFrame Paint
*/
void TThesisFrame: :Paint(TDC& dc, bool erase, TRect& clip)
{
TRect clientRect = GetChentRect();
float hWin = 6;
graphics.HWin(clientRect.Width(), chentRect.Height(), hWin);
48
dc. SetMapMode(MM_LOENGLISH);
dc.SetViewportOrg(TPoint(clientRect.Width()/2, clientRect.Height()/2));
switch(fiinctionCalled)
{
case 0: //initial paint call
return;
case 1: //cube
DemoCube(dc);
return;
case 2: //2DGIFTWRAPPING
Demo2DGiftWrapping(dc);
return;
case 3: //QUICKHULL
DemoQuickHull(dc);
return;
case 4: //GRAHAMS
DemoGrahams(dc);
return;
case 5: //2DINCREMENTAL
Demo2DIncremental(dc);
return;
case 6: //3DGIFTWRAPPING
Demo3DGiftWrapping( dc);
return;
>
/* TThesisApp CmHelpAbout */
void TThesisApp: :CmHelpAbout() { // Show the modal dialog. TThesisAboutDlg(MainWindow).Execute(); } /* . .
OwlMain */
int OwlMain(int, char* 0) { TThesisApp app; return app.Run();
49
A.3 pointh
#if! defined(__POINTH)
#define___POINT_H
#include "global.h"
#include
class Point
{
public:
float x;
float y;
float z;
Point();
Point(float xx, float yy, float zz);
Point(float xx, float yy);
Point(const Point ©);
void Set(float xx, float yy, float zz);
void Se1(float xx, float yy);
friend int operator==(const Point &a, const Point &b);
friend int operator!=(const Point &a, const Point &b);
friend Point operator{const Point &a, const Point &b);
friend Point operator+(const Point &a, const Point &b);
Point& operator=(const Point ©);
float operator](int);
#if defined (TRACING)
void Print(char name); //tracing
#endif
#endif
50
A.4 pointcpp
#include "point.h'
/******************************************************************************
default constructor
******************************************************************************/
Point::
Point()
:*0),y(0), z(0)
0;
/I******************************************************************************
constructor
*****************:^***********************Â¥*********::**:
Point::
Point(float xx, float yy, float zz)
: x(xx), y(yy), z(zz)
{};
/************************************************:*:*****************************
constructor
******************************************************************************/
Point::
Point( float xx, float yy)
: x(xx), y(yy), z(0)
{};
I******************************************************************************
copy constructor
************s:******Je*:t::**::!t***:c:cil:**>c*!c!cj!!(t*:t:st::(:*:s:t::(::e**:t:!t::t::t::):!t::t:*:::(s:s!tsc:t:st:sc*:(!jc:c:t:sc*st:!c*:ty
Point::
Point(const Point ©)
: x(copy.x),y(copy.y),z(copy.z)
{};
I******************************************************************************
Set Point values
******************************************************************************/
void Point::
Set(float xx, float yy, float zz)
{
x = xx;
y = yy;
z = zz;
return;
};
/******************************************************************************
Set the points values
***:fc:f'*:'**:c*::*******::*************:c**********!c*********:f:*:c******::::**:t::tc:c*****:l**/
void Point::
Set(float xx, float yy)
{
x = xx;
y=yy;
51
return;
};
/******************************************************************************
operator==
lie***************************************************************************** j
int operator==(const Point &a, const Point &b)
{
if(a.x == b.x &&
a.y == b.y &&
a.z == b.z) return 1;
return 0;
>;
/******************************************************************************
operator!=
******************************************************************************/
int operator!=(const Point &a, const Point &b)
{
ii(a == b) return 0;
return 1;
Point operator^const Point &a, const Point &b)
{
Point pt(a.x b.x, a.y b.y, a.z b.z);
return pt;
};
Point operator+(const Point &a, const Point &b)
{
Point pt(a.x + b.x, a.y + b.y, a.z + b.z);
return pt;
};
/******************************************************************************
operator=
I******************************************************************************/
Point& Point::
operator^const Point ©)
{
if (this = ©) return *this;
x = copy.x;
y = copy.y;
z = copy.z;
return *this;
};
/******************************************** + *******!*:***;(;********************
operators!] returns the point's x coordinate if 0, y coordinate if 1,
and z coordinate if 2
******************************************************************************/
float Point::
operator[(int i)
{
52
return (i 0) ? x : (i == 1) ? y : z;
}
/******************************************************************************
print out point to file for tracing
******%*****************************************ic****:t::(c*:(c****:t;*:::t::c*******3fc**:':tc j
#if defined (TRACING)
void Point::
Print(char name)
{
fout name x y z endl;
};
#endif
53
A.5 poly.h
#if! defined (_POLY_H)
#define___POLYH
#include "global.h"
#include ''point.h"
#include "vector.h"
#include
#include "math2.h"
#include
class Poly
{
protected:
int nPts;
Point pts;
TColor color;
public:
PolyO;
Poly(const Poly ©);
~Poly();
Point& Poly: :operator[](int i);
void Color(COLORREF c){color.SetValue(c);};
void Color(TColor c) {color = c;};
void Color(int r, int g, int b);
int NPts()const;
Point* Pts();
TColor Color();
void Add(Point &pt);
void Add(int n, Point &newPt);
void Replace(int n, const Point &pt);
void Delete(int n);
void Delete(Point &pt);
void DeleteAll();
Vector PolyNorm(); // returns the normal to the poly
Point MaxX(); // returns the point with the largest X value
Point MinXQ; // returns the point with the smallest X value
Point MaxY(); // returns the point with the largest Y value
Point MinY(); // returns the point with the smallest Y value
Point MaxZ(); II returns the point with the largest Z value
Point MinZ(); // returns the point with the smallest Z value
int operator=(const Poly ©);
int operator!=(const Poly ©);
Poly& operator=( const Poly ©);
54
friend Poly Concatenate(Poly &pl, Poly &p2 );
bool AlreadyPresent(Pomt &pt);
Poly PolyXAxisRotation(float angle);
Poly PolyYAxisRotation(float angle);
Poly PolyZAxisRotation( float angle);
#ifdefined(TRACING)
void Print(char name); //for tracing
#endif
#endif
55
A.6 poly.cpp
#include "poly.h"
Default constructor
* * * * * * * * * * * ** ** * * * * * III * * * * * * * * * >e * * * * * * * * * * * j
Poly::
PolyO
: nPts(O), color(0)
{.
pts = NULL;
};
/***^**************************************************************************
Copy constructor
******************************************************************************/
Poly::
Poly( const Poly ©)
: nPts(copy.nPts),
color(copy.color)
{
pts = new Point[nPts];
for(int i = 0; i < nPts; i++)
{
pts[i] = copy.pts[i];
}
>;
/******************************************************************************
Destructor
tt***************************************************************************#/
Poly::
~Poly()
{
delete[] pts;
};
/******************************************************************************
The operatorQ member returns the poly's point at that given index
**********************t*******************************************************/
Point& Poly:: operator 0(int i)
{
return pts[i];
};
/******************************************************************************
Color(int r, int g, int b) sets color to RGB values
******************************************************************************/
void Poly::
Color(int r, int g, int b)
{
color.SetValue(RGB(r,g,b));
};
/sle*******************************************^********************************
56
return number of pts in the poly
a************************************************##**#**********************:**/
int Poly::
NPts()const
{
return nPts;
};
/******************************************************************************
return the array of pts
*********:^:^*>c***********!f^**********************************:c***************/
Point Poly::
PtsO
{
return pts;
y,
I******************************************************************************
return color of polygon
99c9eae4eateaeafe9teaeaeaej4eaeatB9c9teafe3tc9eaea^3cae34:aeaeaeaeaiea4cate3eafeaeateaeateaeaeae94ea4eaeaeafe34e9eaeaeaeaieaieaeafe9caCe^e3t:ateafeafeaeateaeacafeafeae9e9fc9edeaeaeaeafeaeaf: j
TColor Poly::
Color()
{
return color;
};
/******************************************************************************
overloaded = operator
4cae34e3ea(eae9e?ea4eaeae3(e9e4:3e?e3e3e4Â£9eac3eaieaeateateaea{c3^^e3te9fe%a(:afeae94eae9e)e^es4:9t:at:a^94e94eaic3c9fe3e9c3fe9c^a)e?eaca{eaf:ateaeacaeafcaic9e3te9eacae3fea)cac4:94e4c9fe j
int Poly::
operator=(const Poly ©)
{
if(nPts != copy.nPts) return 0;
for(int i = 0; i < nPts; i++)
{
if(pts[i] != copy.pts[i]) return 0;
}
if (color != copy.color) return 0;
return 1;
};
/******************************************************************************
overloaded != operator
******************************************************************************/
int Poly::
operator!=(const Poly ©)
{
ii(*this = copy) return 0;
return 1;
};
/* *****************************************************************************
overloaded = operator
******************************************************************************/
Poly& Poly::
operator=( const Poly ©)
57
{
if(*this = copy) return *this;
deleteQ pts;
nPts = copy.nPts;
pts = new Point[nPts];
for(int i = 0; i < nPts; i++)
{
pts[i] = copy.pts[i];
}
color = copy, color;
return *this;
};
/******************************************************************************
add a point to the end of the array
**:^********************************:^***:^******:^***************************/
void Poly::
Add(Point &newPt)
{
if(AlreadyPresent(newPt))retum;
Point newPts = new Point[nPts + 1];
for(int i = 0; i < nPts; i++)
{
newPts[i] = pts [i];
}
newPts [nPts] = newPt;
delete[ pts;
pts = new Point[nPts + 1];
for(int i = 0; i < nPts + 1; i++)
{
pts[i] = newPts[i];
}
delete[ newPts;
nPts++;
return;
>;
/******************************************************************************
add a point to the indicated position in the array
*********************************************:^*******************************/
void Poly::
Add(int n, Point &newPt)
{
if(AlreadyPresent(newPt))retum;
Point newPts = new Point[nPts + 1];
for(int i = 0; i < n; i++)
{
newPts[i] = pts[i];
}
newPts [n] = newPt;
for(int i = n+1; i < nPts+1; i++)
{
58
newPts[i] = pts[il];
}
deleteQ pts;
pts = new Point[nPts + 1];
for(int i = 0; i < nPts + 1; i++)
{
pts[i] = newPts [i];
}
deleteQ newPts;
nPts++;
return;
};
/******************************************************************************
replace a point int the poly at the given index value
s*******************************#********************************************/
void Poly::
Replace(int n, const Point &pt)
{
ii(n >= nPts) return;
ptsfn] = pt;
return;
};
/***********************************+******************************************
delete a point from the poly
******:^*:c*******************>f***********#************************************/
void Poly::
Delete(int n)
{
Point newPts = new Point[nPts 1];
for(int i = 0; i < n; i++)
{
newPts[i] = pts[i];
}
for(int i = n+1; i < nPts; i++)
{
newPts[il] = pts[i];
}
deleteQ pts;
pts = new Point[nPts 1];
for(int i = 0; i < nPts 1; i++)
{
pts[i] = newPts[i];
}
deleteQ newPts;
nPts;
return;
};
/******************************************************************************
delete the first point that matches the parameter from the poly
**********#****:c:c::*:M********3:***************Â¥***************************::****/
void Poly::
59
Delete(Point &pt)
{
Point newPts = new Point[nPts 1];
int j = 0;
bool deleted = false; // point hasn't been deleted yet
for(int i = 0; i < nPts; i++)
{
// if points are not the same, copy it to new array
if(pts[i] != pt  deleted)
{
newPts [j] = pts[i];
j++;
}
else
{
deleted = true; //makes sure only one point is deleted
}
}
delete[] pts;
pts = new PointfnPts 1];
for(int i = 0; i < nPts 1; i++)
{
pts[i] = newPts[i];
}
delete[] newPts;
nPts;
return;
};
/*****************#************************************************************
clear all pts in the poly
******************************:************************************************/
void Poly::
DeleteAll()
{
delete(] Pts
pts = NULL;
nPts = 0;
color = 0;
return;
};
/******************************************************************************
determines the normal of the poly
******************************************************************************/
Vector Poly::
PolyNorm()
{
Vector temp;
//if there are 2 or less points, return null vector
if(nPts <= 2) return temp;
60
Vector vl(pts[0]);
Vector v2(pts[l]);
Vector v3(pts[2]);
return Norm(vl,v2,v3);
}
/******************************************************************************
returns the point in the polygon with the max X value
******************************************************************************/
Point Poly::
MaxXQ
{
float maxX = pts[0].x;
Point maxXPt = pts[0];
for(int i = 0; i < nPts; i++)
{
if(pts[i].x > maxX)
{
maxXPt = pts[i];
maxX = pts[i].x;
}
}
return maxXPt;
/ft*****************************************************************************
returns the point in the polygon with the min X value
******************************************************************************y
Point Poly::
MinX()
{
float minX = pts[0].x;
Point minXPt = pts[0];
for(int i = 0; i < nPts; i++)
{
il(pts[i].x < minX)
{
minXPt = pts[i];
minX = pts[i].x;
}
}
return minXPt;
}
/I******************************************************************************
returns the point in the polygon with the max Y value
******************************************************************************/
Point Poly::
MaxY()
{
float maxY = pts[0].y;
Point maxYPt = pts[0];
for(int i = 0; i < nPts; i++)
{
61
ii(pts[i].y > maxY)
{
maxYPt = pts[i];
maxY = pts[i].y;
}
}
return maxYPt;
}
/*******^*********************************************************************
returns the point in the polygon with the min Y value
********************1^********************************************************/
Point Poly::
MinY()
{
float minY = pts[0].y;
Point minYPt = pts[0];
for(int i = 0; i < nPts; i++)
{
if(pts[i].y < minY)
{
minYPt = pts[i];
minY = pts[i].y;
}
}
return minYPt;
}
/******************************************************************************
returns the point with the highest z coordinate in the polygon
*********************:*********************************************************/
Point Poly::
MaxZ()
{
float maxZ = pts[0].z;
Point zPt = pts[0];
for(int i = 0; i < nPts; i++)
{
ifl[pts[i].z > maxZ)
{
zPt = pts[i];
maxZ = pts[i].z;
}
}
return zPt;
}
returns the point with the smallest z coordinate in the polygon
***************************************************************:!:**************/
Point Poly::
MinZ()
{
float minZ = pts[0].z;
62
Point zPt = pts[0];
for(int i = 0; i < nPts; i++)
{
il(pts[i].z < minZ)
{
zPt = pts[i];
minZ = pts[i].z;
}
}
return zPt;
}
/I*****************************************************************************
Adds the points from p2 to the end of p 1 (if they are not already present)
ft*******^********************************************************************/
Poly
Concatenate(Poly &pl, Poly &p2)
{
Poly newPoly(pl);
for(int i = 0; i < p2.NPts(); i++)
{
il( !newPoly.AlreadyPresent(p2[i]))
{
newPoly. Add(p2 [i]);
}
}
return newPoly;
};
/***+*****************************************************=(;**********);*>(<*******
is the point already in the array?
bool Poly::
AlreadyPresent(Point &pt)
{
bool alreadyPresent = false;
for(int i = 0; i < nPts; i++)
{
i^pts[i] = pt)
{
alreadyPresent = true;
}
}
return alreadyPresent;
};
/******************************************************************************
rotate the poly about the xaxis the given angle (in degrees)
*************^************************************************************,1:**/
Poly Poly::
PolyXAxisRotation(float angle)
{
Poly rotatedPoly;
63
Point pt;
for(int i = 0; i < nPts; i++)
{
pt = XAxisRotation(pts[i],angle);
rotatedPoly.Add(pt);
}
return rotatedPoly;
/*********:^*******************************************************************
rotate the poly about the yaxis the given angle (in degrees)
****************************************************************************** f
Poly Poly::
PolyYAxisRotation( float angle)
{
Poly rotatedPoly;
Point pt;
for(int i = 0; i < nPts; i++)
{
rotatedPoly .Add(YAxisRotation(pts[i],angle));
}
return rotatedPoly;
};
/******************************************************************************
rotate the poly about the zaxis the given angle (in degrees)
****************************************************************************** j
Poly Poly::
PolyZAxisRotation( float angle)
{
Poly rotatedPoly;
Point pt;
for(int i = 0; i < nPts; i++)
{
rotatedPoly.Add(ZAxisRotation(pts[i],angle));
}
return rotatedPoly;
};
y******************************************************************************
print information about poly for tracing
*******************************^**********************************************/
#if defined (TRACING)
void Poly::
Print(char name)
{
fout "For name ": nPts pts" endl;
for(int i = 0; i < nPts; i++)
{
fout for pts[" i "]:"
x[" i "] = pts[i].x
", y[" i "] = pts[i].y
, z[" i "] = pts[i].z endl;
}
64
fout color = color endl
return;
};
#endif
A.7 polytope.h
#if !defined(_POLYTOPEH)
#define _POLYTOPE_H
#include "poly.h"
#include
#include
class Polytope
{
protected:
int nPolys;
Poly polys;
public:
Polytope();
Polytope(int n, Poly p);
Polytope(const Polytope ©);
~Polytope();
int NPolys();
Poly PoIys();
void Add(const Poly &poly);
void Replace(int n, const Poly &poly);
void Delete(int n);
void DeleteAll();
Poly& operator[(int i);
int operator=(const Polytope ©);
int operator!={const Polytope ©);
Polytope& operator=(const Polytope ©);
#if defined(TRACING)
void Print(char name); //for tracing
#endif
#endif
66
A.8 polytope.cpp
#include ''polytope.h'
/*:*****************************************************************************
Default constructor
******************************************************************************/
Polytope::
Polytope()
: nPolys(0)
{
polys = NULL;
};
/******************************************************************************
Constructor
* * * * * * * 4c * a#e * * * * * * * * * * * * 4c * * ** * * * * * * * * * * * * * * j
Polytope::
Polytope(int n, Poly p)
: nPolys(n)
{
polys = new Poly [nPolys];
for(int i = 0; i < nPolys; i++)
{
polys[i] = pH;
}
};
/******************************************************************************
Copy constructor
*****************Â£Â£*************!''*********************************************/
Polytope::
Polytope(const Polytope ©)
: nPolys(copy.nPolys)
{
polys = new PolyfnPolys];
for(int i = 0; i < nPolys; i++)
{
polys[i] = copy.polys[i];
}
};
/******************************************************************************
Destructor
****************************************************************************** I
Polytope::
~Polytope()
{
deleteQ polys;
polys = NULL;
};
/******************************************************************************
return the polys
****************************************************************************** I
67
Poly Polytope::
Polys()
{
return polys;
};
/******************************************************************************
return the number of polys
int Polytope::
NPolys()
{
return nPolys;
};
/*******************************************************************:(:**********
overloaded = operator
******************************************************************************/
Polytope& Polytope::
operator^ const Polytope ©)
{
if(*this == copy) return *this;
delete]] polys;
polys = NULL;
nPolys = copy .nPolys;
polys = new Poly [nPolys];
for(int i = 0; i < nPolys; i++)
{
polysfi] = copy.polys[i];
}
return *this;
};
overloaded = operator
******************************************************************************/
int Polytope::
operator==(const Polytope ©)
{
iflnPolys != copy.nPolys) return 0;
for(int i = 0; i < nPolys; i++)
{
if(polys[i] != copy.polys[i]) return 0;
}
return 1;
};
/******************************************************************************
overloaded != operator
***********3^*****************************************************************/
int Polytope::
operator!=(const Polytope ©)
{
68
if(*this = copy) return 0;
return 1;
};
The operatorQ member returns the polytope's poly at that given index
fc*****************************************************************************/
Poly& Polytope: operator Q(int i)
{
return polys[i];
};
/******************************************************************************
add a poly to the polytope
n's default value is nPolys at end of the array
* * * * * * * * * * * # * * 4c lie * ** * * * * * * * * * * * * * * * * * * * * * * j
void Polytope::
Add(const Poly &newPoly)
{
Poly newPolys = new Poly[nPolys + 1];
for(int i = 0; i < nPolys; i++)
{
newPolys[i] = polys[i];
}
newPolys[nPolys] = newPoly;
delete[] polys;
polys = NULL;
polys = new Poly[nPolys + 1];
for(int i = 0; i < nPolys + 1; i++)
{
polysfi] = newPolys [i];
}
delete!] newPolys;
nPolys++;
return;
};
/I*****************************************************************************
replace a poly in the polytope at the index value given
*****************i^#*****************************:^**********************:':***%/
void Polytope::
Replace(int n, const Poly &newPoly)
{
polys[n] = newPoly;
return;
};
/******************************************************************************
delete a point from the poly
*****************************:(! I*:***********************************************/
void Polytope::
Delete(int n)
{
Poly newPolys = new Poly [nPolys 1];
69
for(int i = 0; i < n; i++) newPolys[i] = polys[i];
for(int i = n+1; i < nPolys; i++) newPolys[il] = polys[i];
delete[] polys;
polys = new Poly[nPolys 1];
for(int i = 0; i < nPolys 1; i++) polys[i] = newPolys[i];
delete[] newPolys;
nPolys;
return;
};
/***********************************+************************+*****************
clear all polys in the polytope
void Polytope::
DeleteAllQ
{
delete[] polys;
polys = NULL;
nPolys = 0;
return;
};
/******************************************************************************
printPolytope prints information about polytope for tracing
#if defined (TRACING)
void Polytope::
Print(char name)
{
fout "for name there are" nPolys polys endl;
for(int i = 0; i < nPolys; i++)
{
fout "for poly[" i "]:" endl;
polys[i].Print("poly in polytope");
}
};
#endif
70
A.9 edge.h
#if! defined(_EDGEH)
#define_EDGE_H
#include
#include "global.h"
#include "point.h"
#include
class Edge
{
public:
Point ptl;
Point pt2;
Edge();
Edge(Point pi, Point p2);
Edge(const Edge ©);
friend int operator=( const Edge &a, const Edge &b);
friend int operator!=(const Edge &a, const Edge &b);
Edge& operator=(const Edge ©);
void Set(Point &pl, Point &p2);
void Switch();
#if defined(TRACING)
void Print(char name); //tracing
#endif
};
/* use Borland container class for ease */
typedef TArrayAsVector EdgesArray;
#endif
71
A. 10 edge.cpp
#include "edge.h'
/*****************************************************************+
default constructor
******************************************************************/
Edge::
Edge()
: ptl(0,0,0), pt2(0,0,0)
{};
/******************************************************************
constructor
Edge::
Edge(Point pi, Point p2)
: ptl(pl), pt2(p2)
{};
/******************************************************************
copy constructor
************ ******************************************************/
Edge::
Edge(const Edge ©)
: ptl(copy.ptl),pt2(copy.pt2)
{};
/******************************************************************
overloaded = Note: edge is not directional
******************************************************************/
int operator=={const Edge &a, const Edge &b)
{
if(a.ptl = b.ptl &&
a.pt2 b.pt2) return 1;
if (a.ptl == b.pt2 &&
a.pt2 = b.ptl) return 1;
return 0;
};
/I*****************************************************************
overloaded !=
******************************************************************/
int operator!=(const Edge &a, const Edge &b)
{
il(a = b) return 0;
return 1;
}
/******************************************************************
overloaded =
******************************************************************/
Edge& Edge::
operator=(const Edge ©)
{
if (this = ©) return *this;
72
ptl = copy.ptl;
pt2 = copy.pt2;
return *this;
};
/*****************************************************************************
Sets the edge values
*****^****************1^*****************************************************/
void Edge::
Set(Point &pl, Point &p2)
{
ptl = pi;
pt2 = p2;
};
/*****************************************************************************
Switchs ptl and pt2
I*****************************************************************************/
void Edge::
Switch()
{
Point temp;
temp = ptl;
ptl = pt2;
pt2 = temp;
};
/****************************************************************::*
print out point to file for tracing
******************************************************************/
#if defined (TRACING)
void Edge::
Print(char name)
{
fout "For name ":" endl;
ptl.PrintC'ptl");
pt2.Print("pt2");
};
#endif
73
A.11 vector.h
#if !defined(_VECTOR_H)
#define_VECTOR_H
#include "global.h"
#include "point.h"
//#include
//#include "math2.h"
#include
class Vector
{
public:
float values[3];
Vector();
Vector(float a, float b, float c);
Vector(const Point &pt);
Vector(const Vector ©);
Vector& operator=(const Vector ©);
int operator=(const Vector ©);
int operator!=(const Vector ©);
void Set(float x, float y, float z);
void Set(Point &pt);
#if defined(TRACING)
void Print(char name); //tracing
#endif
};
#endif
74
A. 12 vector.cpp
#include "vector.h"
/*** *1^^* ******11^ i***************** ******** ******** ********* ************ *******
Constructor with no values
******************************************************************************/
Vector::
Vector()
{
for(int i = 0; i < 3; i++)
{
valuesp] = 0;
}
};
/******************************************************************************
Constructor given values
******************************************************************************/
Vector::
Vector(float a, float b, float c)
{
values [0] = a;
valuesfl] = b;
values [2] = c;
};
I******************************************************************************
Constructor from a point
******************************************************************************/
Vector::
Vector( const Point &pt)
{
values[0] = pt.x;
values[l] = pt.y;
values[2] = pt.z;
};
/******************************************************************************
Copy constructor
******************************************************************************/
Vector::
Vector( const Vector ©)
{
for(int i = 0; i < 3; i++)
{
valuesp] = copy.valuesp];
}
};
/******************************************************************************
operator=
******************************************************************************/
Vector& Vector::
operator=(const Vector ©)
75
{
if *this = copy) return *this;
for(int i = 0; i < 3; i++)
{
values[i] = copy.values[i];
>
return *this;
};
/******************************************************************************
operator==
I******************************************************************************/
int Vector::
operator=( const Vector ©)
{
for(mt i = 0; i < 3; i++)
{
ifvalues[i] != copy.values[i])retum 0;
}
return 1;
};
/******************************************************************************
operator!=
I**:***************************************************************************/
int Vector::
operator!=(const Vector ©)
{
if *this = copy) return 0;
return 1;
};
/******************************************************************************
Set sets the value of the vector using float values
************************************:^****************************************/
void Vector::
Sef float x, float y, float z)
{
values [0] = x;
values[l] = y;
values[2] = z;
};
/****^************************************************************************
Set sets the value of the vector using a point
*****%*********^*************************%************************************/
void Vector::
SefPoint &pt)
{
values[0] = pt.x;
valuesfl] = pty;
values[2] = pt.z;
};
print out vector to file for tracing
76
******************************************************************************/
#if defined (TRACING)
void Vector::
Print(char name)
{
fout "for name ":" values[0]
values[l] values[2] endl;
};
#endif
77
A.13 matrix.h
#if! defined(_MATRIX_H)
#define _MATRIX_H
#include "vector.h"
#include "point.h"
class Matrix
{
public:
float values[3][3];
Matrix();
Matrix(const Matrix ©);
Matrix& operator=(const Matrix ©);
int operator=(const Matrix ©);
int operator!=(const Matrix ©);
};
#endif
78
A.14 matrix.cpp
#include "matrixh1
******************************************************************************y
Matrix::
Matrix()
{
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
values[i][j] = 0;
}
}
};
/** ****************************************************************************
********************** ********************************************************/
Matrix::
Matrix( const Matrix ©)
{
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
values[i][j] = copy.values[i][j];
}
}
};
/******************************************************************************
***************************** + ******=(;**J(<******=(:**%***************^***^*****=t:**(/
Matrix& Matrix::
operator=(const Matrix ©)
{
if (this == ©) return *this;
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
values [i][j] = copy.values[i][j];
}
}
return *this;
};
/******************************************************************************
fc*****************************************************************************/
int Matrix::
operator==(const Matrix ©)
{
for(int i = 0; i < 3; i++)
79
{
for(int j = 0; j < 3; j++)
{
if(values[i][j]!= copy.values[i][j]) return 0;
}
}
return 1;
};
/******************************************************************************
******************************************************************************/
int Matrix::
operator!=(const Matrix ©)
{
i^*this = copy) return 0;
return 1;
};
80
A.15 graphics.h
#if! defined (_GRAPHICS_H)
# define _GRAPHICS_H
#include "global.h"
#include "poly.h"
#include "polytope.h"
#include "math.h
#include "math2.h"
#include "matrix.h"
#include "vector.h"
#include "colordef.h"
#include ''timer.h"
# include
#include
class Graphics
{
private:
float hWin, vWin; // thehorizonal and vertical logical window size
int hReal, vReal; // the horizonal and vertical real window size
public:
Graphics();
int HWin(int cx, int cy, float maxX); //sets hWin and returns vWin
void VWin(int cx, int cy, float maxY); //sets vWinow
float HWin(); //returns vWindow
float VWin(); //returns vWindow
int HReal(); //returns hReal
int VReal(); //returns vReal
Poly ConvertWorldToReal(Poly &wPts);
Point ConvertWorldToReal(const Point &wPt);
Poly ConvertRealToWorld(Poly &rPts);
Point ConvertRealToWorld(const Point &rPt);
TPoint ConvertRealToTPt(Poly &rPts);
TPoint ConvertRealToTPt(const Point &rPt);
void Print2DPoly(TDC &dc, Poly &wPts);
void Print3DPoly(TDC &dc, Poly &wPts, Point &C);
void PrintPolytope(TDC &dc, Polytope &wPolys, Point &C);
float ConvertToWorldLength(float rl);
Polytope TransformToXYPlane(Polytope &polys, Point &C);
Poly TransformToXYPlane(Poly &poly, Point &C);
Matrix Z( float x);
Matrix X( float x);
bool IsVisible(Poly &wPts, Point &c);
void Print(TDC &dc, const Point &Pt, const TColor &c);
void ConvertAndPrint(TDC &dc, const Point &Pt, const TColor &c);
81
void PrintBig(TDC &dc, const Point &Pt, const TColor &c);
void ConvertAndPrintBig(TDC &dc, const Point &Pt, const TColor &c);
void Print(TDC &dc, const Point &pl, const Point &p2, const TColor &c);
void ConvertAndPrint(TDC &dc, const Point &pl,
const Point &p2, const TColor &c);
void Print(TDC &dc, Poly &poly, TColor &c);
void ConvertAndPrint(TDC &dc, Poly &poly, TColor &c);
void PrintBig(TDC &dc, Poly &poly, TColor &c);
void ConvertAndPrintBig(TDC &dc, Poly &poly, TColor &c);
void PrintLines(TDC &dc, Poly &poly, TColor &c);
void ConvertAndPrintLines(TDC &dc, Poly &poly, TColor &c);
};
#endif
82
A. 16 graphics.cpp
#include "graphics.h'
/**********************************************************#*******************
default constructor
* * ate * * * * * * * 4c * ik * * * * * * * * * * * * * * * * * * * * * * * * * * j
Graphics: :Graphics()
{
hWin = 1;
vWin = 1;
}
/******************************************************************************
Set the maximum x and y values (given max x values)
***************************************3^*************************************/
int Graphics::
HWin(int xr, int yr, float maxX)
{
hReal = xr;
vReal = yr;
hWin = maxX;
vWin = (hWin / float(hReal)) float(vReal);
return vWin;
};
Set the maximum x and y values (given max y values)
*************************3^***************************************************/
void Graphics::
VWin(int xr, int yr, float maxY)
{
hReal = xr;
vReal = yr;
vWin = maxY;
hWin = (vWin / float(vReal)) float(hReal);
};
/******************************************************************************
Convert world values to real values
*3*3*3:*3:*3*3*3fc*3fc**3*3fc*****3**3fc**3t3***3t**3t*3E3ic*3t*3:3t:**3f:3:**3t3:3:3c3c3tr3f:*3t:***3:3:3:3:3i'*3f:**3:**3:3csc3t:3:33/
Poly Graphics::
ConvertWorldToReal(Poly &wPts)
{
int nPts = wPts.NPts();
Poly rPts(wPts);
foifint i = 0; i < nPts; i++)
{
rPts[i].x = (float(hReal)*wPts[i].x) / hWin;
rPts[i].y = (float(vReal)*wPts[i].y) / vWin;
}
return rPts;
83
/I*:****************************************************************************
Convert world point to real point
****3^*************************************^*********************************/
Point Graphics::
ConvertWorldToReal( const Point &wPt)
{
Point rPt;
rPt.x = (float(hReal)*wPt.x) / hWin;
rPt.y = ( float(vReal)*wPt.y) / vWin;
return rPt;
};
/******************************************************************************
Convert real values to world values
************^*************:^******3i^******************************************/
Poly Graphics::
ConvertRealToWorld(Poly &rPts)
{
int nPts = rPts.NPts();
Poly wPts(rPts);
for(int i = 0; i < nPts; i++)
{
wPts[i].x = (hWin / float(hReal)) rPts[i].x;
wPts[i].y = (vWin / float(vReal)) rPts[i].y;
}
return wPts;
};
/***********:M*****************************************************************
Convert real point to world point
******************************************************************************/
Point Graphics::
ConvertRealToWorld(const Point &rPt)
{
Point wPt;
wPt.x = (hWin / float(hReal)) rPt.x;
wPt.y = (vWin / float(vReal)) rPt.y;
return wPt;
};
/******************************************************************************
Convert xy POINT values from real for drawing to screen
**********:4^**>l^************************************************************:t:*/
TPoint Graphics::
ConvertRealToTPt(Poly &rPts)
{
int nPts = rPts.NPts();
TPoint TPts = new TPoint[nPts];
for(int i = 0; i < nPts; i++)
{
TPts[i].x = Round(rPts[i].x);
TPts[i].y = Round(rPts[i].y);
84
}
return TPts;
};
Convert real point to xy POINT drawing
******************************************************************************/
TPoint Graphics::
ConvertRealToTPt( const Point &rPt)
{
TPoint TPt;
TPt.x = Round(rPt.x);
TPt.y = Round(rPt.y);
return TPt;
};
/******************************************************************************
Convert world coord to TPoints for drawing
*************** ***************************************************************/
void Graphics::
Print2DPoly(TDC &dc, Poly &wPts)
{
TPoint* tPts = ConvertRealToTPt(ConvertWorldToReal(wPts));
//Printing procedure
TPen polyPen(TColor(MY_BLACK));
TBrush polyBrush(wPts.Color());
dc. SelectObject(polyPen);
dc. SelectObject(polyBrush);
dc.Polygon(tPts, wPts.NPts());
dc.RestoreObjects();
return;
}
Print a 3D poly to the screen
******************************************************************************/
void Graphics::
Print3DPoly(TDC &dc, Poly &wPts, Point &C)
{
Poly poly = TransformToXYPlane(wPts, C);
TPoint* tPts = ConvertRealToTPt(ConvertWorldToReal(poly));
// printing procedure
TPen polyPen(TColor(MY_BLACK));
TBrush polyBrush(poly.Color());
dc. SelectObject(polyPen);
dc. SelectObject(polyBrush);
dc.Polygon(tPts, poly.NPts());
dc.RestoreObjects();
return;
};
85
converts real length into world length
ft******************^**********************************************************/
float Graphics::
ConvertToWorldLength(float rl)
{
float wl;
wl = (hWin rl) / float(hReal);
return wl;
};
/******************************************************************************
returns hWin the logical width of the window
***************************************^**************************************/
float Graphics::
HWin()
{
return hWin;
>;
/******************************************************************************
return vWins the logical height of the client window
************1^****************************************************************/
float Graphics::
VWin()
{
return vWin;
};
/******************************************************************************
the width of the chent window in pixels
*************^***************************************************************/
int Graphics::
HReal()
{
return hReal;
};
/******************************************************************************
the height of the client window in pixels
***************************************************i^**********:^*************/
int Graphics::
VReal()
{
return vReal;
};
/******************************************************************************
TransformToXYPlane transforms the given polytope to the xyplane
******************************************************************************/
Polytope Graphics::
TransformToXYPlane(Polytope &polys, Point &C)
{
#if defined( TRACING)
fout "Entering TransformToXYPlane" endl;
#endif
86
Polytope transformedPolys;
float gamma;
float d;
float beta;
Matrix x, z, rlnverse, r;
if (C.x > 0) gamma = M_PI_2 + atan(C.y/C.x);
if (C.x = 0) gamma = M_PI;
if (C.x < 0) gamma = M_PI_2 + atan(C.y/C.x) + MJPI;
#if defined(TRACING)
fout "C.x = C.x C.y = C.y C.z = C.z endl
fout "gamma = gamma endl;
#endif
d = sqrt(Sqr(C.x) + Sqr(C.y) + Sqr(C.z));
beta = acos(C.z / d);
#if defined(TRACING)
fout "beta = beta endl;
#endif
x = X(beta);
z = Z(gamma);
rlnverse = x z;
r = rlnverse;
transformedPolys = polys;
for(int i = 0; i < polys.NPolys(); i++)
{
#if defined(TRACING)
polys[i].Print("polys[i] before transform");
#endif
foifint j = 0; j < polys[i].NPts(); j++)
{
Point pt = r polys[i][j];
transformedPolys[i][j] = pt;
}
#if defined(TRACING)
transformedPolys [i].Print("transfonnedPoly[i]");
#endif
}
#if defined(TRACING)
fout "Exiting TransformToXYPlane" endl;
#endif
87
return transformedPolys;
};
/*****************************************************************************
Print a polytope (in world coord) to the screen
s**********************************************:^*****************************/
void Graphics::
PrintPolytope(TDC &dc, Polytope &wPolys, Point &C)
{
Timer timer;
Polytope polys = TransformToXYPlane(wPolys, C);
for(int i = 0; i < wPolys.NPolys(); i++)
{
if( !IsVisible(wPolys[i],C))
{
#ifdefined(TRACING)
wPolys[i].Print("NOT visible1');
#endif
TPoint* tPts = ConvertRealToTPt(CbhvertWorldToReal(polys[i]));
// printing procedure
TPen polyPen(TColor(MY_BLACK));
TBrush polyBrush(polys[i].Color());
dc. SelectObject(polyPen);
dc. SelectObject(polyBrush);
dc.Polygon(tPts, polys[i].NPts());
dc.RestoreObjects();
}
}
for(int i = 0; i < wPolys.NPolys(); i++)
{
if(IsVisible(wPolys[i],C))
{
#if defined(TRACING)
wPolys [i]. Print( "visible");
#endif
TPoint* tPts = ConvertRealToTPt(ConvertWorldToReal(polys[i]));
// printing procedure
TPen polyPen(TColor(MY_BLACK));
TBrush polyBrush(polys[i].Color());
dc. SelectObject(polyPen);
dc. SelectObject(polyBrush);
dc.Polygon(tPts, polys[i].NPts());
dc.RestoreObjects();
}
}
88
}
return;
/* * * * *** * * i*i si * * * * * ** * * * * ** * ** * ********** * * *** ** ****** if *
TransformToXYPlane transforms the give poly to a poly on the xyplane
*****************************************************************************/
Poly Graphics::
TransformToXYPlane(Poly &poly, Point &C)
{
Poly poly3D = poly;
float gamma;
float d;
float beta;
Matrix x, z, rlnverse, r;
if(C.x > 0) gamma = M_PI_2 + atan(C.y/C.x);
if (C.x = 0) gamma = M_PI;
if(C.x < 0) gamma = M_PI_2 + atan(C.y/C.x) + M_PI;
d = sqrt(Sqr(C.x) + Sqr(C.y) + Sqr(C.z));
beta = acos(C.z / d);
x = X(beta);
z = Z(gamma);
rlnverse = x z;
r = rlnverse;
for(int i = 0; i < poly.NPts(); i++)
{
Point pt = r poly[i];
poly3D.Replace(i,pt);
}
return poly3D;
};
******************************************************************************/
Matrix Graphics::
Z( float f)
{
Matrix z;
z.values[0][0] = cos(f);
z.values[0][l] = sin(f);
z.values[l][0] = sin(f);
z.values[l][l] = cos(f);
z.values[2][2] = 1;
return z;
};
1**^^^^^^^^************************************************************
**c****************************************************************************/
Matrix Graphics::
89
X( float f)
{
Matrix x;
x.values[0][0] = 1;
x.values[l][l] = cos(f);
x.values[l][2] = sin(f);
x.values[2][l] = sin(f);
x.values[2][2] = cos(f);
return x;
};
/******************************************************************************
IsVisible returns true if the face (poly) is visible from the observation
point c
******************************************************************************/
bool Graphics::
IsVisible(Poly &wPts, Point &c)
{
#if defined(TRACING)
fout "Entering IsVisible" endl;
#endif
#if defined(TRACING)
wPts.Print("wPts poly is");
#endif
Vector norm = wPts.PolyNorm();
#if defined(TRACING)
fout "norm is: norm.values[0]
norm.values[l]
norm.values[2] endl;
#endif
Point pt = wPts.Pts()[0];
// create vector that translates C to the origin
Vector vl(c.xpt.x, c.ypt.y, c.zpt.z);
float angle = AngleBetweenVectors(norm, vl);
#if defined(TRACING)
fout "angle is (1.57 is pi/2):" angle endl;
#endif
#ifdefined(TRACING)
fout "Exiting IsVisible" endl;
#endif
if( angle >= M_PI_2) return false;
return true;
90
/******************************************************************************
Print a point (in real coord) to the screen using 9 pixels
so it is more visable
******************************************************************************/
void Graphics::
Print(TDC &dc, const Point &Pt, const TColor &c)
{
dc.SetPixel(Pt.xl, Pt.y+1, c);
dc.SetPixel(Pt.x, Pt.y+1, c);
dc.SetPixel(Pt.x+l, Pt.y+1, c);
dc.SetPixel(Pt.xl, Pt.y, c);
dc.SetPixel(Pt.x, Pt.y, c);
dc.SetPixel(Pt.x+l, Pt.y, c);
dc.SetPixel(Pt.x1, Pt.y1, c);
dc.SetPixel(Pt.x, R.y1, c);
dc.SetPixel(Pt.x+l, Pt.y1, c);
return;
}
/******************************************************************************
Print a point (in real coord) to the screen using 25 pixels
so it is more visable
******************************************************************************/
void Graphics::
PrintBig(TDC &dc, const Point &Pt, const TColor &c)
{
dc.SetPixel(Pt.x2, Pt.y+2, c);
dc.SetPixel(Pt.xl, Pt.y+2, c);
dc.SetPixel(Pt.x, Pt.y+2, c);
dc.SetPixel(Pt.x+1, Pt.y+2, c);
dc.SetPixel(Pt.x+2, Pt.y+2, c);
dc.SetPixel(Pt.x2, Pt.y+1, c);
dc.SetPixel(Pt.xl, Pt.y+1, c);
dc.SetPixel(Pt.x, Pt.y+1, c);
dc.SetPixel(Pt.x+l, Pt.y+1, c);
dc.SetPixel(Pt.x+2, Pt.y+1, c);
dc.SetPixel(Pt.x2, Pt.y, c);
dc.SetPixel(Pt.xl, Pt.y, c);
dc.SetPixel(Pt.x, Pt.y, c);
dc.SetPixel(Pt.x+l, Pt.y, c);
dc.SetPixel(Pt.x+2, Pt.y, c);
dc.SetPixeI(Pt.x2, Pt.y1, c);
dc.SetPixel(Pt.xl, Pt.y1, c);
dc.SetPixel(Pt.x, Pt.y1, c);
dc.SetPixel(Pt.x+1, R.y1, c);
dc.SetPixel(R.x+2, R.y1, c);
dc.SetPixel(R.x2, R.y2, c);
dc.SetPixel(R.xl, R.y2, c);
dc.SetPixel(R.x, R.y2, c);
dc.SetPixel(R.x+l, R.y2, c);
dc.SetPixel(R.x+2, R.y2, c);
return;
91
}
/******************************************************************************
Convert a point to real coord and prints it to the screen 
using 9 pixels
********!**********************************************************************/
void Graphics::
ConvertAndPrint(TDC &dc, const Point &p, const TColor &c)
{
Print(dc, ConvertWorldToReal(p), c);
return;
}
/******************************************************************************
Convert a point to real coord and prints it to the screen 
using 25 pixels so it is more visable
******************************************************************************/
void Graphics::
ConvertAndPrintBig(TDC &dc, const Point &p, const TColor &c)
{
PrintBig(dc, ConvertWorldToReal(p), c);
return;
}
/I******************************************************************************
Print the points of a polygon (in real coord) to the screen 
using 9 pixels so they are more visable
******************************************************************************/
void Graphics::
Print(TDC &dc, Poly &poly, TColor &c)
{
for(int i = 0; i < poly.NPts(); i++)
{
Print(dc, poly.Pts()[i],c);
}
return;
};
/****^^***********************************************************************
Print the points of a polygon (in real coord) to the screen 
using 9 pixels so they are more visable
****^********^*:^*************************^***********************************/
void Graphics::
PrintBig(TDC &dc, Poly &poly, TColor &c)
{
for(int i = 0; i < poly.NPts(); i++)
{
PrintBig(dc, poly.Pts()[i],c);
}
return;
};
/******************************************************************************
Convert the points of a polygon to real coord and print them
to the screen using 9 pixels so they are more visable
92
void Graphics::
ConvertAndPrint(TDC &dc, Poly &poly, TColor &c)
{
for(int i = 0; i < poly.NPts(); i++)
{
ConvertAndPrint(dc, poly.Pts()[i],c);
}
return;
};
/******************************************************************************
Convert the points of a polygon to real coord and print them
to the screen using 25 pixels so they are more visable
******************************************************************************/
void Graphics::
ConvertAndPrintBig(TDC &dc, Poly &poly, TColor &c)
{
for(int i = 0; i < poly.NPts(); i++)
{
ConvertAndPrintBig(dc, poly.Pts()[i],c);
}
return;
};
/******************************************************************************
Prints a line (in real coord) to the screen
***********************************>^***:M>l^>l^********************************/
void Graphics::
Print(TDC &dc, const Point &pl, const Point &p2, const TColor &c)
{
TPen linePen(c,2,PS_INSIDEFRAME);
dc.SelectObject(linePen);
dc.MoveT o(p 1 ,x,p 1 .y);
dc.LineTo(p2.x, p2.y);
dc.RestoreObjects();
rdum;
}
/******************************************************************************
Converts and prints a line (in real coord) to the screen
t********^*******************^**********************************************/
void Graphics::
ConvertAndPrint(TDC &dc, const Point &pl,
const Point &p2, const TColor &c)
{
Point startPt(ConvertWorldToReal(pl));
Point endPt(ConvertWorldToReal(p2));
Print(dc,startPt,endPt,c);
retrnn;
}
/*s*****************************************************************************
Prints the lines (in real coord) of a poly to the screen
void Graphics::
93
PrintLines(TDC &dc, Poly &poly, TColor &c)
{
TPen linePen(c,2,PS_INSIDEFRAME);
dc.SelectObject(linePen);
dc.MoveT o(poly .Pts()[0] .x, poly .Pts()[0] .y);
for(int i = 1; i < poly.NPts(); i++)
{
dc.LineT o(poly.Pts()[i].x, poly.Pts()[i] .y);
}
dc.LineTo(poly.Pts()[0].x, poly.Pts()[0].y);
dc.RestoreObjects();
return;
}
/******************************************************************************
Converts and prints the lines (in real coord) of a poly to the screen
ll^*******^********************************************************************/
void Graphics::
ConvertAndPrintLines(TDC &dc, Poly &poly, TColor &c)
{
Poly realPoly(ConvertWorldToReal(poly));
PrintLines(dc, realPoly, c);
}
94
A. 17 math2.h
#if! defined(_MATH2_H)
# define_MATH2H
#include
#include "global.h"
#include "point.h"
#include "vector.h"
#include "matrix.h"
#include
#include
#include
#define Ln 10 2.30258509299405E+000
# define OneOverLnlO 0.43429448190325E+000
#define Pi 3.1415927
#define PiOverl80 #define PiUnderl80 1.74532925199433E002 5.72957795130823E+001
/* CONTENTS
General Functions Description
Abs(x) Returns the absolute value of x.
Round(x) Returns the nearest integer to x.
Trunc(x) Returns the integer part of x.
Frac(x) Returns the fractional part of x.
Sqr(x) Returns x x.
Sqrt(x) Returns xAl/2.
Radians(x) Returns x in radians.
Degrees(x) Returns x in degrees.
CosD(x) Returns the cos of x when x is in degrees.
SinD(y) Returns the sin of x when x is in degrees.
Power(x,i) Raises x to the power of i.
Log(x) Compute the base 10 logarithm of x.
95
