我想编写一个函数，返回最接近某个点 p 的三角形网格(由底宽为 w 的等边三角形组成，平行于 OX 轴)的最近网格节点(作为一个点)。网格从点 s 开始。函数签名应如下所示:
def snapToGrid(p,w,s):
...
例如 snapToGrid([0.49,0],0.5,[0.0]) == [0.5,0]
有什么想法可以开始吗？
请您参考如下方法:
编辑: 这个答案是在知道要动态计算三角网格之前，我暂时保留它，因为它可能会有所帮助，但对动态点生成没有帮助。
我相信动态生成点的答案将依赖于找到三角形的高度，然后意识到节点只会存在于该三角形高度的倍数处。
这应该会处理您的 X 组件。
求出三角形的宽度还会告诉您节点沿 Y 轴出现的倍数，但是，每隔两行三角形的节点点将位于宽度的 1/2 处三角形的。
第一步是找到远离原点的行数。
这反过来会让你知道是使用triangle width作为Y坐标的倍数，还是triangle width+1/2 triangle width 用于 Y 乘数。
使用这两个值应该很容易找到最接近您的点的 n*height 和 n*width 组合。
对不起，文本墙，如果你在纸上绘制网格，你会看到三角形沿着 X 轴形成节点行，以及列(对于 even rows) 和半列(对于 奇数行)。
在寻找最近点时，网格的类型/形状通常无关紧要。从逻辑上讲，您最接近的点将属于您的点所在的形状。因此，为了简化事情，您需要做的就是找到离您最近的点，这是一个非常简单的问题。
使用 K-D Tree 似乎最容易找到它，其中分割点是网格的 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
