三角网格中最近点

2 投票

2 回答

989 浏览

提问于 2025-04-17 09:51

我想写一个函数，这个函数可以返回一个三角形网格中离某个点最近的网格节点（作为一个点）。这个网格是由等边三角形组成的，底边宽度为w，且与OX轴平行。网格的起始点是s。函数的格式应该像这样：

def snapToGrid(p,w,s):
    ...

比如说， snapToGrid([0.49,0],0.5,[0.0]) == [0.5,0]

有没有什么好的建议可以让我开始呢？

函数设计等边三角形网格节点三角网格最近点查找

2 个回答

这个问题的答案来自于很多人，其中包括“J. M. 不是数学家”在数学交流网站上的回答。

这里有一张答案的截图（2018年9月）

另外，在对原问题的评论中，同一个用户提到了另一个网站：http://www.geom.uiuc.edu/docs/reference/CRC-formulas/node7.html 这个页面描述了一个更一般情况的解决方案。

回答于 2025-04-17 由 Python大师

分享举报

编辑：这个回答是在不知道三角形网格是动态计算的情况下写的，我暂时保留这个回答，因为它可能有帮助，但对动态生成点没有帮助。

我认为动态生成点的答案会依赖于找到三角形的高度，然后意识到节点只会出现在三角形高度的倍数上。这应该能解决你的 X 组件的问题。

找到三角形的宽度也会告诉你节点在 Y 轴上出现的倍数，不过，每隔一行的三角形节点会在三角形宽度的一半的位置。找出你的原点距离原始点有多少行是第一步。

这将让你知道是用 三角形宽度 作为 Y 坐标的倍数，还是用 三角形宽度 + 1/2 三角形宽度 作为 Y 的倍数。

使用这两个值，应该很容易找到离你的点最近的 n*高度 和 n*宽度 的组合。

抱歉文字有点多，如果你在纸上画出你的网格，你会看到三角形沿着 X 轴形成节点的行，以及（对于 偶数行）列和（对于 奇数行）半列。

在寻找最近的点时，通常网格的类型或形状并不重要。逻辑上，你最近的点会属于你所在的形状。所以为了简化问题，你只需要找到离你最近的点，这其实是个很简单的问题。

这似乎最容易通过使用 K-D树来找到，其中的分割点是网格的 X 和 Y 坐标。然后简单的二分查找就能找到离你输入的坐标最近的网格点。

链接的文章中有 K-D 树操作的伪代码。

你也可以有一个字典，映射到 X 坐标，每个值包含一个对应于该 X 坐标的 y:name 对的字典。

这将允许你以以下方式搜索节点：

coordinate_x[<xvale>][<yvalue>]

这将返回你要找的节点，要获取 xvalue 和 yvalue，只需通过字典的键进行最近搜索，如下所示：

for x in coordinate_x.keys():
    if x-point_x < min:
        make x-point the closest

回答于 2025-04-17 由 Python大师

分享举报