| ||

- Algorithm 2.1: Computing an interval tree for a set of intervals, recursively.
- Algorithm 2.2: Answering a stabbing query for an interval tree v and a value x
_{ q }, recursively. - Algorithm 2.3: Construction of a simple balanced one-dimensional search tree.
- Algorithm 2.4: Building a segment tree.
- Algorithm 2.5: Insertion of a segment s in the segment tree.
- Algorithm 2.6: The stabbing query for a segment tree.
- Algorithm 2.7: The inductive construction algorithm of a multi-level segment tree.
- Algorithm 2.8: The inductive query operation for a multi-level segment tree.
- Algorithm 2.9: Recursive construction of a kd-tree .
- Algorithm 2.10: The query procedure of the d-dimensional kd-tree.
- Algorithm 2.11: The inductive construction algorithm of a d-dimensional range tree.
- Algorithm 2.12: The inductive query operation for a d-dimensional range tree.

- Algorithm 3.1: The first building block of the algorithm for Boolean operations is the procedure that splits a BSP.
- Algorithm 3.2: The second building block for Boolean operations merges two BSPs.
- Algorithm 3.3: Testing for ray-scene intersections with a deferred BSP.

- Algorithm 4.1: Construction of BVHs by insertion.
- Algorithm 4.2: General scheme of hierarchical collision detection.
- Algorithm 4.3: Time-critical traversal scheme. The recursive procedure is now replaced by a queue.

- Algorithm 6.1: The incremental construction of the Voronoi diagram.
- Algorithm 6.2: Inserting a new site in a Delaunay triangulation.
- Algorithm 6.3: Searching for the triangle in the Delaunay diagram that contains p.
- Algorithm 6.4: The DAG and its DCEL are updated by flip operations, cross-references between triangles in DAG and T(DAG) are created by FlipDCEL.
- Algorithm 6.5: Update of the DAG and its DCEL by inserting p into triangle t.
- Algorithm 6.6: The construction of a slab search structure for the region query returns a 2D arrayS. For each vertical line, the array contains a sorted array of crossing segments.
- Algorithm 6.7: The region query can be answered efficiently using a slab decomposition and a binary search.
- Algorithm 6.8: Answering a region query by tracing a line through the DCEL.
- Algorithm 6.9: Lloyds algorithm to compute a centroidal Voronoi diagram for a region R.
- Algorithm 6.10: Algorithm to generate a mosaic.
- Algorithm 6.11: Simple Monte Carlolike method to compute natural neighbors.

- Algorithm 7.1: Simple algorithm to construct the GG, starting from the Delaunay graph of a set of points.
- Algorithm 7.2: Simple algorithm and heuristic to build the GG.
- Algorithm 7.3: Simple algorithm to compute the r-SIG in O(n) time on average.
- Algorithm 7.4: Simple algorithm to clean (edit) a training set from incorrectly labeled samples.
- Algorithm 7.5: Pseudocode for the root-finding algorithm based on interpolation search. P is an array containing the points of the shortest path from p
_{ 1 }= P_{ 1 }to p_{ 2 }= P_{ n }, which can be precomputed. d_{ i }= f_{ B }(P_{ i }) approximates the distance of P_{ i }to object B. (*) Note that either d_{ l }or d_{ r }is negative. - Algorithm 7.6: This algorithm can be used to initialize P for Algorithm 7.5 if precomputing and storing all shortest paths in a map is too expensive. (q is a priority queue.)

- Algorithm 8.1: Basic main loop of most kinetic data structures.
- Algorithm 8.2: Simple algorithm for answering a stabbing query.
- Algorithm 8.3: Updating a kinetic segment tree.

- Algorithm 9.1: FastTwoSum easily computes a non-overlapping expansion.
- Algorithm 9.2: TwoSum computes a non-overlapping expansion x + y = a + b.
- Algorithm 9.3: GrowExpansion computes a non-overlapping expansion h
_{ 1 }+ h_{ 2 }+ h_{ m }_{ +1 }= e + b. - Algorithm 9.4: ExpansionSum computes a non-overlapping expansion h
_{ 1 }+ + h_{ m }_{ + }_{ n }= e + f. - Algorithm 9.5: TwoProduct computes a non-overlapping expansion x + y = a — b.
- Algorithm 9.6: Split splits a floating-point value a into a = x + y,where x has (p ˆ s) bits and y has (s ˆ 1) bits.
- Algorithm 9.7: ScaleExpansion computes a non-overlapping expansion h
_{ 1 }+ + h_{ 2 }_{ m }= be. - Algorithm 9.8: Compress computes a non-overlapping expansion h
_{ 1 }+ + h_{ n }= e with non-zero entries. The largest component is a good approximation of e. - Algorithm 9.9: The ordering predicate for a simple perturbation scheme.
- Algorithm 9.10: An -arithmetic test for T(a, b, c) and T(a, c, b).
- Algorithm 9.11: Computing the upper-left hull of an y-monotone chain.

- Algorithm 10.1: Computing the binary decomposition of a set of objects D.
- Algorithm 10.2: Collecting all elements of W.
- Algorithm 10.3: Computing the query for the binary decomposition W.
- Algorithm 10.4: Destroying the structure W.
- Algorithm 10.5: Inserting an element into the binary decomposition.
- Algorithm 10.6: The extended DELETE operation incorporates the half- size rule and the WeakDelete operation.
- Algorithm 10.7: The extended INSERT operation.

Geometric Data Structures for Computer Graphics2006

ISBN: N/A

EAN: N/A

EAN: N/A

Year: 2005

Pages: 69

Pages: 69

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net