相关疑难解决方法(0)

我有N个矩形,其边与x轴和y轴平行.还有另一个矩形模型.我需要创建一个算法来判断模型是否被N个矩形完全覆盖.

我有一些想法.我认为首先,我需要通过左侧对矩形进行排序(可以在O(n log n)时间内完成),然后使用垂直扫描线.

+------------------------------------------------------------> x
|O
|                  +----+
|   +---------+    |    |
|   |        ++----+--+ |
|   |      +-++----+-+| |
|   |      | |     +-++-+
|   +------+ +-------++
|          +---------+
|
|
|
|y

蓝色矩形是模型.

首先,我需要抽象算法.对于实现没有特殊要求.矩形可以表示为一对点(左上角和右下角).

这是准备测试的任务之一.我知道最好的算法可以在O(n log n)时间内完成.

我的数学功能让我失望!我需要一种将网络范围减少到超集的有效方法,例如,如果我输入IP范围列表:

• 1.1.1.1至2.2.2.5
• 1.1.1.2至2.2.2.4
• 10.5.5.5至155.5.5.5
• 10.5.5.6至10.5.5.7

我想返回以下范围:

• 1.1.1.1至2.2.2.5
• 10.5.5.5至155.5.5.5

注意:输入列表没有排序(虽然它们可能是？).执行此操作的简单方法是检查列表中的每个范围,以查看输入范围x是否为子集,如果是,则不插入范围x.但是,无论何时插入新范围,它都可能是现有范围的超集,因此您必须检查现有范围以查看它们是否可以折叠(例如,从我的列表中删除).

编辑:

简单的代码我用来解决问题以防任何人感兴趣(感谢Fredrik):

    int windowOverlap(Rectangle rect1, Rectangle rect2)
    {
        if (rect1.IntersectsWith(rect2))
        {
            Rectangle overlap = Rectangle.Intersect(rect1, rect2);
            if (overlap.IsEmpty)
                return overlap.Width * overlap.Height;
        }

        return 0;
    }

原始问题:

我想知道一种快速而又脏的方法来检查两个矩形是否重叠,以及它们是否确实计算了重叠区域.为了好奇,我对以下情况感兴趣:1)两个矩形中的所有线条都是垂直的或水平的,或2)任何两个矩形的一般情况,但我真正需要的唯一答案是案例1.

我在想:

double areaOfOverlap( Rect A, Rect B)
{
    if ( A.Intersects(B) )
    {
        // calculate area
        // return area
    }

    return 0;
}

对于A.Intersects(),我考虑使用分离轴测试,但如果矩形只有水平和垂直线,那么还有更简单(更快)的检查方法吗？

如果矩形只有水平和垂直线,那么计算它们相交的区域有一个快速的方法吗？

最后,这与这个问题无关,但我很感激有人可能会在一本好书/网页上提出任何建议,我可以在那里查看计算机图形学的数学知识.我已经离开大学一段时间了,觉得我忘记了一切:)!其他人有这个问题吗？

(注意:我发现这个问题与此不同,这似乎更复杂,并没有直接回答这个问题.)

当一位朋友谈到编程竞赛时,我们想到了最好的方法:

给定一个点列表,找到覆盖最多点的预定大小的圆的中心.如果有几个这样的圈子,唯一重要的是找到其中一个.

示例输入:1000点,500x500空间和60直径的圆.

我写了一个绘图功能,绘制各种屏幕上的精灵.这些精灵只能重叠到一个点.如果它们有很多重叠,它们会变得太模糊.因此,我需要检测这些精灵何时重叠太多.幸运的是,问题被简化,因为精灵可以被视为正交矩形.我想知道这些矩形重叠多少.现在,我只是通过测试一个矩形中的每个像素来强制它,以查看另一个矩形是否包含它.我计算这些并计算重叠百分比.我认为这可能是一种更好,更少蛮力的方法.我可以使用什么算法来确定这个？

我正在使用wxwidgets.

我有一个长方体列表，由它们的左下后角和右上角前角的坐标定义，边缘平行于轴。坐标是双精度值。这些长方体密集，会与一个或多个其他长方体重叠，甚至完全包含其他长方体。

我需要计算所有给定长方体所包含的总体积。重叠（甚至多次）的区域应该只计算一次。

例如，卷：

1. ((0,0,0)(3,3,3))
2. ((0,1,0) (2,2,4))
3. ((1,0,1) (2,5,2))
4. ((6,6,6)(8,8,8))

总体积为 27 + 1 + 2 + 8 = 38。有没有一种简单的方法可以做到这一点（在 O(n^3) 时间内或更好？）？

我正在寻找一种方法来检查矩形的集合(Java TreeSet) - 由一个"可比较的"Java类实现,使用google guavas Range for x和y range - 用于交叉点和孔.我知道一个选项可能是使用kd树,但我不知道如何构建这样一个kd树(对于矩形它应该是4d,不应该吗？)以及如何解决问题(交集,孔).

排序优先考虑y轴上的x轴.

编辑:(尝试重述问题):用例是创建任意表(由2或3个矩形块"header","pre column","data"组成).我必须保证每个块中没有交叉点和孔(即由无效的html或其他表数据源提供)(除此之外,块必须组合在一起).目前(刚刚得到一个想法)我试图保存位置(x,y)被占用的二维数组.最后,所有位置必须恰好占用一次.