Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Киркпатрика - Реализация

1. Найдём некоторую внутреннюю точку A многоугольника P1. Такая точка А будет внутренней точкой CH.
2. Возможно два случая:
   1. Точка A не является внутренней точкой многоугольника P2. Проводим две опорные прямые для многоугольника P1, проходящие через точку А. Эти опорные прямые проходят через вершины В и С многоугольника P2.Все точки внутри треугольника АВС не принадлежат границе выпуклой оболочки CH. Все остальные точки упорядочиваем по полярному углу относительно центра А, слиянием двух упорядоченных списков вершин за время O + O = O, а затем применяем к полученному списку метод обхода Грэхема, требующий лишь линейное время. Опорные прямые к многоугольнику P2 могут быть построены исходя из следующих соображений. Прямая АP_i, где P_i — некоторая вершина многоугольника P2, является опорной к P2 в том и только в том случае, если ребра и лежат в одной полуплоскости, ограниченной этой прямой. Нетрудно видеть, что для построения опорных прямых AB и AC требуется в худшем случае один обход вершин многоугольника P2, то есть время O.
   2. Точка А является внутренней точкой многоугольника P2 . Упорядочиваем вершины обоих многоугольников относительно центра А, сливая два упорядоченных списка вершин P1 и P2 за O.
3. Теперь к полученному списку вершин можно применить метод обхода Грэхема, который выполняется за линейное время. Теперь получена выпуклая оболочка объединения выпуклых многоугольников P1P2.