Advanced Data Structures Theory and Applications

This chapter demonstrates several applications of data structures to image and graphics processing operations. We selected three applications (among many) that are useful in these industries: (1) R trees for searching objects in maps; (2) KD trees for optimizing computations in geographic information systems (GISs); and (3) ray shooting for graphics rendering. The chapter ends with a group of projects.

Objective 18.1 This chapter addresses computer graphics applications of R trees, KD trees and octrees.

Nearest neighbor and certain other searches involve degree measurements and parallelograms. A basis node is inserted into the priority queue. The search of closest entries in the queue continues until the queue is empty or results are returned. Various aspects of R trees (children, node operations, leaves) are detailed in Section 6.4. This approach is useful for obtaining geographic information by calculating distance metrics.

R trees provide spatial information by calculating geographical coordinates and geometric structures.

R trees can store abstract objections like restaurant locations and map insets and answer queries like finding museums within a certain radius, illustrating the best route to a specific location, and finding the nearest gas station.

R trees can accelerate nearest neighbor searches for various distance metrics including great-circle distances.

Insertion of an object requires the recursive traversal of the tree from the root. At each step, the rectangles on the current directory are examined and the candidate is chosen using heuristic approach (e.g., choosing a rectangle with minimum enlargement). The search proceeds until it reaches the leaf node. The tree should be notified of full nodes before insertion. A heuristic approach splits a full node in half to prevent need for an exhaustive search. The newly created node traverses to the previous level; the overflow propagates to the root note [182].

Deleting the entry from a page requires the adaptation of the parent page. A full page will not balance with its neighbors. It will dissolve and the nodes will be reinserted. If a root node contains fewer elements, the tree height will decrease.

R tree searching is similar to B+ tree searching; both start at the roots. All nodes contain sets of rectangles and pointers to indicate child nodes. Every leaf node contains rectangles of spatial objects. Every rectangle in a node must decide whether to overlap. Corresponding nodes must also be searched if overlap occurs. Searching continues recursively until the child note is traversed. When a leaf node is searched, the boundary box is also searched and its results are included if they lie within the search rectangle.

GIS studies are essential in fields like geography, cartography, civil engineering, and image processing. Processing of geographic information involves integrated database techniques and pictorial data processing. Recent research has developed many methods for handling map data. Map information is stored graphically as points, sequences of straight line segments, and regions (polygons). Distances and other spatial data are stored in matrices.

Points, line polygons, and other graphics are used to map geographic objects. KD trees can optimize GIS search queries significantly. KD trees work recursively by partitioning two-dimensional maps into rectangular blocks using parallel lines and coordinates. Each block represents a page in disk storage. Sets of records are clustered into small groups based on spatial proximity. Partitioning by various tree structures can reduce the time needed for answering queries.

GISs store large amounts of data and require secondary memories to store excess data. Paging (partitioning records into small groups) is one way to organize huge data quantities. Using search keys to handle GIS queries is an important function. One issue is the difficulty of calculating and storing distances between objects in advance of queries. A GIS will typically have to read many records in disks and calculate distances whenever a metric response is needed. This type of processing involves expensive computation time and access to huge numbers of pages.

Matsuyama et al. [183] tried to facilitate query responses in GISs by reducing the number of accessed pages. Although a user can inquire about any area on a two-dimensional map, his queries usually focus on a small area. To respond to such limited inquiries, information about neighboring records should be stored on the same page, in a pattern identical to clustering data for identification. Geographic data processing requires dynamic file structures so that data can be inserted, modified, and deleted easily.

To achieve dynamic partition of a record, A KD tree search [183] divides two-dimensional map spaces into rectangular blocks by setting lines parallel to rectangular axes. Each block matches a page on a hard disk where all records including block items are stored. Accessing a disk on a hard page requires verification of the corresponding rectangle on a map. Processing can proceed quickly as soon as the page is accessed from main memory.

1.Lengths of the vertical and horizontal sides of the rectangle are compared for partitioning.

2.The rectangle is divided into two parts with the help of a straight line perpendicular to the longer side. The dividing line must ensure that each portion contains the same amount of data.

3.Repeat Steps 1 and 2, for each rectangle until the amount of data in any rectangle becomes less than the capacity of a page.

The position of the rectangle can be represented by double trees. The node of the tree represents a rectangular area generated by the division process. The root node points to the whole map and leaf nodes represent blocks related to pages.

If excessive insertions cause page overflow, divide the page into two pages using the above steps. Deleting entries is more complicated because the user must decide whether a page is associated with another page by checking neighboring trees.

Whenever a deletion creates an empty page, the leave node of the tree is marked “NIL”. A tree will become unbalanced after many insertions and removals and the database may need restructuring.

A file system can be reorganized by (1) partitioning map space as described above; or (2) saving the binary tree used in partitioning to control page access. File organization can significantly improve handling of distance queries. To find all points in a specific rectangle, we perform a comprehensive search using recursive algorithms to compare rectangle applications. If the range is contained on both sides of the split line, only the child of the related node should be searched.

▪ Example 18.1 — Partitioning city map. After a map is partitioned into blocks, KD tree partitioning is applied, using the centroids of the blocks as data points. A secondary KD tree handles page allocation. Each block corresponds to a disk track and pages whose centroids are contained in a block are allocated to the same track. Quadtrees can simplify searches for adjacent pages [183]. ▪

Roth [184] described ray casting (also known as ray shooting) in detail. The technique is used to process queries in computational geometry. A set of objects is assigned to d-dimensional space where the objects are preprocessed and sent to a data structure. The first object of each query ray is subject to a “fast hit.”

