SPATIAL & MVG OBJ DB
SPATIAL & MVG OBJ DB CIS 4930
Popular in Course
Popular in Comm Sciences and Disorders
This 21 page Class Notes was uploaded by Aliyah Boyer on Friday September 18, 2015. The Class Notes belongs to CIS 4930 at University of Florida taught by Staff in Fall. Since its upload, it has received 15 views. For similar materials see /class/207033/cis-4930-university-of-florida in Comm Sciences and Disorders at University of Florida.
Reviews for SPATIAL & MVG OBJ DB
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/18/15
CS 373 NonLecture E Convex Hulls Fall 2002 E Convex Hulls E1 De nitions We are given a set P of n points in the plane We want to compute something called the convex hull of P lntuitively the convex hull is what you get by driving a nail into the plane at each point and then wrapping a piece of string around the nails More formally the convex hull is the smallest convex polygon containing the points 0 polygon A region of the plane bounded by a cycle of line segments called edges joined end to end in a cycle Points where two successive edges meet are called vertices o convex For any two points p q inside the polygon the line segment 17 is completely inside the polygon o smallest Any convex proper subset of the convex hull excludes at least one point in P This implies that every vertex of the convex hull is a point in P We can also de ne the convex hull as the largest convex polygon whose vertices are all points in P or the unique convex polygon that contains P and whose vertices are all points in P Notice that P might have interior points that are not vertices of the convex hull A set of points and its convex hull Convex hull vertices are black interior points are white Just to make things concrete we will represent the points in P by their Cartesian coordinates in two arrays X1n and Y1 We will represent the convex hull as a circular linked list of vertices in counterclockwise order if the ith point is a vertex of the convex hull nexti is index of the next vertex counterclockwise and predi is the index of the next vertex clockwise otherwise nexti pred 0 It doesn t matter which vertex we choose as the head of the list The decision to list vertices counterclockwise instead of clockwise is arbitrary To simplify the presentation of the convex hull algorithms 1 will assume that the points are in general position meaning in this context that no three points lie on a common line This is just like assuming that no two elements are equal when we talk about sorting algorithms If we wanted to really implement these algorithms we would have to handle colinear triples correctly or at least consistently This is fairly easy but de nitely not trivial E2 Simple Cases Computing the convex hull of a single point is trivial we just return that point Computing the convex hull of two points is also trivial For three points we have two different possibilities 7 either the points are listed in the array in clockwise order or counterclockwise order Suppose our three points are a l7 c7 d and 67 f given in that order and for the moment let s also suppose that the rst point is furthest to the CS 373 NonLecture E Convex Hulls Fall 2002 left so a lt c and a lt f Then the three points are in counterclockwise order if and only if the line a bc d is less than the slope of the line a Z7e7 f d 7 I f 7 b 7lt c7a 67a counterclockwise ltgt Since both denominators are positive we can rewrite this inequality as follows counterclockwise ltgt f 7 bc 7 a gt d 7 be 7 a This nal inequality is correct even if 2717 is not the leftmost point If the inequality is reversed then the points are in clockwise order If the three points are colinear remember we re assuming that never happens then the two expressions are equal e 0 ad Three points in counterclockwise order 417 Another way of thinking about this counterclockwise test is that we re computing the cross pmduct of the two vectors c7 d 7 2717 and e f 7 a b which is de ned as a 2 x 2 determinant counterclockwise ltgt C T a d T 6 gt 0 e 7 a f 7 b We can also write it as a 3 x 3 determinant l a b counterclockwise ltgt 1 c d gt 0 l e f All three boxed expressions are algebraically identical This counterclockwise test plays exactly the same role in convex hull algorithms as comparisons play in sorting algorithms Computing the convex hull of of three points is analogous to sorting two numbers either they re in the correct order or in the opposite order E3 Jarvis s Algorithm Wrapping Perhaps the simplest algorithm for computing convex hulls simply simulates the process of wrapping a piece of string around the points This algorithm is usually called Jarvis s march but it is also referred to as the ngt wmppmg algorithm Jarvis s march starts by computing the leftmost point 6 225 the point whose ac coordinate is smallest since we know that the left most point must be a convex hull vertex Finding 6 clearly takes linear time CS 373 NonLecture E Convex Hulls Fall 2002 The execution of Jarvis s March Then the algorithm does a series of pivoting steps to nd each successive convex hull vertex starting with Z and continuing until we reach 6 again The vertex immediately following a point p is the point that appears to be furthest to the right to someone standing at p and looking at the other points In other words if q is the vertex following p and r is any other input point then the triple p 1quot is in counter clockwise order We can nd each successive vertex in linear time by performing a series of 0n counter clockwise tests JARVISMARCHX1 n Y1 n 5 H1 for i H 2 to n if lt XV 5 Hi I 6 repeat q H p 1 Make sure I7 739 qgtgt for i H 2 to n if CCWpiq q z newtlpl H q prevlql H17 17 Eq until p Z Since the algorithm spends 0n time for each convex hull vertex the worst case running time is 0n2 However this nai39ve analysis hides the fact that if the convex hull has very few vertices Jarvis s march is extremely fast A better way to write the running time is 0nh where h is the number of convex hull vertices In the worst case h n and we get our old 0n2 time bound but in the best case h 3 and the algorithm only needs 0n time Computational geometers call this an outputsensitive algorithm the smaller the output the faster the algorithm E4 Divide and Conquer Splitting The behavior of Jarvis s marsh is very much like selection sort repeatedly nd the item that goes in the next slot In fact most convex hull algorithms resemble some sorting algorithm For example the following convex hull algorithm resembles quicksort We start by choosing a pivot point p Partitions the input points into two sets L and R containing the points to the left 3 CS 373 NonLecture E Convex Hulls Fall 2002 of p including p itself and the points to the right of p by comparing ac coordinates Recursively compute the convex hulls of L and R Finally merge the two convex hulls into the nal output The merge step requires a little explanation We start by connecting the two hulls with a line segment between the rightmost point of the hull of L with the leftmost point of the hull of R Call these points p and q respectively Yes it s the same p Actually let s add two copies of the segment 1771 and call them bridges Since p and q can see each other this creates a sort of dumbbell shaped polygon which is convex except possibly at the endpoints off the bridges Merging the left and right subhulls We now expand this dumbbell into the correct convex hull as follows As long as there is a clockwise turn at either endpoint of either bridge we remove that point from the circular sequence of vertices and connect its two neighbors As soon as the turns at both endpoints of both bridges are counter clockwise we can stop At that point the bridges lie on the upper and lower common tangent lines of the two subhulls These are the two lines that touch both subhulls such that both subhulls lie below the upper common tangent line and above the lower common tangent line Merging the two subhulls takes 0n time in the worst case Thus the running time is given by the recurrence Tn 0n Tk Tn 7 k just like quicksort where k the number of points in R Just like quicksort if we use a naive deterministic algorithm to choose the pivot point p the worst case running time of this algorithm is 0n2 If we choose the pivot point randomly the expected running time is 0nlog There are inputs where this algorithm is clearly wasteful at least clearly to us If we re really unlucky we ll spend a long time putting together the subhulls only to throw almost everything away during the merge step Thus this divide and conquer algorithm is not output sensitive 1 A set of points that shouldn t be divided and conquered E5 Grahamis Algorithm Scanning Our third convex hull algorithm called Graham 5 scan rst explicitly sorts the points in On log n and then applies a linear time scanning algorithm to nish building the hull 4 CS 373 NonLecture E Convex Hulls Fall 2002 We start Graham s scan by nding the leftmost point 6 just as in Jarvis s march Then we sort the points in counterclockwise order around 6 We can do this in 0nlog n time with any comparison based sorting algorithm quicksort mergesort heapsort etc To compare two points p and q we check whether the triple 617 q is oriented clockwise or counterclockwise Once the points are sorted we connected them in counterclockwise order starting and ending at Z The result is a simple polygon with n vertices A simple polygon formed in the sorting phase of Graham s scan To change this polygon into the convex hull we apply the following three penny algorithm We have three pennies which will sit on three consecutive vertices p 177quot of the polygon initially these are 6 and the two vertices after 6 We now apply the following two rules over and over until a penny is moved forward onto 6 o If p 177quot are in counterclockwise order move the back penny forward to the successor of r o If p 177quot are in clockwise order remove q from the polygon add the edge pr and move the middle penny backward to the predecessor of p The three penny scanning phase of Graham s scan Whenever a penny moves forward it moves onto a vertex that hasn t seen a penny before except the last time so the rst rule is applied n 7 2 times Whenever a penny moves backwards a vertex is removed from the polygon so the second rule is applied exactly n 7 h times where h is as usual the number of convex hull vertices Since each counterclockwise test takes constant time the scanning phase takes 0n time altogether E6 Chan7s Algorithm Shattering The last algorithm 1711 describe is an output sensitive algorithm that is never slower than either Jarvis s march or Graham s scan The running time of this algorithm which was discovered by 5 CS 373 NonLecture E Convex Hulls Fall 2002 Timothy Chan in 1993 is 0nlog h Chan s algorithm is a combination of divideand conquer and gift wrapping First suppose a little birdie tells us the value of h we ll worry about how to implement the little birdie in a moment Chan s algorithm starts by shattering the input points into nh arbitrary1 subsets each of size h and computing the convex hull of each subset using say Graham s scan This much of the algorithm requires 0nh hlog h On log h time D I I I E E7 0 O I gt I 39 o Q n a 39 Shattering the points and computing subhulls in Onlogh time Once we have the nh subhulls we follow the general outline of Jarvis s march wrapping a string around the nh subhulls Starting with p t where t is the leftmost input point we successively nd the convex hull vertex the follows p and counterclockwise order until we return back to 6 again The vertex that follows p is the point that appears to be furthest to the right to someone standing at p This means that the successor of p must lie on a right tangent line between p and one of the subhullsia line from p through a vertex of the subhull such that the subhull lies completely on the right side of the line from p s point of View We can nd the right tangent line between p and any subhull in 0log h time using a variant of binary search This is a practice problem in the homework Since there are nh subhulls nding the successor ofp takes 0nh log h time altogether Since there are h convex hull edges and we nd each edge in Onhlog h time the overall running time of the algorithm is 0nlogh i j j Wrapping the subhulls in Onlog 71 time 7 5 5 Unfortunately this algorithm only takes 0nlog h time if a little birdie has told us the value of h in advance So how do we implement the little birdie Chan s trick is to guess the correct value of h let s denote the guess by M Then we shatter the points into nh subsets of size if compute their subhulls and then nd the rst if edges of the global hull If h lt if this algorithm computes the complete convex hull in On log if time Otherwise the hull doesn t wrap all the way back around to 6 so we know our guess h is too small Chan s algorithm starts with the optimistic guess h 3 If we nish an iteration of the algorithm and nd that if is too small we square if and try again In the nal iteration if lt hz so the last iteration takes 0nlog if 0nlog hz 0nlog h time The total running time of Chan s algorithm is given by the sum Onlog3nlog32nlog34nlog32k 1In the gures in order to keep things as Clear as possible l ve Chosen these subsets so that their convex hulls are disjoint This is not true in genera CS 373 NonLecture E Convex Hulls Fall 2002 for some integer k We can rewrite this as a geometric series 0nlog3 2nlog3 4nlog3 2kniog3 Since any geometric series adds up to a constant times its largest term the total running time is a constant times the time taken by the last iteration which is 0nlogh So Chan s algorithm runs in 0nlog h time overall even without the little birdie Re resentation of the tha orean Theorem By Steve Zelenty CIS 4930 Aesthetic Computing The Pythagorean theorem is the theory that states that the value of the hypotenuse side of a ninetydegree triangle to the second power is equivalent to the sum of the squares of the other two sides of the triangle It can be state simply with the formula Aquot2 Bquot2 CA2 When trying to view this formula from an artistic point of view I decided to represent it as the ow of water being ltered and combined For this physical representation I decided to use real colored water to bring a realistic quality to it I thought it would be interesting to do this in a way that can be simply applied to everyday systems The Pythagorean Theorem AAZ BAZ CA2 And from this formula given a known A and a known B C SQRTCA2 A gt Water falling from left pipe B gt Water falling from right pipe quot2 gt The filters water first goes through gt The combination of filtered A and filtered B gt The tank that holds the water Aquot2 and water Bquot2 CA2 gt Water in tank combined from Aquot2 and Bquot2 SQRT gt Filter attached to the bottom of CA2 tank C gt Water ltered through SQRT in bottom tank How GHQ 07335 V52 n ANGLED VIEW 2LEF1 WE FRONT VIEW Jorg s Graphics Lecture Notes 7 Particles amp Shape Grammars l Particles amp Shape Grammars Kinematics kinematics 7 motion trajectories only 7 without consideration of physical con siderations such as forces7 friction7 inertia etc as opposed to dynamics angle 9 position p p Ft9 forward kinematic equation 9 F 1p inverse kinematic equation We need the set of angles 9 for animation Inverse kinematics is diffcult since F 1 may not be wellde ned there may be several or no way to achive position pi Alternative kegframe animation inbetweening7 or interpolation7 Newtonian Particles position p7 velocity V7 state Y I E R5 as functions of time t Y 7 5 7 Myrna gm To determine the state at time t h from the state at time t need to solve the ODE Examples of force f l gravitational force 0 f 77 0 2 spring force harmonic oscillator between p and q De ne d I p 7 q and d I Hooke s law damping d d d d gtd WP f kspringd do kdamp Jorg s Graphics Lecture Notes 7 Particles amp Shape Grammars 2 repulsing force krepulse f74 i 09701 avoid 0n2 Solving the ODE Euler should not be used But explains basic forwardsolving idea Yt h Yt hYt 0h2 Yt hgY t 0h2 stiff ODE7s Runge Kutta solvers Verlet Integration Implicit Euler Yt h Yt hgYt h t h pm hpt pt Constraints soft approximate and hard eig collision 0 Detection 7 dif cult bounding boxes quadtrees binary space partition ing 0 Reaction Let p I pt 7 pt Where t is the previous time and tquot the time of intersection n is the normal at pt Then the new point is in the direction p215715nngt Jorg s Graphics Lecture Notes 7 Particles amp Shape Grammars This corresponds to an elastic collision no energy loss7 deformation 0 Soft constraints With penalty function min Hp 7 poll Examples 0 bounce c o sphere bouncing intercept With sphere of radius 7 H1 MW AW hH T NormalZ W Jorg s Graphics Lecture Notes Particles amp Shape Grammars Language based models tree shape grammar Example Koch curve snow ake F gt FLFRRFLF gt There exists a unit circle so that the Koch curve inside it has in nite length a N Example F gt FRFFLFF random OPENGLLRfrac Space lling Hilbert curve Fractals self similar structures my Gmth Lectuze New 7 Funds 2 Shape Glammazs thfxamal dmlemmndlm mm mum lnmvw woes Tn u sig e mm A zwoyma 2 mass nactal moun 39 s brawman xardam mamquot dispbamml 7 my cam wnh variance mm m an mewwm yields and human m 127 Mandelbrot set w din Julia 54 z zic 012EC CexAugeJmndelhmtcnsh mmm 54 um 54 m a a m which mm mm mnv ges Easy Chaos Theory Population Growth as a Model Nicholas Hughes C18 4930 Aesthetic Computing April 5 2002 Description This model is a basic understanding of chaos theory using population growth to represent and help understand it Basically this is a model of a forest scene where the trees represent the population and they show growth by moving up and down on the spindle The rivers ow into it and help the trees grow When the ow of the river increases then the trees grow faster When the ow of the river decreases the trees grow at a slower rate This is shown by having the trees move up and down the spindle in correspondence to growing and shrinking respectively e edia used to create this model was primarily wood for instance in the base and ground level of the model Also metal rods were used so that the trees could grow and help model actual tree growth The trees themselves are toy trees that were purchased at an art supply store I wanted to create this model because I found chaos theory to be a very interesting concept I like that it acts unpredictably This physical model achieves that as you can explain to people how the population behaves according to the water ow The population will increase dependent on the water ow and since the trees can move up and down the spindle they can show how the population behaves According to chaos theory the population should increase at a certain rate and nally max out at a certain value Basically population should steadily rise to a certain value If the value of r is 3 or greater though the population will not max out but will jump from one high value to a very low value For example if the population is a value between 0 and 1 and the r value is 27 the value of the population will steady out at 692 If the value of r is 3 or greater though it will never steady out switching between values periodically Stxueture The mathematical formula ofthls population growth ls Pn1 Pm 1 rpm orrt em be seen as next year39s populatror r thls year39s populatror 1 e ths year39s populatror In both cases ms the growth rate of the population Ma m The eomportertts thatmap from the equanonto the model are as follows Pm Thls ls the trees that are on th spmdle r Thls ls the rrverthatleads to the trees rtrs the blue spray pamt on the model Pn1 Thls ls represented agaln by the trees on the spmdle exeeptthrs trme rt ls the trees after they have been movedln the approprrate dlrecnon on the spmdle Tap Deantew atlet have been waved Pn m Pnol ttees Rtvet vattablet l Ttees Pot mam atletbemg waved nnthe spmdle see stee vlew Rtvetevettehle t mtheeeuetten mam lt4 V a i V immm n3 2 7 mgim 35mm 53 52 n3 a 7 9532ng mgim i is23123339 em ame 3 2n keagm rm iii rm Em n322sm n m2mm Arm 13 3 Im 53 E mi 9 a gamma is a 523mg 35 a was 5 2
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'