N个矩形的交点

观察1：给定多边形A和矩形B，可以通过与对应于B的每个边的半平面的4个相交来计算相交A∩B。

观察2：从凸多边形上切一个半平面会得到一个凸多边形。第一个矩形是凸多边形。此 *** 作最多增加每1个顶点的数量。

观察3：凸多边形的顶点到直线的符号距离是单峰函数。

这是算法的草图：

以CCW顺序将当前部分交集D保持在平衡的二叉树中。

切割由直线L定义的半平面时，找到D中与L相交的两个边。这可以通过对数时间，通过一些巧妙的二元或三元搜索，利用到L的有符号距离的单峰性来完成。我不完全记得。）从D移除L一侧的所有顶点，并将交点插入D。

对所有矩形的所有边L重复。