Отсечение полигона выпуклым окном

Отсекается последовательно по границам выпуклого окна. Сначала отсекаются все отрезки полигона, затем, точки пересечения сортируются вдоль границы окна и из их последовательных пар формируются дополнительные ребра полигона. Существуют особые случаи, когда вершины ребер лежат на границе окна, ребра, обе вершины которых лежат на границе окна следует отбрасывать, а если у ребра одна вершина лежит на границе (другая внутри), считать ее точкой пересечения. Нужно заметить, что точки пересечения делятся на входящие (в окно) и выходящие (из окна). Входящие – P2 внутри окна, выходящие – P1 внутри окна. Дополнительные ребра должны всегда идти от выходящей точки к входящей, это правило позволит сохранить правильное направление ребер в полигоне и избежать петель.

При отсечении выпуклого полигона точек пересечение всегда две (или ни одной), поэтому никакой сортировки не нужно, просто соединить выходящую точку с входящей.