Алгоритм - вычисление - пары - видимость
Cтраница 1
Алгоритм вычисления пар видимости, приведенный в разд. Как будет показано в разд. [1]
 |
Порядок четырех углов области видимости, показанной на рисунке, позволяет утверждать о том, что эта область не является простым многоугольником. [2] |
Если алгоритм вычисления пар видимости успешно завершает свою работу на обоих многоугольниках Р и Q, то объявляется, что многоугольник Р простой. [3]
Вследствие успешности завершения алгоритма вычисления пар видимости также известно, что области, входящие в Q, могут быть склеены друг с другом по горизонтальным отрезкам, определяющим пары видимости. [4]
Это с учетом оценки сложности алгоритма вычисления пар видимости и дает суммарную оценку О ( п log log n ] сложности алгоритма триангуляции простого многоугольника. [5]
Теперь мы готовы к обсуждению самого алгоритма вычисления пар видимости. Входными данными для алгоритма служит описание одной области видимости V. Чтобы алгоритм можно было применить к исходному многоугольнику, мы преобразуем этот многоугольник в область видимости, разбив его границу на два боковых граничных сегмента, концевыми вершинами которых являются вершины исходного многоугольника с минимальной и максимальной / - координатой; / - координаты этих двух вершин выбираются в качестве значений г / min и Утах для получаемой таким образом области. Приводимый ниже алгоритм аналогичен алгоритму из разд. [6]
Неоднородные деревья поиска с указателями используются в алгоритме вычисления пар видимости для представления частей границ областей. Термин неоднородный указывает на тот факт, что указатели структуры обеспечивают особо эффективный доступ к некоторым частям структуры, а именно к двум ее концам. В противоположность этому однородные деревья поиска с указателями обеспечивают быстрый доступ в окрестность любого элемента. Однородное дерево поиска с указателями получается из красно-черного дерева путем добавления новых указателей. А именно, каждая вершина содержит указатели на двух своих сыновей и на родительскую вершину. Эти дополнительные указатели называются ссылками по уровню. [7]
Последнее, что необходимо обсудить, прежде чем перейти к описанию алгоритма вычисления пар видимости, это понятие особой пары и действие процедуры корректировки ( refine); они влияют на выполнение алгоритма жордановой сортировки с исправлением ошибок. Пара точек пересечения dV с L называется особой, если одна из них является первой, а другая - последней точками пересечения некоторой Г - границы ( в порядке следования вдоль dV), иначе пара называется нормальной. [9]
Теперь рассмотрим, какие операции над структурами данных, представляющими границы областей, требуется выполнить на каждом шаге алгоритма вычисления пар видимости, использующего стратегию сбалансированного разбиения. [11]
Хотя алгоритм жордановой сортировки с исправлением ошибок и обнаруживает в некоторых случаях, что многоугольник не является простым, столкнувшись с неподдающимися корректировке пересечениями или нарушениями свойства пустоты, однако успешное завершение алгоритма вычисления пар видимости не доказывает, что он действительно прост. [13]
 |
Образование подобластей. На верхнем и нижнем деревьях выделены семьи вершин дерева, соответствующих подобластям. Трапеции, отмеченные на рисунке цифрой 0, полностью игнорируются. [14] |
Более того, области видимости, отсекаемые в результате такой замены и, следовательно, игнорируемые алгоритмом при обработке, представляют собой трапеции. Эффективность алгоритма вычисления пар видимости достигается за счет того, что он избегает каких-либо вычислений, связанных с такими тривиальными областями видимости. Рассмотрим теперь, как определяются значения ут п и z / max для получаемых подобластей. [15]
Страницы: 1 2