tailieunhanh - Ebook Computational geometry - Algorithms and applications (3rd edition): Part 2

(BQ) Part 2 book "Computational geometry - Algorithms and applications" has contents: Delaunay triangulations, more geometric data structures, convex hulls, binary space partitions, robot motion planning, quadtrees, visibility graphs, simplex range searching. | 9 Delaunay Triangulations Height Interpolation When we talked about maps of a piece of the earth’s surface in previous chapters, we implicitly assumed there is no relief. This may be reasonable for a country like the Netherlands, but it is a bad assumption for Switzerland. In this chapter we set out to remedy this situation. We can model a piece of the earth’s surface as a terrain. A terrain is a 2-dimensional surface in 3-dimensional space with a special property: every vertical line intersects it in a point, if it intersects it at all. In other words, it is the graph of a function f : A ⊂ R2 → R that assigns a height f (p) to every point p in the domain, A, of the terrain. (The earth is round, so on a global scale terrains defined in this manner are not a good model of the earth. But on a more local scale terrains provide a fairly good model.) A terrain can be visualized with a perspective drawing like the one in Figure , or with contour lines—lines of equal height—like on a topographic map. Figure A perspective view of a terrain Of course, we don’t know the height of every point on earth; we only know it where we’ve measured it. This means that when we talk about some terrain, we only know the value of the function f at a finite set P ⊂ A of sample points. From the height of the sample points we somehow have to approximate the height at the other points in the domain. A naive approach assigns to every p ∈ A the height of the nearest sample point. However, this gives a discrete terrain, which 191 Chapter 9 DELAUNAY TRIANGULATIONS doesn’t look very natural. Therefore our approach for approximating a terrain is as follows. We first determine a triangulation of P: a planar subdivision whose bounded faces are triangles and whose vertices are the points of P. (We assume that the sample points are such that we can make the triangles cover the domain of the terrain.) We then lift each sample point to its correct height, thereby mapping every triangle in the

• Toán học
• Computational geometry
• Delaunay triangulations
• More geometric data structures
• Convex hulls
• Binary space partitions
• Robot motion planning
• Line segment intersection
• Polygon triangulation
• Linear programming
• Orthogonal range searching
• Point location
• Voronoi diagrams
• Computational Chemistry
• Mathematical Sciences
• Distance Geometry
• Chemical Reactions
• Numerical Methods
• Prototypical Problem
• Chromatography A
• Computational fluid dynamics
• Extra column volume effect
• Protein chromatography
• Threedimensional system
• Mathematics as science
• Applied mathematics
• Computational mathematics
• Fields of mathematics
• Foundations and philosophy
• Magnetohydrodynamic
• Parabolic Equations
• Axisymmetric Geometry
• Magnetic Flux Coordinates
• Plasma Equilibrium
• Elliptic Equations
• Difference Equations
• The melt
• Types of inclusions in AI alloys
• Reactions of the melt with its environment
• Surface film formation
• Entrainment
• Entrainment defects
• cơ khí chế tạo máy
• tài liệu cơ khí
• sổ tay cơ khí
• hướng dẫn cơ khí
• ôn thi cơ khí