在三角测量等距网格中，给定一个点在哪个三角形中？

Question

我有一个三角形等距网格，就像这样：
_{（来源：mathforum.org）} 在我的代码中，三角形按列分组。

当我悬停鼠标时，我想计算鼠标坐标所在的三角形。是否有一个简单的算法来实现这个功能？

- Steph Thirion

---

取决于情况，顶部必须有一个三角形的一部分，因为它不会与屏幕顶部对齐。你如何处理这个问题？ - Chris H

Answer 1

这与cletus所说的类似，但可能是以不同的方式看待它。

我假设三角形的边长为1。

假设您有以下网格：

       y'
      /
     /__/__/__/__/__/__/
    /__/__/__/__/__/__/
   /__/__/__/__/__/__/____ x'
(0,0)

如果你考虑一个坐标系中的网格，其中x和y轴成60度角，那么在该角度系统中的坐标(x',y')将对应于正交系统中的坐标(x,y)（具有相同的原点和轴的一般方向）。

在你的问题中，给定了(x,y)，我们需要找到(x',y')，然后计算出三角形。

如果i是沿着x的单位向量，j是沿着y的正交向量，那么我们有：

x'* i + y'( i/2 + sqrt(3) * j /2) = xi + yj.

基本上，沿着“倾斜”的y轴的单位向量是i/2 + sqrt(3)/2 * j。沿着x轴的单位向量与正常的x轴相同，即i。

因此，

x' + y'/2 = x
y' * sqrt(3)/2 = y

解决问题的方法如下：

y' = 2*y/sqrt(3)
x' = x - y/sqrt(3)

假设现在x'和y'是正数。

如果c = [x']，则x'的整数部分为c。

如果r = [y']，则y'的整数部分为r。

那么在（角度）网格中，该点位于第cth列和第rth行。（向右和向上计数，并从0开始计数）。

因此，我们已经将您的点缩小到了一个平行四边形。

       ____
      /\ * /   
     /___\/
   (c,r)

现在为了找出它在哪个三角形中，您可以考虑 x' 和 y' 的小数部分。

{x} = x' - [x'] = x' - c.
{y} = y' - [y'] = y' - r.

现在，

如果{x} + {y} > 1，那么该点位于标有 * 的三角形中。 如果{x} + {y} < 1，则该点位于另一个三角形中。 如果{x} + {y} = 1，则该点位于两个三角形共同的直线上。

希望这也能帮到您。

- Aryabhatta

Answer 2

你需要做的是尽可能将其转化为网格，因为网格更容易处理。首先要做的是确定它所在的列。你说你存储了它，所以通过将x坐标除以列宽再减去盒子起始位置就更容易了。简单吧。之后你想要确定它在哪个三角形内。你部分地将其转换为网格的方法是，假装你有一堆直角三角形而不是等距三角形。三角形沿y轴（列的一侧）具有长度。将该数字除以2，然后计算出你向下移动了多少步。基于向下的步数和列是偶数还是奇数，可以告诉你你是否正在查看：

+--------+
|-_      |
|  -_    |
|    -_  |
|      -_|
+--------+

或者反过来。此时，您只需要确定它在哪一条线的一侧，以确定它位于哪个直角三角形中，这也告诉您它位于哪个等距三角形中。

您有几种选择。

1. 您可以使用类似Bresenham的线算法来光栅化斜边，当您到达所在的列时，计算您是否在该行上方或下方；
2. 因为这里只有两个可能的网格（一个是另一个的反向，所以实际上只有一个）。您可以存储一组行值的数组，指定对于第3列，斜边在偏移量2处，而对于第6列，它在4处等等。

您甚至可以使用（1）生成（2）作为快速查找。

唯一需要考虑的其他事情是如果鼠标光标在边缘会发生什么？

- cletus

---

你不需要画一条线或者查找表——斜率就是除法。 - mattdm