Quad TreesCMSC 420Applications of Geometric / Spatial Data Structs.•Computer graphics, games, movies•computer vision, CAD, street maps (google maps / google Earth)•Human-computer interface design (windowing systems)•Virtual reality•Visualization (graphing complex functions)Geometric Objects•Scalars: 1-d poin•Point: location in d-dimensional space. d-tuple of scalars. P=(x1,x2,x3...,xd)-arrays: double p[d];-structures: struct { double x, y, z; }-good compromise: •Vectors: direction and magnitude (length) in that direction.struct Point { const int DIM = 3; double coord[DIM];};Lines, Segments, Rays•Line: infinite in both directions-y = mx + b [slope m, intercept b]-ax + by = c-In higher dimensions, any two points define a line.•Ray: infinite in one direction•Segment: finite in both directions•Polygons: cycle of joined line segments-simple if they don’t corss-convex if any line segment connecting two points on its surface lies entirely within the shape.-convex hull of a set of points P: smallest convex set that contains PWhat’s a good representation for a polygon?circularly linked list of pointsGeometric Operations•P - Q is a vector going from point Q to P•Q + v is a point at the head of vector v, if v were anchored at Q•v + u: serially walk along v and then u. v+u is the direct shortcut.•Great use for C++ operator overloading.PQQxv uv+uTypes of Queries•Is the object in the set?•What is the closest object to a given point?•What objects does a query object intersect with?•What is the first object hit by the given ray? [Ray shooting]•What objects contain P?•What objects are in a given range? [range queries]Intersection of Circle & RectangleR.high[0]R.low[0]Dimension 0R.low[1]R.high[1]Dimension 1Circle center = CQuestion: how do you compute the distance from circle center to the rectangle?Intersection of Circle & RectangleR.high[0]R.low[0]R.low[1]R.high[1]Instead of a lot of special cases, break the distance down by dimension (component)d2 = distx(C,R)2 + disty(C,R)2Distance = square root of the sum of the squares of the distances in each dimensiond = √dx2 + dy2 + dz2distx(C,R) is 0 unless C is in blue regionsdistance(C, R): dist = 0 for i = 0 to DIM: if C[i] < R.low[i]: dist += square(R.low[i] - C[i]) else if C[i] > R.high[i]: dist += square(C[i] - R.high[i]) return sqrt(dist)Distance between point C and rectangle RWhy are geometric (spatial) data different?•In 1-d:-we usually had a natural ordering on the keys (integers, alphabetical order, ...)-But how do you order a set of points?•Take a step back:-In the 1-d case, how did we use this ordering?-Mostly, it gave us an implicit was to partition the data.•So:-Instead of explicitly ordering and implicitly partitioning, we usually: explicitly partition.-Partitioning is very natural in geometric spaces.No natural ordering...Why are geometric (spatial) data different?•In 1-d:-usually the static case (all data known at start) is not very interesting-can be solved by sorting the data (heaps => sorted lists, balanced trees => binary search)•With geometric data, -it’s sometimes hard to answer queries even if all data are known (what’s the analog of binary search for a set of points?)-Therefore, emphasize updates less (though we’ll still consider them)-Model: preprocess the data (may be “slow” like O(n log n)) and then have efficient answers to queries.Static case also interesting...Point Data Sets –!Today•Data we want to store is a collection of d-dimensional points.-We’ll focus on 2-d for now (hard to draw anything else)•Simplest query: “Is point P in the collection?”PR QuadtreesPR Quadtrees (Point-Region)•Recursively subdivide cells into 4 equal-sized subcells until a cell has only one point in it.•Each division results in a single node with 4 child pointers.•When cell contains no points, add special “no-point” node.•When cell contains 1 point, add node containing point + data associated with that point (perhaps a pointer out to a bigger data record).PR Quadtrees Internal NodesNESESWNWNENWSESWPR QuadtreesNESESWNWLMNPQRLMNPQRFind in PR QuadtreesLMNPQRLMNPQRInsert in PR Quadtrees•insert(P):-find(P)-if cell where P would go is empty, then add P to it (change from to ) -If cell where P would go has a point Q in it, repeatedly split until P is separated from Q. Then add P to correct (empty) cell.•How many times might you have to split?unbounded in nDelete in PR Quadtrees•delete(P):-find(P)-If cell that would contain P is empty, return not found!-Else, remove P (change to ).-If at most 1 siblings of the cell has a point, merge siblings into a single cell. Repeat until at least two siblings contain a point.•A cell “has a point” if it is or .Features of PR Quadtrees•Locations of splits don’t depend on exact point values (it is a partitioning of space, not of the set of keys)•Leaves should be treated differently that internal nodes because:-Empty leaf nodes are common, -Only leaves contain data •Bounding boxes constructed on the fly and passed into the recursive calls. •Extension: allow a constant b > 1 points in a cell (bucket quadtrees)Height Lemma•if -c is the smallest distance between any two points-s is the side length of the initial square containing all the points•Then-the depth of a quadtree is ≤#log(s/c) + 3/2internal node of depth iside length = s/2idiagonal length = s√2/2iTherefore, s√2/2i ≥ c cHence, i ≤#log s√2/c = log(s/c) + 1/2 Height of tree is max depth of internal node + 1, so height ≤ log(s/c) + 3/2Size CorollaryThm. A quadtree of depth d storing n points has O((d+1)n) nodes.Proof: Every internal node represents a square with at least 2 points in it. Hence, each level has fewer than n nodes.North Neighbornorth neighbor of a SW or SE node is the NW or NE node respectivelynorth neighbor of the root is NULLNorth neighbor of a NE or NW node is a child of the north neighbor of its parent.North neighbor of a cell S at depth i is the deepest node of depth ≤ i that is adjacent to the north side of S.Algorithm: walk up until you get an easy case, apply easy case, and then walk down, moving to SW or SE as appropriatedef NorthNeighbor(v, Q): if parent(v) is None: return None if v is SW-child: return NW-child(parent(v)) if v is SE-child: return NE-child(parent(v)) u = NorthNeighbor(parent(v), Q) if u is None or is_leaf(u): return u if v is