没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
Introduction to Computing with Geometry Notes
Dr. C.-K. Shene
July 1, 1998
Chapter 1
Course Overview
1.1 Why Is Computing with Geometry Impor-
tant?
Up to now, perhaps most of your programs use only integers, except for
those you wrote in a numerical methods course which use floating point numbers
exclusively. Before you enter computer graphics, you perhaps would not know
how to use these numbers (integers and/or reals) for representing geometric ob-
jects. But, why is handling geometric objects so important? At a first
glance, the answer to this question is simple: it is because this world is full of
geometric objects. For example, your car, desk, table, chair, CD-ROM and its
player, and TV are all geometric objects. If this is not good enough, just take
a look at the field of computer science to see how many branches do need the
skill of handling geometric objects.
• Computer Graphics
This does not require any further explanation. All characters in Toy Story
are geometric objects. Computer-Aided Design Engineers use computer-
aided design systems for designing something (e.g., a piston engine or a
model aircraft). These are, of course, geometric objects.
• Computational Geometry
What is Computational Geometry? Is it identical to Computing with
Geometry? Literally, they should be the same. However, computational
geometers study the algorithmic aspect and complexity measure of geo-
metric problems involving simple geometric objects such as points, lines,
line segments, polylines and polygons, circles and circular arcs, spheres
and polyhedra. Some classical problems are (1) computing the convex
hull of a set of points, (2) determining the intersection points of a set of
line segments, and (3) triangulating a simple polygon. While the focus is
1
theoretical and algorithmic, the field of computational geometry does deal
with geometric objects.
• Visualization
Richard Hamming once said
The purpose of computing is insight, not numbers
Visualization explores data and information graphically - as a means of
gaining understanding and insight into the data (R. A. Earnshaw and
N. Wiseman, An Introductory Guide to Scientific Visualization, Springer-
Verlag, 1992). As long as graphics is involved, geometric objects appear.
A good example of visualization is medical scanning. An object is scanned
producing many contours on parallel planes. How do we reconstruct the
scanned object, including its interior, from the given contours?
• Computer Vision
In computer vision and image processing, features are extracted from im-
ages taken by cameras and used for other purposes. For example, two
cameras are mounted on a robot for taken stereo pictures. Features are
extracted and sent to algorithms that control the motion of the robot so
that it will not collide with the surrounding environment. What are fea-
tures? Points, line segments and circles are all features in an image. In
many cases, the extracted features are used to reconstructed the scene.
1.2 The Theme of this Course
Going from a geometric concept/problem to a working program usually
takes several steps as follows:
Geometry → Algebra → Algorithm → Program
Since computers do not understand geometry, one must convert a geometric
problem to an algebraic one that uses numbers. Then, one can design algorithms
to manipulate these numbers and finally, programs are developed based on these
algorithms. However, each step is a difficult and challenging task.
Geometry → Algebra
When we think about a geometric object, even a simple one such as a
point or a line, we normally have its shape in mind. But, to have computers to
process a geometric object, we have to find a representation for that object so
that it can be described in a form that can be manipulated by computers. For
example, a point in three-dimensional space is represented with three numbers
like (2.5, 0.0, -4.0), and a line in the xy-coordinate plane has an equation like
3x − 5.3y + 3 = 0.
A geometric object’s representation is usually not unique. A circle can be rep-
resented by an implicit equation:
x
2
+ y
2
= 1 (1.1)
2
or in a parametric form using trigonometric functions:
x = cos(t) (1.2)
y = sin(t) (1.3)
where t is in the range of 0 and 360 degree.
Some geometric objects such as polyhedra many even require complex data
structures to represent all of its details. Therefore, finding a good and appro-
priate representation (for a particular application) is usually a very challenging
task. We shall cover some of these representations in this course. Some are
mathematical (for curves and surfaces) and some are combinatorial (for polyhe-
dra). Whatever representation is chosen, it must be easy to use and manipulate,
and support all desired operations efficiently and accurately.
In addition to a representation for a particular type of geometric objects,
one must convert geometric operations to algebraic forms, too. Take a look at
the following question. Given a sphere of radius r, what is the locus of this
sphere if its center moves on a curve? We know that the locus, usually referred
to as a sweep, looks like a tube; but, it is not so easy to know what exactly
this tube looks like. If the curve is a line, the locus is a cylinder. The difficult
part is that the curve is not a line and/or that the radius of the given sphere
can change. Therefore, we have an easily described geometric operation whose
algebraic counterpart is somewhat complicated.
Algebra → Algorithm
After finding representations for geometric objects and algebraic interpre-
tations for your geometric operations, the next step is to find algorithms for
manipulating the representations and equations. Is it easy? Sometimes it is.
For example, if the problem is ”determine if two lines on the xy-coordinate plane
intersect and if they are, find the intersection point,” it can be solved easily. Let
the lines be
Ax + By + C = 0 (1.4)
Ux + V y + W = 0 (1.5)
Then, if they are parallel to each other (i.e., A ∗ V = B ∗ U), there is no in-
tersection point; otherwise, the intersection point can be found by solving the
above simultaneous linear equations of two variables.
Unfortunately, other practical problems are not so easy. First, the repre-
sentation of a geometric object such as a piston engine of the Boeing 777 is huge
and the number of equations, usually non-linear ones with many variables, is
also huge. Manipulating these representations and equations is not an easy job.
However, we have at least the following choices:
• Symbolic Computation
A symbolic system delivers symbolic answers. For example, if you ask a
symbolic system to solve a quadratic equation Ax
2
+Bx+C = 0, it would
3
give you the following equations of roots:
root1 = (−B + SQRT (B
2
− 4 ∗ A ∗C))/(2 ∗ A) (1.6)
root2 = (−B − SQRT (B
2
− 4 ∗ A ∗C))/(2 ∗ A) (1.7)
Therefore, the answers are algebraic rather than numerical. There are
good symbolic systems available (e.g., Mathematica and Maple). Com-
putation cost is usually very high (e.g. very slow). On the other hand,
symbolic computation is able to give you a closed-form solution, a form
that can be written in one or more formulae.
• Numerical Computation
Numerical solutions give you a bunch of numbers rather than a closed-form
solution. Numerical computation has been a popular way of finding solu-
tions for geometric problem. For example, in calculus you perhaps have
learned Newton’s method for solving non-linear equation. The solution is
merely a number. Numerical computation is fast; but, since computer-
s cannot represent real numbers exactly, extreme care must be taken to
avoid loss of significant digits and other related problems. For example,
if the initial guess for Newton’s method is incorrect, you may not be able
to find a root. As a suggestion, please try to solve the following equation
using Newton’s method:
f(x) = x
1/(2n+1)
(1.8)
where n is a positive integer. This equation has a root at zero. But,
Newton’s method will not converge to zero at all. Try it yourself.
• Approximation
Since symbolic computation is time consuming and numerical computa-
tion sometime does not deliver the result, let us take a compromise. Let
us simplify our solution by only asking for a good approximation. For ex-
ample, it is provably true that in general a polynomial with degree higher
than four does not have any closed-form solution. Numerical methods
(e.g. Newton’s method) can only give us an approximation of the roots of
a higher degree polynomial. So, the question is ”how good is good.” This
is obviously problem dependent. We shall return to this question later on.
The above does not enumerate all possibilities. One can combine several ways
together to solve a single problem. For example, one can use symbolic to solve
some parts of the problem and use a combination of numerical computation
and approximation to do the remaining.Recently, some authors suggested the
so-called geometric methods whose fundamental merit involves characterizing
the results using geometry reasoning and using the characterization for calcu-
lating the result. This method usually work fine with simple problems and may
require a large number of case-by-case analysis. However, if geometric method
works, it usually delivers the solution fast and is more accurate and robust than
4
剩余276页未读,继续阅读
资源评论
shuizaitianny
- 粉丝: 2
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功