| Hide textShow text Hide pseudo-codeShow pseudo-code | |
|
From the given set of points, find the pair closest to one other. Use the mergesort-based method described in the given pseudocode. OverviewThis method for finding the closest pair of points divides the set of points into smaller and smaller subsets, until a set has only two points in it. It is trivial to find the closest pair of points for such set: it is the only pair in the set. After the division, the subareas are merged into larger ones. During each merge procedure the method checks if a new closet known pair of points can be found in the combined subarea. In each merge procedure the method checks all points that are closer to the border of the subareas than the distance between the closest known pair of points. Each point is compared to a maximum of four previously checked points. The order in which the points are checked is given by their Y-coordinate. The points are recursively divided into subareas: The closest_pair function will call itself with different parameters. On each call the parameters p and r define the left and right border point in the area. Each recursive call will divided the area into two subareas, and calls itself recursively for these subareas. After returning from the recursive calls, the method has two subareas, for which it needs to check the border. DetailsThe CLOSEST_PAIR function in the exercise will call itself recursively. A recursive call can be done by selecting from the array Points the indices included in the call by clicking the lowest and highest index included and then pressing the call-button. When call is pressed, the selected interval is added to the Call stack. The selected indices are highlighted using red color. You can return from a recursive call using the Return-button. The function MERGE, not specified in the pseudocode, will merge ordered subarrays A[p .. q] and A[q+1 .. r] into one ordered subarray A[p .. r] as in the mergesort algorithm. The indices are ordered by the y-coordinate. The MERGE functionality in the exercise is created by dragging and dropping the required elements from the Points table to the correct indices in the Auxiliary table. The move-button should be used to move the elements from Auxiliary table to the Points table. Pressing the move button will highlight the region of the Area point visualization that will be checked by the lines 7 to 12 in the CLOSEST_PAIR function. The functionality of the CHECK-function can be achieved through the user interface by selecting the points in the Area visualization. When two points are selected by clicking them a line segment is drawn between them, and the distance between points is shown in the Distance field. The closest known pair of points is stored in the Closest Pair table. The index 0 in the table should hold the point with the smaller value of y-coordinate and index 1 the point with the higher value of y. The division in line 2 of CLOSEST_PAIR is rounded down. The syntax point.x stands for the x-coordinate of the point. | 1. Let min be a global floating point variable initialized to positive infinity 2. Let cp1 and cp2 be global point variables used to store the closest pair found so far 3. Let a be the array used to store the points, where the points are arranged in increasing order by their X coordinate 4. CLOSEST_PAIR(a,0,a.length-1)
CLOSEST_PAIR(Array a, int p, int r)
1. if p < r
2. q = (p+r)/2
3. middle = a[q].x
4. CLOSEST_PAIR(a,p,q)
5. CLOSEST_PAIR(a,q+1,r)
6. MERGE(a,p,q,r)
7. for each point between indices p and r
8. Let curr be the point being examined
9. if abs(curr.x - middle) < min
10. For the four previous examined
points p1, ..., p4
11. Let p_i be a previous examined point
12. CHECK(curr,pi)
CHECK(Point p, Point o) 1. if o is null, return; 2. dist = sqrt((p.x-o.x)^2 + (p.y-o.y)^2) 3. if dist < min 4. min = dist 5. cp1 = o 6. cp2 = p |