(计算机图形学)lecture1What is CG.ppt

* * * * * * * * * * * * * * WUSTL applet * * * * * * * * * * * * * * Computational Geometry Lecture 1: Introduction Joe Mitchell Background Geometry: vectors, dot/cross product AMS301: Counting, graphs, recursion Permutations, combinations Planar graphs, DFS, Euler F(n) = 2F(n/2) + Cn Solve: F(n)=O(n log n) Algorithms: read/parse a C program, big-Oh notation (O(n), O(n log n), O(n2), O(n log n)) What is CG? The algorithmic and mathematical study of efficient methods to solve geometric problems Example 1 Point-in-polygon test: Is point q inside simple polygon P? P n-gon q Na?ve: O(n) per test CG: O(log n) Example 2 Segment intersection: Given n line segments in the plane, determine: Does some pair intersect? (DETECT) Compute all points of intersection (REPORT) Na?ve: O(n2) CG: O(n log n) detect, O(k+n log n) report Applet: Example 4 Post office problem: Voronoi diagrams /Info/People/chew/Delaunay.html Example 5 Triangulation of polygons http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html Ear-Clipping Triangulation Ear-clipping applet Example 6 Sensor placement, “guarding” The Problem Determine a small set of guards to see all of a given polygon P Vertex Guarding a Simple Polygon Vertex guarding applet Example 7 Shortest path for a mobile robot Application: Weather Avoidance * * Basic Optimal Paths Visibility Graph BEST: Output-sensitive alg: O(|E|+n log n) Local optimality: taut string Na?ve algorithm: O(n3) Better algorithms: O(n2 log n) sweep O(n2 ) duality Visibility Graphs Shows also the topological sweep of an arrangement, animated. Example: Shortest Path in Simple Polygon Triangulate P Determine the “sleeve” defined by the triangles in a path in the dual tree, from start to goal Other Applets Rectilinear watchman, online applet STIP online applet : search for a target in polygon * Shortest Path Map Decomposition of the free space Shortest Paths go through same vertices Construct in time: O(n log n); size O(n) C