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

问题描述

我在寻找一种算法来解决这个问题：

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

给定N个矩形的坐标，找出如果这些矩形的交集为空。每个矩形可以躺在任何方向

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.的单峰来完成（这是一部分，我完全不记得了。）对L从D一侧取出所有的顶点，并插入交叉点到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.

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