我这里需要一些算法想法。我有一大组二维点数据(约 100k 条目)作为对象，第三个变量作为平面上这一点的“值”。现在我想计算某个给定坐标处的插值点。
到目前为止，我唯一的想法是迭代整个数据集并收集距离我要计算的点最近的 4 个点的列表，然后在它们之间进行插值。 
如何在多个数据之间插入加权(在本例中按点的距离)？那么结果中更接近十字的点会更多出现吗？
<小时/>对于这种情况下如何获取给定坐标处的插值，您还有其他想法吗？它应该相对准确(但不必是 100%)，并且不应该花费很长时间来计算，因为这必须完成大约 10,000 次，而且我不希望用户等待太久。
<小时/>关于数据:点几乎在一个网格中，二维点的值实际上是高度值，因此两个相邻点的值也几乎相等。
数据存储在 HashMap<Vector2f, Float> 中哪里Vector2f是一个由 2 个 float 组成的简单类。没有任何排序。
最佳答案
这是一个不明显的问题。 3分就容易多了，4分你就会陷入模棱两可的情况。想象一下(对于正方形中样本周围的点)ul 和 br 角的值为 1，其他角的值为 5。它可以解释为高度为 1 的山谷穿过中心，高度为 5 的山脊穿过中心，或者某种奇特的形状样条鞍形。如果考虑到网格的不规则性，最近的 4 个点位于样本的同一侧，这会变得更加有趣(所以你不能只选择 4 个最近的点，你需要找到 4 个边界点)。
对于常规网格上的 4 点情况，您可以使用 https://en.wikipedia.org/wiki/Bilinear_interpolation生成某种“公平”插值。
对于不规则网格上的 4 个点，您可以研究如下解决方案 http://www.ahinson.com/algorithms_general/Sections/InterpolationRegression/InterpolationIrregularBilinear.pdf 但要小心寻找适当的边界点(正如我提到的，找到最近的边界点是行不通的)
关于java - 在多个点之间进行插值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37963504/