To achieve select pixels in any order, then go from top to bottom and from left to right. The camera in the world coordinate system provides the rays. The direction is calculated by locating the four corners of the virtual image in the first world space, then splitting. The normalized direction is calculated from the position of the camera to the virtual pixel.

The initial camera is tested for intersections with three-dimensional visuals containing triangles and other graphics primitives. If the ray does not hit an object, pixels in a certain area are colored. To locate an intersection, the system must review color, structure, content and other relevant data. If the ray hits the center of a triangle, information will be calculated by interpolating the data from the top.

Shadow is an important light effect that can be easily calculated by tracking the rays. If shading illumination for a given point is required the system must capture additional rays between the point and light source. Light can only contribute in the final color if nothing happens between the ray point and the light source. The equation of light which is a straight line in the quarter, can be easily adapted to handle ray because if the light is blocked, it will be 0.

Another powerful feature with ray tracing is the exact reflection of complex surfaces. To create an ideal mirror surface rather than computing light through the normal equation, create a new ray of reflection and find it on the stage. All reflected, broken, and other rays are called secondary rays. Rays mirrored in the form of shade should be moved slightly on the surface to prevent the surface from crossing again.

Radiation due to defraction can be used to tilt light to focus on transparent surfaces. The process is called transmission. When a beam attacks a transparent surface (like glass or water), then a new refracted ray is generated. We will assume that the transmitted beam will follow Snell’s law as (n₁sinθ₁ = n₂sinθ₂), where n₁ and n₂ are the indices of refraction for the two materials.

The classical ray tracking algorithms have features like shadow, reflection and refraction. Depending on the number of lights and type of material, a primary ray can produce many secondary and shadow rays. These beams can be considered as the structure of the tree.

The ray intersect routine uses a ray as input, returns a true value if the object is hit, and a false return if the object is missed. If an object is hit, the data is transmitted into the intersection class.

The basic concept of the binding volume hierarchy is inserting a complex object into a hierarchical structure. For example, if the size of a bounding volume hierarchy is limited, the system can provide more areas until the lower containing real geometry is reached. In this area, there are many other areas, until we finally reach the lower level, where there is real geometry like triangles in the globular circles. To test a ray in a scene, we cross the highest level hierarchy. Whenever an area is attacked, we test its spheric structures and finally tests triangles and other primitives. Normally, the volume limit can reduce beam crossing time from O (n) to O (log n), where the n is the number of primitives used in the scene. This reduction in linearity for logarithmic performance improves capacity and makes creation of scenes with millions of primitives possible.

Octree construction starts with placing a cube around a scene. If more than a certain number of primitives (e.g., 10) occupy the cube, then it is evenly divided into 8 cube, which is re-tested and finally retrieved. The area is a more regular area structure and gives a clear rule of subdivision and does not overlap between cells. The octree is an attractive option but it is not yet ideal for ray shooting operations.[207]

KD tree construction starts with placing a box (essentially a cube) around a scene. If the box contains many primitives, other systems would divide into octets. A KD tree splits the box into two boxes that do not have to be equal. Any arbitrary point in a partitioned box can be at X, Y, or Z. This quality makes KD trees adaptable and better suited to process wrong geometries. They are effective for tracking rays. Their main disadvantage is that the depth of the trees can be deeper, because of the intersection of the Beam to spend more time handling test intersections and less time on older ones.

A binary space partitioning (BSP) tree is similar to a KD tree. Both split spaces into two boxes that are not necessarily equal. KD tree splitting is limited to the XYZ axis. A BSP tree allows the splitting plane to be placed anywhere and aligned in any direction. The disadvantage is that the number of heuristics makes choosing a splitting plane location difficult. Both BSP and KD trees perform ray tracing well.

It is possible to separate a location in a unified network instead of hierarchically; the result is a uniform grid. The process is fast but it incurs high memory costs, especially for large and complex scenes. The performance of a uniform grid decreases in computations involving wide varieties of shapes and places of primitives so they are not practical for use in general ray accelerator structures.

A hierarchical network starts with a grid. Each cell containing many primitives is subdivided. One example is a hierarchical network limited to 2 × 2 × 2 subdivisions. Some hierarchical networks can support subdivisions in any number of cells. They perform beam tracking very well, especially when processing relatively similar shapes.

Project 18.1 — Emergency Assistance. Create an android application that allows users to connect directly with hospitals, fire stations, and police stations by pressing a panic button. The application must allow users to automatically call emergency help and convey user locations to family members. [Hint: Use a KD tree and virtual coordinate system (to compensate for GPS unavailability) in your design.]

Project 18.2 — RSSI based Indoor Positioning System. GPS usually tracks android phone locations on Google maps. Consider a scenario when GPS does not work or you want to track a location on a map. You have to create a local RSSI-based system to handle both situations. [Hints: Your system should gather and map data it using the indoor environment is estimated by FMM which is simultaneous algebraic reconstruction technique (SART). You can use any data structure to implement your system and refer to Sugano [185].]

Project 18.3 — Graphical Password via Image Segmentation. Consider a user who can enter his password as an image. When the system receives the image, it breaks it into segments and stores them in an array. The next time the user authenticates his password, the segmented image is shuffled and returned to the user. If the user selects part of the image, he is either authenticated or stopped from using the system. [Hint: The system uses image segmentation based on coordinates of the segmented image stored in different parts of the system.]

Project 18.4 — Image Processing to Detect Expressions. Emotions can be expressed in many ways. Create a system that can analyze emotions based on expression recognition. The system will try to find an emotion based on an input image. Images are prone to noise so a preprocessing step must be incorporated to remove noise and ensure a correct result. Your system should achieve a 50 to 60% success rate. [Hint: use an effective expression recognition algorithm.]