在三角形等距网格中,给定点是什么三角形？

Question

我有一个三角形的等距网格,像这样: 替代文字

在我的代码中,三角形按列分组.

当我将鼠标悬停在鼠标上时,我想计算鼠标坐标所在的三角形.是否有一个简单的算法可以做到这一点？

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' 的整数部分

r = [y']，y' 的整数部分

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

因此我们将你的观点缩小到平行四边形

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

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

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

现在，

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

希望这也有帮助。

Answer 2

您要做的就是尽可能将其转换为网格，因为网格更容易使用。

您要做的第一件事是计算出它位于哪一列。您说您存储了它，因此通过在 x 坐标上除以框起始处的列宽度偏移量进行简单的整数除法应该会更容易。简单的。

之后你想算出它在哪个三角形中（显然）。如何将其部分转换为网格是假装您有一堆直角三角形而不是一堆等距三角形。

三角形具有沿 y 轴（柱的边）的长度。将这个数字除以二，算出你下降了多少步。根据向下的步数以及该列是偶数还是奇数，将告诉您是否正在查看：

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

或相反。此时，您只需确定它位于直线的哪一侧即可确定它位于哪个直角三角形中，这也可以告诉您它位于哪个等角三角形中。

为此，您有几种选择。

您可以使用布雷森纳姆线算法之类的东西来栅格化斜边，当您点击所在的列时，您可以计算出您是在该线之上还是之下；
因为这里只有两个可能的网格（一个与另一个相反，所以实际上只有一个）。您可以存储行值数组，表示对于第 3 列，斜边位于偏移量 2 处，而对于第 6 列，斜边位于偏移量 4 处，依此类推。

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

唯一需要考虑的另一件事是如果鼠标光标位于边缘会发生什么？