Assume we are given a red/green picture defined a 2^h times 2^h grid. E.g. pixel
ID: 3865361 • Letter: A
Question
Assume we are given a red/green picture defined a 2^h times 2^h grid. E.g. pixels. Each pixel is either green or red. (more general and interesting examples - soon) Need to represent the shape "compactly" Need a data structure that could answers multiple types of queries. For example: For a given q, is q red or green? For a given query disk D, are there any green points in D? How many green points are there in D? Etc etc Assume we are given a red/green picture defined a 2^h times 2^h grid. of pixels. Each pixel has as a unique color (Green or Red) Every node v elementof T is associated with a geometric region R(v) input - a node v elementof T, and a shape S. output - a Quadtree T_v representing the shape of S within R(v)). If S is fully green in R(v), or S is fully red in R(v) = then v is a leaf, labeled Green or Red. Return: Otherwise, divide R(v) into 4 equal-sized quadrants, corresponding to nodes v.NW, v.NE, v.SW, v.SE. Call constructOT recursively for each quadrant.Explanation / Answer
Quad Tree basically use in Image processing technologies and For any image or image part it was placed in 2h * 2h grid .
Assuming a region which is a subset of a 2n by 2n array in the form of unit-square pixels. The most common region representations used in image processing are the binary array . The binary array represents region pixel regions as 1 and nonpixel regions as 0's . The quad tree is formed by drawing a combination of 1s and 0s