tailieunhanh - ALGORITHMS phần 7

điểm phải được trên thân tàu. Sau đó, neo đậu tại điểm đó và tiếp tục "quét" cho đến khi nhấn một điểm, vv, cho đến khi "gói" là hoàn toàn "gói" (điểm bắt đầu được bao gồm một lần nữa). Sơ đồ dưới đây cho thấy thân tàu được phát hiện theo cách này. | 324 CHAPTER 25 point must be on the hull. Then anchor at that point and continue sweeping until hitting another point etc. until the package is fully wrapped the beginning point is included again . The following diagram shows how the hull is discovered in this way. Of course we don t actually sweep through all possible angles wejust do a standard find-the-minimum computation to find the point that would be hit next. This method is easily implemented by using the function theta. pl p2 point developed in the previous chapter which can be thought of as returning the angle between pl p2 and the horizontal though it actually returns a more easily computed number with the same ordering properties . The following program finds the convex hull of an array p of points represented as described in the previous chapter the array position is also used to hold a sentinel FINDING THE CONVEX HULL 325 function wrap integer var i min M integer minangle v real t point begin min l for i 2 to Ndo if p i .y p min .y then min i M o- p N .l p nim minangle repeat M M 1 t p M p A4 p min p min t min N l v minangle minangle for to do if then if then begin min i rninang e theta p M p min end until min N l wrap M end First the point with the lowest y coordinate is found and copied into in order to stop the loop as described below. The variable M is maintained as the number of points so far included on the hull and v is the current value of the sweep angle the angle from the horizontal to the line between p M-l and p M . The repeat loop puts the last point found into the hull by exchanging it with the Mth point and uses the theta function from the previous chapter to compute the angle from the horizontal made by the line between that point and each of the points not yet included on the hull searching for the one whose angle is smallest among those with angles bigger than v. The loop stops when the first point actually the copy of the first point that was put into is encountered .