我正在寻找一种解决此问题的算法：
给定N个直角坐标上的矩形，请找出这些矩形的交点是否为空。每个矩形可以位于任何方向（不必使其边缘平行于Ox和Oy）
您对解决这个问题有什么建议吗？:)我可以考虑测试每个矩形对的交点。但是，它是O（N * N）并且非常慢:(
观察1：给定多边形A和矩形B，可以通过与对应于B的每个边的半平面的4个相交来计算相交A∩B。
观察2：从凸多边形上切一个半平面会得到一个凸多边形。第一个矩形是凸多边形。此操作最多增加每1个顶点的数量。
观察3：凸多边形的顶点到直线的符号距离是单峰函数。
这是算法的草图：
以CCW顺序将当前部分交集D保持在平衡的二叉树中。
切割由直线L定义的半平面时，找到D中与L相交的两个边。这可以通过对数时间，通过一些巧妙的二元或三元搜索，利用到L的有符号距离的单峰性来完成。我不完全记得。）从D移除L一侧的所有顶点，并将交点插入D。
对所有矩形的所有边L重复。
