我在找一个算法来解决这个问题：
给定笛卡尔坐标上的n个矩形，找出这些矩形的交集是否为空。每个矩形可以位于任何方向（不必使其边缘与ox和oy平行）
你有什么解决这个问题的建议吗？：）我可以考虑测试每个矩形对的交集。但是，它是o（n*n）并且非常慢：（
最佳答案
观察1：给定一个多边形A和一个矩形B，可以通过4个与B的每个边对应的半平面相交来计算交点A B。
观察2：从一个凸多边形上切下一个半平面会得到一个凸多边形。第一个矩形是凸多边形。此操作最多每1个顶点增加一个顶点。
观察3：凸多边形顶点到直线的有符号距离是单峰函数。
下面是算法的示意图：
在平衡二叉树中保持当前部分交集d的ccw顺序。
当切割一条线L定义的半平面时，在D中找到与L相交的两条边。这可以在对数时间内通过一些巧妙的二元或三元搜索，利用到L的有符号距离的单峰（这是我不记得的部分）来完成。从D中删除L一侧的所有顶点，并将交点插入到D。
对所有矩形的所有边l重复此操作。
关于algorithm - N个矩形的交点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5880558/