将点转换为其重心坐标

我正在制作一个2.5D游戏引擎(在JavaScript中),我试图让它检测一个块是否在光标下。 这将是一个简单的任务,它被限制在单级等距坐标,而是它应该支持等距世界,三角世界,以及任何投影角度真的,除了它是多层次的(瓷砖可以堆叠在每个其他达到任意限制)。 几乎所有的条件都是任意的,但现在我已经设法缩小了这个问题:

我需要知道一个点是否在六边形内:

在这里输入图像描述

到目前为止,我已经设置了一些有点骇人听闻的东西,我正在检查点是否在边界矩形内,以便删除最明显的情况。 接下来,我正在检查它是否在点ACDF形成的矩形内,另一个简单的检查。 现在困难的部分是我需要检查点是否在三角形内。 如果你有重心坐标,这是非常简单的,但我似乎已经失去了如何获得它们的所有知识。

请注意,虽然内部矩形总是矩形,但三角形可能不是等边的。 如果因为三角形的底部(或顶部)是平坦的而进行优化,则奖励分数。

维基百科有一篇很好的文章,解释如何获得2.1重心坐标转换为重心坐标

维基百科:

显式地,重心坐标的公式是:

在这里输入图像描述在这里输入图像描述在这里输入图像描述

所以在你最上面的三角形中,Ax将对应于x1,Ay到y1等等。 插入公式中的值将产生作为重心坐标的lamdas。 如果他们都是正面的,那么显然这个点在三角形内部。

由于三角形的底部是平坦的(因为我假设它不旋转或者可以在本地坐标中计算),可能的优化是通过仅比较y值来容易地评估一个lambda:

lambda1 = y1 – y

如果你的目标只是做hex的testing(而你实际上并不需要重心坐标),那么你的问题就变得容易了。 您可以简单地查看线段的方程,并find包含testing点的水平跨度的截距,然后检查它是否落在两端之间。

例如,如果你的点A,B,C的坐标分别是(Ax,Ay),(Bx,By)和(Cx,Cy),(Ay = Cy和Ax <Cx,By < – 注意我在下方向指向正Y),那么通过A和B的线段由x=Bx+(Ax-Bx)*(y-By)/(Ay-By)因为我们明确地表示By <Ay,所以可以确定插入y = Ay和y = By给出x的正确值)。 同样,通过C和B的线段由x=Bx+(Cx-Bx)*(y-By)/(Cy-By) 。 一旦你有这两行,你可以testing,以确保您的testing点的X位置之间的两个部分的值:

 bool TestPointInHex(point pt, point A, point B, point C, point D, point E, point F) { if ( (pt.y < By) || (pt.y > Ey) || (pt.x < Ax) || (pt.x > Cx) ) return false; if ( (pt.y >= Ay) && (pt.y <= Fy) ) return true; if ( pt.y < Ay ) { float leftX = Bx + (Ax-Bx)*(pt.yB.y)/(Ay-By); float rightX = Bx + (Cx-Bx)*(pt.yB.y)/(Cy-By); return ( (pt.x >= leftX) && (pt.x <= rightX) ); } else { // pt.y > Fy float leftX = Ex + (Fx-Ex)*(pt.yE.y)/(Fy-Ey); float rightX = Ex + (Dx-Ex)*(pt.yE.y)/(Dy-Ey); return ( (pt.x >= leftX) && (pt.x <= rightX) ); } } 

感谢@ mikael-hogstrom的回答,下面是我为此目的创建的一个函数:

 /** * Checks whether point `p` is inside triangle `abc` based on barycentric * coordinates. * * @param {Number} px x of p * @param {Number} py y of p * @param {Number} ax x of a * @param {Number} ay y of a * @param {Number} bx x of b * @param {Number} by y of b * @param {Number} cx x of c * @param {Number} cy y of c * * @return {Boolean} A boolean indicating whether p is inside abc */ function isPointInsideTriangle (px, py, ax, ay, bx, by, cx, cy) { var v0x = bx - ax var v0y = by - ay var v1x = cx - ax var v1y = cy - ay var v2x = px - ax var v2y = py - ay var d00 = v0x * v0x + v0y * v0y var d01 = v0x * v1x + v0y * v1y var d11 = v1x * v1x + v1y * v1y var d20 = v2x * v0x + v2y * v0y var d21 = v2x * v1x + v2y * v1y var denom = d00 * d11 - d01 * d01 var v = (d11 * d20 - d01 * d21) / denom var w = (d00 * d21 - d01 * d20) / denom var u = 1.0 - v - w return u >= 0 && v >= 0 && u + v < 1 } 

我想我会稍后在必要时进行优化。 🙂

下面是一个愚蠢的testing页面,可以试用它: http : //labs.avd.io/bary.html

感谢大家的帮助!