相交的矩形快速隐藏 [英] Fast hiding of intersecting rectangles

问题描述

我工作的一个有效的算法相交矩形的隐藏所有对奠定了在2D一组 N 矩形（轴线对齐）。 所有的矩形具有相同的宽度和高度。

I'm working on an efficient algorithm to "hide" all the pairs of intersecting rectangles laid out in 2D in a set of N rectangles (axis aligned). All the rectangles have the same width and height.

假设我的出发矩形集合在2D布局是 R = {R_1，R_2，...，r_n} 其中， R_I 都是矩形， R_I 具有布尔属性可见。

Suppose my starting set of rectangles laid out in 2D is R={r_1,r_2,...,r_n} where r_i are all the rectangles, r_i has the boolean attribute visible.

我想找到R的子集S，使得对于每一个 R_I ， r_j 属于向S R_I，_r_j 不相交。

I want to find the subset S of R such that for every r_i, r_j belonging to S r_i,_r_j don't intersect.

第一个平凡的解决方案是蛮力，极大独立集的方法。 首先，我遍历 N（N-1）/ 2 矩形（一个给定的矩形不与自身相交），并检查他们是否相交与否。同时地我也把所有的矩形中集研究作为图的节点 G =（V，E） 。边在该图是由重相交三角形的对psented $ P $。

A first trivial solution is the brute force-maximal independent set approach. First I iterate over N(N-1)/2 rectangles (a given rectangle doesn't intersect with itself) and check if they intersects or not. Contemporaneously I also put all the rectangles in the set R as the nodes of a graph G=(V,E). Edges in that graphs are represented by the pairs of intersecting triangles.

该组非相交的矩形是那么的 1个极大独立集图形。

The set of non intersecting rectangles is then one maximal independent set of the graph.

我觉得这不是最快的方法，但正确的。我读过的，例如如何通过它们的X-提前矩形的列表排序协调会加快相交的矩形对到 O（n日志（N））（而不是蛮力为O（n ^ 2）。

I think this is not the fastest approach, although correct. I've read in some discussion for example how sorting in advance the list of rectangles by their x coordinate would speed up the computation of intersecting rectangle pairs to O(nlog(n) ) (rather than brute force O(n^2).

现在我要问，这样做的人知道这种问题的一个更好的算法（无论是在一组矩形，并为那些矩形的过滤交叉对的计算？）

Now I'm asking, do someone know a better algorithms for such problem (both for the computation of intersecting pairs in a set of rectangles and for the filtering of those rectangles?)

重新制定的问题，SAT问题，也可以是有趣的，但这个想法刚走到我的脑海里。这个问题将在这里找到可见属性，不可见矩形相交另外一个置换。

Reformulating the problem as SAT problem can also be interesting, although this idea just came up to my mind. The problem would be here to find that permutation of visible attributes such that no visible rectangle intersects another one.

推荐答案

是的，你应该矩形用x排序。
由于您的矩形在同一x轴的高度相同，之后你对它们进行排序，你应该能够找到线性时间的交集。你要找的算法称为扫描线。

Yes you should sort the rectangles by x.
Since your rectangles are on the same x axis and are the same height, after you sort them, you should be able to find the intersection in linear time. The algorithm you're looking for is called scan line.

您移动扫描线在所有的矩形（跳跃从它们的X COORDS在设置你只是排序），看看哪些在当前x位置相交。加载所有的X坐标重叠的矩形变成一个数据结构，并检查它们相交（基于y坐标）。

You move a scan line over all your rectangles (jump from their x coords in the set you just sorted) and see which ones intersect at current x location. Load all the x coord overlapping rectangles into a datastructure and check if they intersect (based on y coord).

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