问题标签 [computational-geometry]

我有一个使用 Google 地球的 Windows 窗体应用程序，用户可以在该应用程序中在地图上绘制一个用作地理围栏的多边形。

我想做的是能够缩放到多边形，以便它通过单击按钮很好地适应屏幕。一种缩放以适应功能。

找到多边形的中心并将 Google 地球相机设置为该纬度/经度很容易。

我需要的是一种算法，它采用纬度\经度、屏幕高度\宽度的边界框，然后确定设置相机的高度。

有没有人有这个算法或知道在哪里可以找到？

谢谢！！

我将在秋季参加关于计算几何的课程，我们将在 C 或 C++ 中实现一些算法并对其进行基准测试。大多数学生生成一些数据集并使用time命令测量他们的程序，但我想更彻底一点。

我正在考虑编写一个程序来自动生成不同的数据集，使用它们运行我的程序并使用 R 来测试假设和估计参数。

那么......你如何更准确地测量程序运行时间？

什么可能与测量相关？

哪些假设可能值得测试（方差、缓存造成的影响等）？

我应该在多台机器上测试我的代码吗？这些机器应该有什么不同？

我的总体目标是了解这些算法在实践中的表现，哪些实现技术更好，以及硬件的实际表现如何。

问题：假设您在 2D 平面中有一组点。我想知道这组点是否位于规则网格上（如果它们是 2D 晶格的子集）。我想要一些关于如何做到这一点的想法。

现在，假设我只对这些点是否形成一个轴对齐的矩形网格（底层格子是矩形的，与 x 和 y 轴对齐）以及它是否是一个完整的矩形（晶格有一个没有孔的矩形边界）。任何解决方案都必须非常有效（优于 O(N^2)），因为 N 可以是数十万或数百万。

背景：我写了一个二维向量场图生成器，它适用于任意采样的向量场。在采样在规则网格上的情况下，有更简单/更有效的插值方案来生成图，我想知道什么时候可以使用这种特殊情况。特殊情况足够好，值得做。该程序是用 C 编写的。

我正在寻找一种打包算法，它将不规则多边形减少为矩形和直角三角形。该算法应尝试使用尽可能少的此类形状，并且应该相对容易实现（考虑到挑战的难度）。在可能的情况下，它还应该更喜欢矩形而不是三角形。

如果可能，这个问题的答案应该解释建议算法中使用的一般启发式方法。

对于少于 100 个顶点的不规则多边形，这应该在确定的时间内运行。

目标是为外行生成不规则多边形的“合理”分解。

应用于解决方案的第一个启发式将确定多边形是规则的还是不规则的。对于正多边形，我们将使用我在关于正多边形的类似文章中概述的方法：正多边形的高效打包算法

替代文字 http://img401.imageshack.us/img401/6551/samplebj.jpg

问题
我想将网格（2D 阵列）划分为随机形状的部分（想想地球的构造板块）。

标准是：

• 用户输入网格大小（程序应该缩放，因为这可能非常大）。
• 用户输入网格划分因子（多少部分）。
• 网格是一个矩形的六角网格，顶部和底部都加盖，左右环绕。
• 零件没有碎片。
• 其他零件内没有零件。
• 没有微小或超大的零件。
• 随机形状的零件，不是完美的圆形，或串成的蛇形。

我的解决方案：

• 创建一个可以访问/操作相邻单元格的方法。
• 随机确定每个部分的大小（所有部分的总和等于整个二维数组的大小）。
• 用最后一部分的 id 号填充整个 2D 数组。
• 对于除最后一个部分之外的每个部分：
• 在 2D 数组的随机单元格中播种当前零件 ID 号。
• 遍历整个数组并存储每个单元格的地址，这些单元格与已使用当前部件 ID 号播种的任何单元格相邻。
• 提取其中一个存储的地址并用当前的车牌 ID 号填充该单元格（因此零件开始形成）。
• 重复直到达到零件尺寸。

请注意，为了避免零件内部带有长长的“臂”或大孔，我创建了两个存储阵列：一个用于仅与具有当前零件 ID 号的一个单元相邻的单元，另一个用于与多个相邻的单元，然后我在前者之前用尽后者。

运行我的解决方案给出以下信息：
网格大小：200
宽度：20
高度：10
部分：7

66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
00000333111164444660
00000336111664422600
00000336615522222200
00006655555522222200
00006655555552222220
00066655555552222220

零件编号：0
零件尺寸：47

零件编号：1
零件尺寸：30

