直线多边形交叉

Question

我正在寻找/尝试开发一种与矩形的直线多边形交叉的最佳算法.我正在测试的多边形没有洞.

像这里和这里给出的答案是非常一般的多边形,解决方案可以理解的非常复杂.

希望SO社区可以帮助我记录具有直线多边形的特殊情况的算法.

我正在寻找下图中填充绿色的多边形:

Answer 1

Preparata 和 Shamos 所著的《计算几何：简介》一书有一章介绍直线多边形。