Алгоритм Вейлера-Азертона. Это алгоритм отсечения полигона произвольным окном, можно сказать отсечение одного полигона другим

Это алгоритм отсечения полигона произвольным окном, можно сказать отсечение одного полигона другим. Сначала находятся все точки пересечения ребер полигонов. Они делятся на входящие (в окно) и выходящие (относительно границ окна). Эти точки разделяют ребра окна и полигона на несколько ребер. Затем, начиная с одной из точек пересечения последовательно заносим ребра в новый полигон. Если это точка входа – берутся ребра с полигона, иначе - с окна. Если встречается точка пересечения – происходит переключение полигона, с которого берутся ребра (точки всегда чередуются). Так происходит до тех пор, пока не встретится точка, с которой был начат обход. Т.к. внутренних контуров может быть несколько, то следует проверить, все ли точки пересечения были пройдены, и если не все, то может понадобится несколько таких циклов.

К особым случаям следует отнести контура (как полигона, так и окна), не содержащие точек пересечения. В таких случаях проверяют положение этих контуров относительно другого полигона (проверка положения вершины контура относительно полигона). Например, если внешний контур полигона вне окна и внешний контур окна вне полигона – очевидно общий полигон будет пустым. Если внутренний контур окна внутри полигона – его нужно добавить к внутренним контурам. Если внутренний контур полигона вне окна – его нужно полностью выбросить. Кроме этого может быть еще несколько вариантов.