零件编号：2
零件尺寸：26

零件编号：3
零件尺寸：22

零件编号：4
零件尺寸：26

零件编号：5
零件尺寸：22

零件编号：6
零件尺寸：27

我的解决方案存在的问题：

• 最后一部分总是零散的——在上面的例子中，有三个独立的六组。
• 当零件在死胡同中形成并且没有空间增长到它们的完整尺寸时，该算法将停止（该算法不允许在其他部分上形成零件，除非它是最后一部分，它被放置在整个开始时的二维数组）。
• 如果我在形成 2d 数组之前没有指定零件尺寸，而只是指定零件数量并动态随机生成零件尺寸，这就留下了形成微小零件的可能性，这也可能不会在那里，尤其是当二维数组非常大时。我当前的零件尺寸方法将零件尺寸限制在二维数组总尺寸的 10% 到 40% 之间。如果有一些超级优雅的方法可以做到这一点，我可以不指定零件尺寸 - 用户将拥有的唯一控制是二维数组大小和零件数量。

其他想法：

• 将零件形成完美对齐的正方形，然后在 2D 阵列上运行并随机让每个零件侵占其他零件，将它们扭曲成随机形状。
• 在网格上绘制蛇形线并填充创建的空间，可能使用如下数学：http: //mathworld.wolfram.com/PlaneDivisionbyLines.html

结论：
所以问题来了：我是一个初学者程序员，不确定我是否以正确的方式解决了这个问题。我可以创建一些更多的“修补”方法，将零散的部分转移到一起，如果它们卡在死胡同中，允许形成的部分“跳出”，但感觉很混乱。

你会如何处理这个问题？有没有一些我可以用来简化事情的性感数学？

谢谢

我正在开发一个图像分析应用程序，我需要计算分段粒子的纵横比。

根据 http://www.sympatec.com/Science/Characterisation/05_ParticleShape.html，AR 由（图 1）Xfmin/Xfmax 给出。

有什么算法可以得到这个值（Xf）吗？

问题：

给定：与 3d k 边非凸多边形强相关的 n 个点，其中 n >> k

Find：与点的原始几何形状匹配的最佳拟合凹壳

尝试的解决方案：

警告：伪代码

例子：

输入将只是一个高密度点云，它是多边形平面内近似均匀分布的随机点，带有一点噪音。

输出将是 3d 点中多边形的顶点。

我的问题是，有没有更好的方法来解决这个问题？上述解决方案的问题是这些点可能是嘈杂的。此外，将点光栅化为 2d 然后执行边缘查找非常昂贵。

任何指针都会很棒。提前致谢

StackOverflow 的第一个问题，请温柔一点。

• 在给定一定幅度或“信号强度”的情况下，我试图找到二维笛卡尔平面上三个不同点的中心点的方程（然后是算法）。这些信号强度都是相互关联的，但不必将其与圆的“半径”混为一谈。

三边测量的维基百科条目： http ://en.wikipedia.org/wiki/Trilateration

我也检查了这个线程，但它与我需要的 使用 3 个纬度和经度点以及 3 个距离的三边测量有点不同

一般方程很好，但我将在此处提供一些示例数据点进行测试：

P1: X,Y = 4153, 4550 // 幅度或信号强度 = 143
P2: X,Y = 4357, 4261 // 幅度或信号强度 = 140
P3: X,Y = 4223, 4365 // 幅度或信号强度 = 139

我的一般感觉是这些点需要被翻译成相同的比例（信号强度和点），但我可能是错的。

想法？TIA

在我看来，这是一个非常简单的问题，但今天我自己似乎找不到一个合理的答案。我有两个点，R^3（3D）中的 A 和 B 属于平面 PI。我想在 PI 中找到一个向量 r，它垂直于向量 v = A - B。我知道向量 n，即平面 PI 的法线。从数学上讲，我可以解 vr = 0 和 vxr = n，但是这个系统在 r 方面的解涉及一些我怀疑可能带来一些数值不稳定性的除法。你能建议我解决这个问题的任何数值/计算上的好方法吗？

提前致谢，

费德里科

我有一个点，比如说 p(0.0, 0.0, 20.0) 我想在 XZ 平面上绕点 a(0.0, 0.0, 10.0) 旋转。最简单的方法是什么？我将 Qt 与 QVector3D 和 QMatrix4x4 一起使用来执行转换。我能想到的一切都是这样的：

但这对我来说似乎非常复杂，我想知道是否有任何更简单或更优雅的解决方案？