Нүктелер жиыны үшін дөңгелек қабықшаны есептеу алгоритмі

Кіріспе

Нүктелер жиынтығында дөңгелек қабықшаны есептеу алгоритмі

Грэхамның сканерлеу әдісі – жазықтықтағы нүктелер жиынтығының дөңгелек қабықшасын табу әдісі, уақыт күрделілігі O(n log n) шамасында. Бұл әдіс 1972 жылы алғашқы алгоритмін жариялаған Рональд Грэмнің есімімен аталады. Алгоритм дөңгелек қабықшаның шекарасы бойынша реттелген барлық төбелерін анықтайды. Шекарадағы ойыстарды тиімді анықтау және жою үшін ол стек пайдаланады.

Алгоритм

Алғашқы қадам – y-координатының ең төмен нүктесін табу. Егер жиынның бірден көп нүктесінде ең төменгі y координатасы болса, онда үміткерлердің ішінен ең төменгі x координатасы бар нүкте таңдалуы керек. Бұл нүктеге P деп атаңыз. Бұл қадам O(n) уақыт алады, мұнда n – нүктелердің саны. Келесі қадамда нүктелер жиыны олардың және P нүктесінің x оське қатысты бұрышы бойынша өсу тәртібімен сұрыпталуы керек. Бұл үшін кез келген жалпы мақсаттағы сұрыптау алгоритмін қолдануға болады, мысалы, heapsort (O(n log n)). Бұрыш бойынша сұрыптау үшін бұрышты есептеудің қажеті жоқ. Косинус нүктелік көбейтіндісі арқылы оңай есептеледі немесе түзудің еңістігін қолдануға болады. Егер сандық дәлдік маңызды болса, сұрыптау алгоритмінде салыстыру функциясы салыстырмалы бұрыштарды анықтау үшін векторлық көбейтіндінің таңбасын пайдалана алады. Егер бірнеше нүктелер бірдей бұрышқа ие болса, қашықтық бойынша түйіндіктерді шешіңіз (оңай есептеу үшін Евклидтік қашықтықтың орнына Манхэттен немесе Чебышев қашықтығын қолдануға болады, себебі нүктелер бір түзу бойында жатыр) немесе ең алыс нүктеден басқа барлық нүктелерді жойыңыз. Алгоритм реттелген массивтегі әр нүктені бірінен кейін бірі қарастыру арқылы жүзеге асырылады. Әр нүкте үшін, осы нүктеден бірден бұрынғы екі нүктеден қозғалыс солға немесе оңға бұрылуды білдіретінін анықтау керек. Егер оңға бұрылса, екінші соңғы нүкте дөңгелек қабықшаның бөлігі емес, оның ішінде жатыр. Содан кейін, соңғы нүкте мен қабықшаның ішінде деп табылған нүктеден бұрынғы екі нүкте үшін де осы тексеру жасалады және «солға бұрылу» жиынтығы кездескенше қайталанады. Осы кезде алгоритм реттелген массивтегі келесі нүктеге көшеді, ал қабықшаның ішінде деп табылған нүктелерді ескермейді; оларды қайта қарастырудың қажеті жоқ. (Егер үш нүкте бір түзу бойында болса, оларды жоюды немесе туралы хабарлауды таңдауға болады, себебі кейбір қолданбаларда дөңгелек қабықшаның шекарасындағы барлық нүктелерді табу қажет.) Тағы да, үш нүкте «солға бұрылу» немесе «оңға бұрылу» құрайтынын анықтау үшін екі түзу кесіндісі арасындағы нақты бұрышты есептеудің қажеті жоқ, оны қарапайым арифметикалық амалдармен анықтауға болады. Үш нүкте үшін A, B және C, екі вектордың векторлық көбейтіндісінің z координатын есептеңіз: (B - A) x (C - A). Егер нәтиже 0 болса, нүктелер бір түзу бойында жатыр; егер оң болса, үш нүкте «солға бұрылу» немесе сағат тіліне қарсы бағытта, әйтпесе «оңға бұрылу» немесе сағат тілімен бағытта (сағат тіліне қарсы нөмірленген нүктелер үшін). Бұл процесс бастапқы нүктеге қайта оралады, осы кезде алгоритм аяқталады және стек дөңгелек қабықшадағы нүктелерді сағат тіліне қарсы тәртіппен қамтиды.

The first step in this algorithm is to find the point with the lowest y coordinate. If the lowest y coordinate exists in more than one point in the set, the point with the lowest x coordinate out of the candidates should be chosen. Call this point P. This step takes O(n), where n is the number of points in question. Next, the set of points must be sorted in increasing order of the angle they and the point P make with the x axis. Any general purpose sorting algorithm is appropriate for this, for example heapsort (which is O(n log n)). Sorting in order of angle does not require computing the angle. It is possible to use any function of the angle which is monotonic in the interval The cosine is easily computed using the dot product, or the slope of the line may be used. If numeric precision is at stake, the comparison function used by the sorting algorithm can use the sign of the cross product to determine relative angles. If several points are of the same angle, either break ties by increasing distance (Manhattan or Chebyshev distance may be used instead of Euclidean for easier computation, since the points lie on the same ray), or delete all but the furthest point. The algorithm proceeds by considering each of the points in the sorted array in sequence. For each point, it is first determined whether traveling from the two points immediately preceding this point constitutes making a left turn or a right turn. If a right turn, the second to last point is not part of the convex hull, and lies 'inside' it. The same determination is then made for the set of the latest point and the two points that immediately precede the point found to have been inside the hull, and is repeated until a "left turn" set is encountered, at which point the algorithm moves on to the next point in the set of points in the sorted array minus any points that were found to be inside the hull; there is no need to consider these points again. (If at any stage the three points are collinear, one may opt either to discard or to report it, since in some applications it is required to find all points on the boundary of the convex hull.) Again, determining whether three points constitute a "left turn" or a "right turn" does not require computing the actual angle between the two line segments, and can actually be achieved with simple arithmetic only. For three points , and , compute the z coordinate of the cross product of the two vectors and , which is given by the expression If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn" or counter clockwise orientation, otherwise a "right turn" or clockwise orientation (for counter clockwise numbered points). This process will eventually return to the point at which it started, at which point the algorithm is completed and the stack now contains the points on the convex hull in counterclockwise order.

Сандық беріктігі

Сандық беріктік – шекті дәлдігі бар қозғалмалы нүктелі компьютерлік арифметиканы қолданатын алгоритмдерде туындайтын мәселе. 2004 жылғы мақалада қарапайым инкременттік стратегия талданды, оны, атап айтқанда, Грэм сканерін іске асыру үшін пайдалануға болады. Кейін Д. Цзян және Н. Ф. Стюарт осы мәселені терең зерттеп, кері қателік талдауын қолданып, екі маңызды қорытынды жасады. Біріншісі – дөңес қабықша жақсы жағдайланған мәселе, сондықтан нәтиже ақылға қонымды қателік шегінде болатын алгоритмдерді күтуге болады. Екіншісі, олар Грэм сканерінің өзгертілген нұсқасын, оны Грэм Фортуна деп атады (Стивен Фортунаның сандық тұрақтылыққа қатысты идеяларын енгізе отырып), шекті дәлдік пен нақты емес деректердің тудыратын қиындықтарды "мүмкін болатын шекте" шеше алады.