Tham khảo tài liệu 'thuật toán algorithms (phần 37)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | GEOMETRIC INTERSECTION 353 by A is performed on the rightmost tree in the diagram above. This search discovers the intersections between A and E F and I. Recall that although G and J are visited during this search any points to the left of G or to the right of J would not be touched. Finally the upper endpoints of G J F E and I are encountered so those points are successively deleted leading back to the empty tree. The first step in the implementation is to sort the line endpoints on their y coordinate. But since binary trees are going to be used to maintain the status of vertical lines with respect to the horizontal scan line they may as well be used for the initial y sort Specifically we will use two indirect binary trees on the line set one with header node hy and one with header node hx. The y tree will contain all the line endpoints to be processed in order one at a time the x tree will contain the lines that intersect the current horizontal scan line. We begin by initializing both hx and hy with 0 keys and pointers to a dummy external node z as in treeinitialize in Chapter 14. Then the hy tree is constructed by inserting both y coordinates from vertical lines and the y coordinate of horizontal lines into the binary search tree with header node hy as follows procedure buildytree var N k xl yl x2 y2 integer begin readln N for k l to N do begin readln xl x2 lines k xl lines k . yl lines k . x2 Iines k . y2 bstinsert k yl hy if y2 yl then bstinsert k y2 hy end end This program reads in groups of four numbers which specify lines and puts them into the lines array and the binary search tree on the y coordinate. The standard bstinsert routine from Chapter 14 is used with the y coordinates as keys and indices into the array of lines as the info field. For our example set of lines the following tree is constructed 354 CHAPTER 27 Now the sort on y is effected by a recursive program with the same recursive structure as the treeprint routine for binary .
