15.7. БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ
В монографии [1.4] описан алгоритм разрезания произвольного правильного прямоугольника с помощью произвольной прямой, в котором используется рекурсивное разбиение многоугольника на меньшие многоугольники В статье [15.4] проведено подробное рассмотрение алгоритма 15.3 и некоторых связанных с ним проблем. В статье [15.5] обсуждается общая задача преобразования многоугольников: разделение многоугольника на части, объединение двух пересекающихся многоугольников и т. д. Такие задачи, естественно, можно решать без особых затруднений, произведя соответствующие изменения в алгоритме разрезания, однако отсутствие правильного метода, позволяющего избежать многократного просмотра отдельных частей многоугольника, может привести к избыточным вычислениям.
Использование разбиения многоугольника на выпуклые компоненты при решении задач распознавания образов рассмотрено в монографии [37].
Теорема 15.1 представляет собой перефразировку теоремы, сформулированной Добкиным и Липтоном [15.2]. Второй из эффективных алгоритмов определения пересечения многоугольников предложен Шамосом [15.3]. Хотя этот и другие аналогичные ему
алгоритмы обладают асимптотически (при стремлении числа вершин многоугольника и бесконечности) более высоким быстродействием, чем алгоритмы, описанные в (нашей книге, возможность их непосредственного использования в машинной графике и распознавании образов вызывает определенные сомнения по причинам, приведенным в разд. 15.6 Кроме того, многоугольники со значительным числом вершин (скажем, больше 10), которые встречаются в задачах машинной графики, обычно не являются выпуклыми Таким образом, асимптотические эффективные алгоритмы для решения задачи пересечения многоугольников имеют значение для машинной графики лишь в случае, если они пригодны для работы с невыпуклыми многоугольниками С другой стороны, использование предварительной сортировки и описанных прямоугольников может оказаться целесообразным в задачах на пересечение очень большого числа многоугольников При решении таких задач можно воспользоваться простым методом типа алгоритма 15.3 для определения истинного пересечения, а асимптотически эффективный алгоритм следует использовать для уменьшения числа рассматриваемых многоугольников Методы, обнаруживающие, а не вычисляющие пересечения, изложены в докладе [151].
15.8. ЗАДАЧИ
(см. скан)
