Unformatted text preview:

Monday, February 18, 2002 (Ming C. Lin)Lecture 11: Review on Computational Geometry& Collision Detection for Convex Polytopes3. TetrahedralizationExtreme Points and Convex HullSuppose we have a database of people with their heights and weights.Voronoi DiagramsGeneralized Voronoi DiagramGeneralized Voronoi Diagram: the extension of the Voronoi diagram to higher dimensional features (such as edges and facets, instead of points); i.e. the set of points closest to a feature, e.g. that of a polyhedron.FACTS:In general, the generalized Voronoi diagram has quadratic surface boundaries in it.If the polyhedron is convex, then its generalized Voronoi diagram has planar boundaries.Delaunay TriangulationsTetrahedralizationConvex DecompositionLinear ProgrammingSimple Clipping:Cohen-Sutherland Line-Clipping AlgorithmCyrus-Beck Techniques (1978):A Parametric Line-Clipping AlgorithmD = P1 - P0;Monday, February 18, 2002 (Ming C. Lin)Lecture 11: Review on Computational Geometry & Collision Detection for Convex Polytopes COMPUTATIONAL GEOMETRY(Refer to O'Rourke's and “Dutch” textbook )1. Extreme Points & Convex Hulls Providing a bounding volume2. Voronoi Diagram&Delaunay Triangle For tracking closest points3. Tetrahedralization  Use in CD method & convex decomp4. Convex Decomposition For CD btw non-convex polyhedra5. Linear Programming Check if a pt lies w/in a convex polytopeExtreme Points and Convex HullSuppose we have a database of people with their heights and weights.person weights (lbs) heights (feet)A 150 7.0B 100 5.0C 160 5.5D 200 6.6E 250 4.8Which person(s) is(are) "extreme" in theirmeasurements?1. Certainly A, who is the tallest2. B, who is the lightest 3. E, who is the heaviest & shortest.4. D "extreme"? Both heavy and tall. D maximizes sum of height & weight? No. But, D maximizes the following: (weight in lbs) + 100 *(height in feet)CONCLUSION: A data point of (weight, height) "extreme", iff there are some magic numbers a and b so that within the group ofdata points, it maximizes the function:a * (weight) + b * (height)According to this definition, C is the onlyperson in our example that is not "extreme".heightweight456750 100 150 200 250BEDAC Since the set of all points (x,y) that satisfyax + by = c forms a straight line, whichtranslates when c changes. A point in a finitepoint set S in the plane is an extreme pointof S if one can draw a straight line throughthe point and have all the other points of Slie strictly on one side of the line. Definition: Let S be a set of n points in R2.A point p = (px, py) in S is an extreme pointfor S iff there exists a, b in R such that forall q = (qx, qy) in S with q != p we havea px+ b py > a qx+ b qyGeometric interpretation: There is a linewith the normal vector (a,b) through p sothat all other points of S lies strictly on oneside of this line. Intuitively, p is the mostextreme point of S in the direction of thevector v = (a,b).Definition: The convex hull of a set S is theintersection of all convex sets that containsS. It should be easy to see that the convexhull of S is the smallest convex polygon thatcontains S and that the extreme points of Sare just the corners of that polygon. Solvingthe convex hull problem implicitly solves theextreme point problem.Constructing Convex Hulls- Graham’s Scan- Marriage before Conquest(similar to Divide-and-Conquer)- Gift-Wrapping- IncrementalAnd, many others ……Lower bound: O(n log H), where n is theinput size (No. of points in the given set) andH is the No. of the extreme points.Voronoi DiagramsProximity Problem: Given a set S of npoints in R2 , for each point pi in S what isthe set of points (x, y) in the plane that arecloser to pi than any other point in S ?Answer: Voronoi diagram of the set S Intuition: To partition the plane intoregions, each of these is the set of points thatare closer to a point pi in S than any other.The partition is based on the set of closestpoints, e.g. bisectors that have 2 or 3 closestpoints.Given two points pi and pj, the set of pointsclosest to pi than pj is just the half-planeHi(pi ,pj) containing pi . Hi(pi ,pj) is definedby the perpendicular bisector to the linesegment of pipj . The set of points closer topi than any other point is formed by theintersection of at most n-1half-planes, wheren is the number of points in the set S . Thisset of points, Vi(S) is called the "Voronoipolygon" associated with pi. Formally, Vi(S)can be defined as the following: Vi(S)={x in R2| d(x, pi) - d(x, q); all q in S}The collection of n Voronoi polygons giventhe n points in the set S is the "Voronoidiagram", Vor(S), of the point set S. Everypoint (x, y) in the plane lies within a Voronoipolygon. If a point (x,y) in Vi(S), then pi isthe point nearest to the point (x,y). Thesimilar idea applies to the same problem in3D or higher dimensional space. Generalized Voronoi DiagramGeneralized Voronoi Diagram: theextension of the Voronoi diagram to higherdimensional features (such as edges andfacets, instead of points); i.e. the set ofpoints closest to a feature, e.g. that of apolyhedron. FACTS:- In general, the generalized Voronoidiagram has quadratic surface boundariesin it. - If the polyhedron is convex, then itsgeneralized Voronoi diagram has planarboundaries.Voronoi RegionsDefinition: A "Voronoi region"associated with a feature is a set ofpoints that are closer to that featurethan any other. FACTS:- The Voronoi regions form a partition ofspace outside of the polyhedronaccording to the closest feature. - The collection of Voronoi regions ofeach polyhedron is the generalizedVoronoi diagram of the polyhedron.- The generalized Voronoi diagram of aconvex polyhedron has linear size andconsists of polyhedral regions. And, allVoronoi regions are convex.Delaunay TriangulationsThe Delaunay triangulation is thetopological dual (graph theoretical dual orcombinatorial theoretic dual) of the Voronoidiagram. Duality: A point in the plane has twoparameters: (x,y). A (non-vertical) line inthe plane also has two parameters: its slopeand y-intercept.


View Full Document

UNC-Chapel Hill COMP 259 - LECTURE NOTES

Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?