Этот процесс легко изобразить геометрически: движемся вдоль SUBJ, отрезок за отрезком, до момента пересечения (точка 2 в примере). Теперь имеет смысл прекратить движение по SUBJ и вместо этого перейти к обходу CLIP. Существует два способа перехода на отсекаемый полигон. Во-первых, можно повернуться так, что CLIP будет обходиться в своем прямом направлении. При этом внутренние части обоих полигонов SUBJ и CLIP будут оставаться справа. Матем, найдя пересечение, снова повернемся и проследуем вдоль SUBJ в его прямом направлении и т. д. Каждая обнаруженная вершина или точка пересечения вносится в список вывода. Повторим процесс «повернуть и перескочить на другой полигон», обходя каждый из полигонов в его прямом направлении, до тех пор, пока не придем снова к первой вершине. В этот момент список вывода состоит из (1, Ъ, 2, В).
Теперь проверим, нет ли еще каких-либо пересечений с полигоном SUBJ. Обнаружена точка 3, и этот процесс повторяется, в результате чего составляется следующий список вывода: (3,4,5,6). Дальнейшие проверки пересечений показывают, что все они уже встречались, поэтому процесс отсечения прерывается,
4.10. Тематические задания и в результате остаются два полигона (1, Ь, 2, В) и (3,4,5,6). Систематизированный способ реализации процесса «следуй прямо и перескакивай» состоит в том, чтобы путем обхода каждого из полигонов (так, чтобы его внутренняя часть была справа) и попутной записи вершин и точек пересечения (в том порядке, в которым они обнаружены) создать следующие два списка: БиЩЬЮТ: а, 1, Ь, 2, с, 3,4, й, 5,6, СЫРПЗТ: А, 6,3, 2, В, 1, С, Д 4,5.
(Как будут выглядеть эти списки, если между двумя полигонами не будет обнаружено пересечений?) Таким образом, обход полигонов равносилен просматриванию списка, а перескакивание на другой полигон равносильно переходу к другому списку.
Отметим, что когда составлены эти списки, в процессе остается очень мало геометрии - только тест «находится ли точка вне полигона?», чтобы правильно идентифицировать входящую в список вершину. Правильное направление, в котором нужно обходить каждый полигон, задается порядком следования элементов его списка. Ход выполнения этого алгоритма показан применительно к вышеприведенному примеру на рис. 4.56.