问题标签 [geometry]

找到适合空白空间的最大面积矩形的最有效算法是什么？

假设屏幕看起来像这样（'#' 表示填充区域）：

一个可能的解决方案是：

通常我会喜欢找出解决方案。虽然这一次我想避免浪费时间自己摸索，因为这对我正在从事的项目有实际用途。有众所周知的解决方案吗？

Shog9写道：

您的输入是一个数组（正如其他响应所暗示的那样），还是一个任意大小、定位的矩形形式的遮挡列表（在处理窗口位置时可能是窗口系统中的情况）？

是的，我有一个结构可以跟踪放置在屏幕上的一组窗口。我还有一个网格，它跟踪每个边缘之间的所有区域，无论它们是空的还是填充的，以及它们的左边缘或上边缘的像素位置。我认为有一些修改的形式可以利用这个属性。你知道吗？

我有两个点（一条线段）和一个矩形。我想知道如何计算线段是否与矩形相交。

我在屏幕空间中有 4 个 2D 点，我需要将它们反向投影回 3D 空间。我知道这 4 个点中的每一个都是 3D 旋转刚性矩形的一个角，并且我知道矩形的大小。如何从中获得 3D 坐标？

我没有使用任何特定的 API，也没有现有的投影矩阵。我只是在寻找基本的数学来做到这一点。当然没有足够的数据将单个 2D 点转换为 3D 没有其他参考，但我想如果你有 4 个点，你就会知道它们在同一平面上彼此成直角，而且你知道它们之间的距离，你应该能够从那里弄清楚。不幸的是，我无法完全弄清楚如何。

这可能属于摄影测量的范畴，但谷歌搜索并没有让我找到任何有用的信息。

我正在尝试使用 GPU 功能解决当前的问题：“给定一个点云 P 和一个由点和法线 (Pp, Np) 描述的定向平面，返回云中距离等于或小于 EPSILON 的点从飞机上”。

与我的一位同事交谈后，我得出了以下解决方案：

1) 准备一个带有附加纹理坐标的点的顶点缓冲区，这样每个点都有不同的顶点坐标 2) 将投影状态设置为正交 3) 旋转网格，使平面的法线与 -z 轴对齐，并且偏移它使得 x,y,z=0 对应于 Pp 4) 设置 z 剪切平面使得 z:[-EPSILON;+EPSILON] 5) 渲染到纹理 6) 从显卡中检索纹理 7)从显卡读取纹理并查看渲染了哪些点（根据它们的索引），这些点是所需距离范围内的点。

现在问题如下： q1）我需要打开一个窗口框架才能进行这样的操作吗？我在 MATLAB 中工作并调用 MEX-C++。根据经验，我知道一旦你打开一个新框架，整个套装就会惨遭崩溃！q2) 为 GLPoint 提供纹理坐标的原语是什么？q3) 我不太清楚如何实现对纹理的渲染？任何参考，教程都会很棒... q4）您将如何从卡中检索此纹理？再次，任何参考，教程都会很棒......

我的日程安排很紧，因此，如果您能指出我应该学习的技术的名称，而不是像有人所做的那样指向 GLSL 规范文档和 OpenGL API，那就太好了。这些对我的问题的回答有点太模糊了。

非常感谢您的任何评论。

ps 另请注意，如果可能的话，我宁愿不使用像 CUDA 这样的任何资源，因此，在不需要我编写新着色器的情况下，获得使用尽可能多的 OpenGL 元素的东西。

注意：交叉发布在 http://www.opengl.org/discussion_boards/ubbthreads.php?ubb=showflat&Number=245911#Post245911

作为工作项目的一部分，我必须计算 3D 空间中一组点的质心。现在我正在以一种看似简单但幼稚的方式来做这件事——通过取每组点的平均值，如下所示：

其中x,y和z是浮点数数组。我似乎记得有一种方法可以获得更准确的质心，但我还没有找到一个简单的算法来做到这一点。有人有什么想法或建议吗？我为此使用 Python，但我可以改编其他语言的示例。

从 GIS 文件（城市地图）中获得一组（2D）点，我需要生成定义该地图（其边界）的“轮廓”的多边形。它的输入参数将是点集和“最大边长”。然后它将输出相应的（可能是非凸的）多边形。

到目前为止，我发现的最佳解决方案是生成 Delaunay 三角形，然后删除比最大边长更长的外部边。在所有外部边缘都比这短之后，我只需删除内部边缘并获得我想要的多边形。问题是，这非常耗时，我想知道是否有更好的方法。

我正在开发一个游戏，我创建了一张随机的省份地图（风险或外交）。为了创建该地图，我首先生成一系列半随机点，然后计算这些点的 Delaunay 三角剖分。

完成后，我现在正在寻找创建点的 Voronoi 图，作为省边界的起点。我此时的数据（不是双关语）由原始的一系列点和 Delaunay 三角形的集合组成。

我在网上看到了很多方法来做到这一点，但其中大多数都与 Delaunay 的派生方式有关。我很想找到一些不需要集成到 Delaunay，但可以仅根据数据工作的东西。如果做不到这一点，我正在寻找相对几何新手可以理解的东西，而不是最佳速度。谢谢！

如果椭圆的长轴是垂直的或水平的，那么边界框的计算很容易，但是当椭圆旋转时呢？

到目前为止，我能想到的唯一方法是计算周边的所有点并找到最大/最小 x 和 y 值。似乎应该有一个更简单的方法。

如果有一个函数（在数学意义上）以任意角度描述椭圆，那么我可以使用它的导数来找到斜率为零或未定义的点，但我似乎找不到。

编辑：澄清一下，我需要轴对齐的边界框，即它不应该与椭圆一起旋转，而是与 x 轴保持对齐，因此转换边界框将不起作用。

我有一组覆盖封闭矩形的非重叠矩形。找到鼠标单击的包含矩形的最佳方法是什么？

显而易见的答案是拥有一个矩形数组并按顺序搜索它们，使得搜索 O(n)。是否有某种方法可以按位置对它们进行排序，以使算法小于 O(n)，例如 O(log n) 或 O(sqrt(n))？

如何测试线段是否与二维中的轴对齐矩形相交？该段由其两端定义：p1，p2。矩形由左上角和右下角点定义。