15.5. ПЕРЕСЕЧЕНИЕ ДВУХ МНОГОУГОЛЬНИКОВ

Определение пересечения двух многоугольников представляет существенный интерес для решения проблемы разделения видимых и невидимых элементов воспроизводимого объекта и является наиболее общей постановкой задачи разрезания. Задачу определения пересечения двух многоугольников можно решить при помощи многократного применения алгоритма 15.3. Рассмотрим многоугольники причем будем считать, что многоугольник — выпуклый. Возможно следующее решение поставленной задачи. Пусть — стороны многоугольника — вершины многоугольника который может быть как выпуклым, так и невыпуклым. Воспользуемся алгоритмом 15.3 для определения разрезания многоугольника каждой стороной многоугольника . В результате разрезания стороной возникнут новые многоугольники, число которых может изменяться от 0 до увеличенного на 1 числа вогнутых вершин Поскольку число получающихся многоугольников может оказываться довольно значительным, при решении этой задачи должен быть налажен тщательнейший учет.

Для описания и всех остальных многоугольников, которые могут возникнуть в процессе разрезания, лучше всего использовать связный список. В частности, каждой вершине ставится в соответствие указатель, который при обходе многочлена по часовой стрелке указывает следующую вершину. Для обозначения указателя будет применяться символ Вначале при Перейдем теперь к модификации алгоритма 15.3. Вместо проведения сторон многоугольников будут просто корректироваться соответствующие указатели. В частности, на шаге 6 в список вводится точка пересечения и устанавливается где — число, обозначающее позицию новой точки в конце списка. На шаге 7 устанавливается поскольку следующая точка пока не известна. Если вершина невидима, то ее указателю также присваивается значение

0. Элементы этой процедуры иллюстрируются на рис. 15.4, где стрелками отмечены результаты использования указателей. Для придания процедуре законченности необходимо задать указатели для связывания точек пересечения. Для этого точки сортируются в порядке увеличения значений координаты у или х, если режущая прямая горизонтальна. Затем эти точки берутся попарно и указателем с нулевыми значениями присваиваются значения адресов вторых элементов соответствующей пары. Так, в случае, приведенном на рис. 15.4, вводятся две связи:

Рис. 15.4. Иллюстрация к расстановке указателей при разрезании произвольного многоугольника произвольной прямой

Теперь совсем нетрудно обойти описок вершин и найти новые многоугольники. На самом деле, эту процедуру не требуется доводить до конца, поскольку при использовании алгоритма 15.3 фактически не имеет значения число многоугольников. Вероятно, наилучшим способом обхода списка вершин является использование еще одного набора указателей, содержащих адрес в списке одной точки каждого многоугольника. Этот набор следует просматривать последовательно, используя каждый очередной указатель как предписание полного обхода контура соответствующего многоугольника.

Описанная выше процедура предназначена для определения пересечения двух многоугольников посредством нахождения пересечений многоугольника полуплоскостями Ни заданными сторонами многоугольника (Прямая, содержащая сторону делит плоскость на две части. Полуплоскость представляет собой ту часть плоскости, которая содержит точки, расположенные внутри многоугольника в окрестности стороны Если — невыпуклый, то этот метод приводит к определению пересечения не с а с пересечением полуплоскостей Последнее называют центром или ядром многоугольника Оно представляет собой выпуклый многоугольник, обладающий тем свойством, что прямая, проведенная из любой его точки в любую вершину многоугольника полностью лежит в последнем. (Естественно, может оказаться, что ядро является пустым множеством.) Рассмотрение ядер и их свойств выходит за пределы задач нашей книги (см. разд. 15.7).

С другой стороны, алгоритм 15.3 можно использовать для разбиения невыпуклого многоугольника на выпуклые. Рассмотрим, в частности, многоугольник П, один из вогнутых углов которого образован сторонами Разрезание многоугольника сначала стороной а затем стороной приводит к возникновению двух многоугольников: В каждом из них число вогнутых углов хотя бы на единицу меньше, чем в многоугольнике П. Повторив эту процедуру для всех сторон, образующих вогнутые углы, получим набор многочленов, объединение которых равно П. Эти многоугольники можно разрезать, используя стороны, образующие их вогнутые углы, и так далее, вплоть до тех пор, пока все полученные многочлены не окажутся выпуклыми (см. задачи 15.6, 15.7).

Вместо разбиения многоугольника на выпуклые многоугольники можно следующим образом изменить способ использования алгоритма 15.3. Каждая сторона используется для разрезания исходного а не многоугольников, возникших в результате предыдущих разрезов. В конце процедуры точки пересечения, расположенные на сторонах группируются таким образом, чтобы было построено пересечение многоугольников. Исчерпывающий анализ этого метода выходит за пределы задач нашей книги, причем не только из-за ее сложности, но и потому, что в большинстве прикладных задач машинной графики многоугольник либо

соответствует наблюдаемому фрагменту изображения (некоторый правильный прямоугольник), либо является проекцией треугольника или четырехугольника (см. гл. 17).