# Applications of spatial data structures: computer graphics, image proccessing, and GIS - Hanan S.

ISBN 0-201-50300-X

**Download**(direct link)

**:**

**192**> 193 194 195 196 197 198 .. 248 >> Next

4.69. Each node is visited at most four times as it can only be a neighbor of four nodes.

4.70. Hunter and Steiglitz [Hunt78, Hunt79a] suggest the following method. Assume that we know the adjacency of edges but not necessarily the clockwise ordering of the edges. First, find the leftmost point in the polygon, say ë. Clearly anything to the left of A is outside. Now, examine the angle formed by the two line segments that meet at ë. Points along its angle bisector are candidates for points inside the polygon. Clearly those points that are infinitesimally close to A but along the angle bisector are inside ë. Now we must determine how far down the angle bisector it is safe to go and still remain within the polygon. This is achieved by finding the leftmost vertex that is to the right of A, say â. Draw a vertical line through â, say L, and notice that, to its left, is a simple triangle, all of whose interior points are also interior to the polygon. Choose the point that is halfway down the angle bisector of A toward L, say C. The rest of the process is easy. In particular, now we can determine which of the sides of the edges that are adjacent at a are inside the polygon and then traverse the edges in a clockwise order so that the inside of the polygon is to the right. Given v vertices, this process takes O(v) time.

4.71. The maximum degree of a vertex.

4.72. It ensures that the decomposition stops as soon as possible. An alternative formulation is that if a leaf node contains a vertex, say v, then at least one of its brothers must contain a vertex or a q-edge that is a segment of an edge not incident at v. For example, it precludes the further subdivision of the node containing d in Figure 4.24.

4.73. Condition 2' does not imply condition 1 due to the possible presence of isolated vertices. Conditions 1, 2', and 4 are insufficient because polygonal maps exist that would require a pm1 quadtree of infinite depth to satisfy condition 2'. For example, consider vertex e in Figure 4.24. We observe that the node containing vertex E does not satisfy condition 2' because of the two q-edges incident at it. Assume that the x and ó coordinates of E cannot be expressed (without error) as a rational number whose denominator is a power of two (e.g., let both coordinates be one-third). This means that E can never lie on the boundary between two quadrants. Thus by virtue of the continuity of the q-edges, no matter how many times we subdivide the quadrant containing vertex E, there will always exist a pair of (possibly infinitesimally small) q-edges incident at e that will occupy the same quadtree leaf.

4.74. pmjnsert requires only that the dictionary field be set immediately after the call to clip_lines in pmjnsert and that dictionary(p) be left unmodified in split_pm_node. The revised pm_delete is considerably simpler, as shown below.CHAPTER 2 II 409

recursive procedure PM_DELETE(P,R)

Ã Delete the list of edges pointed at by P in the PM (i.e., PM1, PM2, and PM3) quadtree rooted at R. It is assumed that the DICTIONARY field of all gray nodes indicates the edges in the subtrees below. PM_CHECK is generic. It is replaced by its appropriate analog for the PM1, PM2, and PM3 quadtrees. */ begin

value pointer edgelist Ð; value pointer node R; pointer edgelist L; quadrant I;

L <- CLIP_LINES(P,SQUARE(R));

if empty(L) then return; Ã None of the edges is in the quadrant */ DICTIONARY(R) <- SET_DIFFERENCE(DICTIONARY(R),L); if GRAY(R) then begin

if PM_CHECK(DICTIONARY(R),SQUARE(R)) then PM_MERGE(R) else begin

for I in {'NW', 'NE', 'SW', 'SE'} do PM_DELETE(L,SON(RJ)); end; end; end;

recursive procedure PM_MERGE(P)

Ã Merge the four sons of the quadtree rooted at node P. The storage taken up by the four sons is reclaimed by use of returntoavail. This process is recursive in the case of a PM1 quadtree. */ begin value pointer node P; quadrant I;

for I in {'NW', 'NE', 'SW', 'SE'} do begin

if GRAY(SON(P,l)) then PM_MERGE(SON(P,l)) else begin \

returntoavail(SON(P,l)); SON(P1I) <- NIL; end; end; end;

4.75. An upper bound when leaf and gray nodes are counted is (n — i) • m,-. This is the same as the total path length of the tree (ignoring nonleaf nodes) if there is only one edge stored with each leaf node. A lower bound can be estimated by assuming that for each gray node, at most three of its sons are intersected by a given edge. Actually a better estimate can be achieved by noting that if three sons are intersected at one level, then only one son is intersected at the next level. See the discussion of space requirements in410 II

SOLUTIONS TO EXERCISES

Section 1.2 and the analysis of the dynamic insertion of an edge in a pm1 quadtree in Section 4.2.3.1 of [Same90a].

4.76. If all four sons of a node are gray, then at least one son contains a vertex, say v, and an edge that does not intersect v.

4.77. A subtree containing two edges cannot be merged until it is large enough to include their common vertex without including any other vertices or nonsharing edges.

**192**> 193 194 195 196 197 198 .. 248 >> Next