N 个矩形的交集 [英] Intersection of N rectangles

问题描述

我正在寻找解决这个问题的算法:

I'm looking for an algorithm to solve this problem:

给定笛卡尔坐标上的 N 个矩形，找出这些矩形的交点是否为空.每个矩形可以位于任何方向(不必使其边缘平行于 Ox 和 Oy)

Given N rectangles on the Cartesian coordinate, find out if the intersection of those rectangles is empty or not. Each rectangle can lie in any direction (not necessary to have its edges parallel to Ox and Oy)

您对解决这个问题有什么建议吗?:) 我可以考虑测试每个矩形对的交集.但是，它是 O(N*N) 并且非常慢:(

Do you have any suggestion to solve this problem? :) I can think of testing the intersection of each rectangle pair. However, it's O(N*N) and quite slow :(

推荐答案

观察1:给定一个多边形A和一个矩形B，交点A∩B可以用4个半平面的交点计算出B的每条边对应的半平面.

Observation 1: given a polygon A and a rectangle B, the intersection A ∩ B can be computed by 4 intersection with half-planes corresponding to each edge of B.

观察 2:从凸多边形切割半平面会得到一个凸多边形.第一个矩形是凸多边形.这个操作最多每增加1个顶点数.

Observation 2: cutting a half plane from a convex polygon gives you a convex polygon. The first rectangle is a convex polygon. This operation increases the number of vertices at most per 1.

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

Observation 3: the signed distance of the vertices of a convex polygon to a straight line is a unimodal function.

这是算法的草图:

在平衡二叉树中按逆时针顺序维护当前部分交集D.

Maintain the current partial intersection D in a balanced binary tree in a CCW order.

当切割由线 L 定义的半平面时，找到 D 中与 L 相交的两条边.这可以通过一些巧妙的二元或三元搜索在对数时间内完成，该搜索利用到 L 的有符号距离的单峰性.(这是我不太记得的部分.)从D中删除L一侧的所有顶点，并将交点插入D.

When cutting a half-plane defined by a line L, find the two edges in D that intersect L. This can be done in logarithmic time through some clever binary or ternary search exploiting the unimodality of the signed distance to L. (This is the part I don't exactly remember.) Remove all the vertices on the one side of L from D, and insert the intersection points to D.

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

Repeat for all edges L of all rectangles.

这篇关于N 个矩形的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！