我想知道处理大量移动对象（球体、三角形、框、点等）的最佳数据结构是什么？我试图回答两个问题，最近邻和碰撞检测。

我确实意识到，传统上，像 R 树这样的数据结构用于最近邻查询，而 Oct/Kd/BSP 用于处理静态对象或很少移动对象的碰撞检测问题。

我只是希望那里有其他更好的东西。

我感谢所有的帮助。

我有一个未排序的嘈杂 X、Y 点列表。然而，它们确实形成了一条穿越世界的道路。我想要一种算法来使用线段绘制这些数据的近似值。

这类似于您如何使用线拟合算法来选择线性数据的近似值。我的问题更加困难，因为这条路在世界各地弯曲和蜿蜒。 替代文字 http://www.praeclarum.org/so/pathfinder.png

有谁知道任何标准/强大/易于理解的算法来实现这一点？

问答：

你说的吵是什么意思？如果我有一个理想的路径实现，那么我的一组点将从该理想路径中采样，并将高斯噪声添加到 X 和 Y 元素。我不知道该噪声的平均值或标准偏差。我也许可以猜到std dev ...

这些点是否靠近但不在您寻求近似的理想但复杂的路径上？是的。

你有关于路径形状的任何先验信息吗？还有其他方法可以获取此类信息吗？不幸的是没有。

数组中的四个二维点。我需要按顺时针顺序对它们进行排序。我认为只需一次交换操作即可完成，但我无法正式将其放下。

编辑：在我的例子中，这四个点是一个凸多边形。

编辑：这四个点是凸多边形的顶点。他们不必井井有条。

我正在尝试创建一个 WPF 形状（折线）编辑器，这是一个我想用来在画布中编辑形状的控件。

编辑器需要做的是能够显示形状的点和线并移动它们。

任何人都可以向我提供如何实现这一目标或起点的想法吗？到目前为止，我还没有找到任何与我如何做到这一点有关的东西。

我的情况

• 输入：一组矩形
• 每个矩形由 4 个这样的双精度组成： (x0,y0,x1,y1)
• 它们不会以任何角度“旋转”，它们都是相对于屏幕“上/下”和“左/右”的“正常”矩形
• 它们是随机放置的——它们可能在边缘接触、重叠或没有任何接触
• 我将有数百个矩形
• 这是在 C# 中实现的

我需要找到

• 由它们重叠形成的区域 - 画布中多个矩形“覆盖”的所有区域（例如，两个矩形，它将是交叉点）
• 我不需要重叠的几何形状——只需要面积（例如：4 平方英寸）
• 重叠不应计算多次 - 例如，想象 3 个具有相同大小和位置的矩形 - 它们彼此重叠 - 该区域应计算一次（而不是三次）

例子

• 下图包含三个矩形：A、B、C
• A 和 B 重叠（如虚线所示）
• B 和 C 重叠（如虚线所示）
• 我正在寻找的是显示破折号的区域

-

比较两个多边形的相似性的常用方法是什么？顶点是二维的。

有一些几何数据和变换如何将变换应用于几何以得到一个新的几何与它的数据转换？

例如：我有一个 Path 对象，它的 Path.Data 设置为 PathGeometry 对象，我想使用变换来变换PathGeometry 对象的点，而不是对将在渲染时使用的 PathGeometry 应用变换.

PS我知道Transform类有一个Point Transform.Transform(Point p)可以用来变换Point的方法但是......有没有办法一次变换任意几何？

编辑：查看我的回复以获取当前找到的解决方案

在我的 Direct3D 应用程序中，可以使用鼠标或箭头键移动相机。但是，如果我将 (0,1,0) 硬编码为 中的向上方向向量LookAtLH，则该帧在相机的某些方向上会变为空白。

我刚刚了解到，当沿 Y 轴看时，(0,1,0) 不再作为向上方向工作（似乎很明显？）。对于这些特殊情况，我正在考虑将我的向上方向切换到其他方向。有没有更优雅的方法来处理这个？

我有一条从 (x1,y1,z1) 到 (x2,y2,z2) 的线（实际上是一个立方体）。我想旋转它，使其沿着从（x3，y3，z3）到（x4，y4，z4）的另一条线对齐。目前我正在Math::Atan2与Matrix::RotateYawPitchRoll. 有没有更好的方法来做到这一点？

编辑：我认为我对这篇文章的措辞非常糟糕。我实际上正在寻找的是来自两个向量的旋转矩阵。

我有 3 个点（A、B 和 X）和一个距离（d）。我需要创建一个函数来测试点 X 到线段 AB 上的任何点是否比距离 d 更近。

问题首先是，我的解决方案是否正确，然后提出更好（更快）的解决方案。

我的第一关如下

这段代码最终将针对大量 P 和大量 A/B/d 三元组运行，目的是找到所有通过至少一个 A/B/d 的 P，所以我怀疑有一种方法在此基础上降低总体成本，但我还没有研究过。

（顺便说一句：我知道一些重新排序、一些临时值和一些代数恒等式可能会降低上述成本。为了清楚起见，我只是省略了它们。）

编辑：这是一个 2D 问题（但推广到 3D 的解决方案会很酷

编辑：进一步思考，我预计命中率在 50% 左右。X 点可以在嵌套层次结构中形成，因此我希望能够将大型子树修剪为全通过和全失败。限制三连音的 A/B/d 将更像是一个技巧。

编辑：d 与 AB 的数量级相同。

编辑：Artelius 发布了一个不错的解决方案。我不确定我是否完全理解他的意思，因为我在完全理解之前就走上了正轨。无论如何，结果想到了另一个想法：

• 首先 Artelius 的位，预先计算一个矩阵，该矩阵将 AB 居中并与 X 轴对齐。（2 次添加、4 毫升和 2 次添加）
• 将其全部折叠到第一象限（2个腹肌）
• 在 X&Y 中缩放以使区域的中心部分成为一个单位正方形 (2 mul)
• test if the point is in that square (2 test) is so quit
• test the end cap (go back to the unscaled values
  • translate in x to place the end at the origin (1 add)
  • square and add (2 mul, 1 add)
  • compare to d^2 (1 cmp)

I'm fairly sure this beats my solution.

(if nothing better comes along sone Artelius gets the "prize" :)