# UMD CMSC 420 - Quad Trees (45 pages)

Previewing pages*1, 2, 3, 21, 22, 23, 43, 44, 45*of 45 page document

**View the full content.**## Quad Trees

Previewing pages *1, 2, 3, 21, 22, 23, 43, 44, 45*
of
actual document.

**View the full content.**View Full Document

## Quad Trees

0 0 83 views

Lecture Notes

- Pages:
- 45
- School:
- University of Maryland, College Park
- Course:
- Cmsc 420 - Data Structures

**Unformatted text preview: **

Quad Trees CMSC 420 Applications 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 struct Point const int DIM 3 double coord DIM Vectors direction and magnitude length in that direction 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 What s a good representation for a polygon simple if they don t corss convex hull of a set of points P smallest convex set that contains P convex if any line segment connecting two points on its circularly surface lies entirely within the shape linked list of points Geometric Operations P Q is a vector going from point Q to P P Q Q v is a point at the head of vector v if v were anchored at Q x Q v u serially walk along v and then u v u is the direct shortcut v u v u Great use for C operator overloading Types 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 Rectangle Circle center C R low 1 R high 0 R low 0 Dimension 0 Dimension 1 R high 1 Question how do you compute the distance from circle center to the rectangle Intersection of Circle Rectangle R high 1 R low 1 R low 0 Instead of a lot of special cases break the distance down by dimension component R high 0 Distance square root of the sum of the squares of the distances in each dimension d dx2 dy2 dz2 d2 distx C R 2 disty C

View Full Document