问题标签 [rectangles]

我目前的计划是通过子类化 NSView 来绘制矩形，但这对于我正在尝试做的事情来说似乎是一种非常低效的方式，即绘制一堆固定的、不重叠的矩形，它们会不时改变颜色。有没有更好的办法？谢谢。

给定一组 N 维整数点，我如何找到最小的 N 维长方体集（二维情况下的矩形），使得整数点在整数点集中当且仅当它包含在一个或多个长方体/矩形。整数点是指具有整数坐标的点。

例如，给定点 (1,0), (2, 0) 和 (3,1), (4,1) 最小的矩形集是 (1,0-2,0),(3,1-4, 1)，见下图：

显然我可以进行蛮力搜索，但我正在寻找一种更有效的算法，即使它仍然具有很高的复杂性。

我知道这是更多的高中数学（哇，我在那里已经很久了）但我正在尝试以编程方式解决这个问题，所以我正在接触 stackoverflow 的集体知识

鉴于此布局：

中点是我的参考点，在一个数组中我有所有其他点的向量点（P）

我可以通过将浅蓝色区域分成四个象限并进行蹩脚的冒泡排序来找到每个象限中的最大（y）或最低（x）值，从而达到这种状态。

我只需要找到外边界完全达到红色没有空白的象限。例如，左下角和右上角没有任何空白区域击中浅蓝色矩形。

我确信我的术语在这里都没有了，我不是在寻找任何特定的代码，但是如果有人可以为我指出一个更优化的解决方案来解决这个问题或者我已经拥有的下一步。

谢谢

我正在尝试计算旋转矩形（2D）的顶点。

如果矩形没有被旋转，这很容易，我想出了那部分。

如果矩形已经旋转，我想到了两种可能的方法来计算顶点。

1. 弄清楚如何将顶点从本地/对象/模型空间（我在下面找到的）转换到世界空间。老实说，我不知道，如果这是最好的方法，那么我觉得如果我能弄清楚的话，我会从中学到很多东西。

2. 使用 trig 以某种方式确定矩形的端点相对于矩形在世界空间中的位置。到目前为止，这一直是我一直在尝试的方式，我只是还没弄清楚怎么做。

这是迄今为止计算顶点的函数，感谢您的帮助

我有一个动态数量的等比例和大小的矩形对象，我想在屏幕上以最佳方式显示。我可以调整对象的大小，但需要保持比例。

我知道屏幕尺寸是多少。

如何计算将屏幕划分为所需的最佳行数和列数以及将对象缩放到什么大小？

谢谢，

杰米。

编辑：

如果有人感兴趣，我用来解决问题的简单代码（感谢 Fredrik）：

原始问题：

我想知道一种快速而肮脏的方法来检查两个矩形是否重叠以及它们是否计算重叠区域。出于好奇，我对以下情况感兴趣：1）两个矩形中的所有线都是垂直或水平的，或者 2）任何两个矩形的一般情况，但我真正需要的唯一答案是情况 1。

我的思路是这样的：

对于 A.Intersects() 我正在考虑使用分离轴测试，但是如果矩形只有水平线和垂直线，是否有更简单（更快）的检查方法？

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

最后，这与问题无关，但我很感激有人在一本好书/网页上提出的任何建议，我可以在其中复习计算机图形学的数学。我已经离开大学一段时间了，感觉好像我忘记了一切:)！其他人有这个问题吗？

（注意：我发现这个问题与这个似乎更复杂的问题不同，并且没有直接回答这个问题。）

我正在为年轻人设计一个碰撞检测游戏教程，所以我希望它尽可能简单，以便于解释。

要求非常简单。世界是二维的，只包含矩形（任意大小）。BSP 甚至四叉树似乎都过大了（再次强调简单性），但我想要比暴力破解所有 n(n-1)/2 可能的冲突更有效的东西。

2D，仅矩形，简单。

谁能指出我可以查找的算法？我正在寻找四叉树算法吗？

编辑：此外，矩形永远不会旋转（我保持简单）。为了让您了解我的工作规模，您的典型用户的笔记本电脑/台式机（不到 5 年）上将运行数百个矩形，这些矩形是用 Python 和 Pygame 实现的。

我正在尝试在 C# 应用程序（6000x6000，尽管大多数是透明的）中创建相当大的位图，并且需要将它们绘制到仅支持绘制矩形的特定输出 API。

现在，我想知道是否有人有一种算法可以将位图缩小为一系列填充的类似颜色位图的矩形；因为将所有内容绘制为 1x1 矩形对于此目的来说太慢了。例如，应该将一个圆缩减为一个大的中心矩形，而将圆的其余部分缩减为有效的矩形。该算法甚至不需要那么快，因为我的单像素方法所花费的大部分时间是循环遍历 API 本身的每个矩形。

我有一组N个正数，以及一个尺寸为X和Y的矩形，我需要将其划分为N个较小的矩形，这样：

• 每个较小矩形的表面积与其在给定集合中的相应数字成正比
• 大矩形的所有空间都被占用，小矩形之间没有剩余空间
• 每个小矩形都应尽可能接近正方形
• 执行时间应该相当短

我需要这方面的指示。你知道网上描述的这种算法吗？你有什么想法（伪代码很好）？

谢谢。

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

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

蓝色矩形是模型。

首先，我需要抽象算法。对于实现没有特殊要求。一个矩形可以表示为一对点（左上和右下）。

这是准备考试的任务之一。我知道最好的算法可以在O(n log n)时间内做到这一点。