algorithm - 在笛卡尔坐标系中确定二维三角形交点

Question

我正在编写一个简单的图形编辑器，用户可以在其中绘制一个三角形(顺时针或逆时针方向)，然后可以选择该三角形并将其拖动。

我的问题归结为确定鼠标光标坐标是否与三角形相交。因为我使用的是 GLFW，所以我的窗口空间是在笛卡尔坐标系上定义的，其中 x/y 的范围为 [-1, 1]。

当我尝试使用重心坐标(或找到的任何其他方法 here)确定是否有交点时，这会导致问题

我目前的做法如下:

double xpos, ypos;
glfwGetCursorPos(window, &xpos, &ypos);

// Get the size of the window
int width, height;
glfwGetWindowSize(window, &width, &height);

// Convert screen position to world coordinates
xworld = ((xpos / double(width)) * 2) - 1;
yworld = (((height - 1 - ypos) / double(height)) * 2) - 1; // NOTE: y axis is flipped in glfw

double area = 0.5 * (-p1y * p2x + p0y * (-p1x + p2x) + p0x * (p1y - p2y) + p1x * p2y);

double s = 1 / (2 * area) * (p0y * p2x - p0x * p2y + (p2y - p0y) * xworld + (p0x - p2x) * yworld),
       t = 1 / (2 * area) * (p0x * p1y - p0y * p1x + (p0y - p1y) * xworld + (p1x - p0x) * yworld);
if (s > 0 && t > 0 && 1 - s - t > 0)
    return true;
return false;

如果三角形位于第一象限且逆时针方向，这有点有效，但是，如果在三角形的左侧，它也可以识别为相交。

感谢您的帮助。

编辑: 问题是我在代码中的错别字(我的三角形中的顶点值错误)最终使用面积方法的计算来检测交叉点。

Answer 1

如果您不知道三角形的缠绕顺序，您可以检查鼠标光标位置是在每条边的左侧还是在每条边的右侧。如果其中之一为真，则鼠标光标确实位于三角形内。

幸运的是，在三角形的情况下，它的顶点的任何 2 次组合都会产生它的边。所以这道题就是计算六个叉积。

而且，在用户绘制完三角形后，您可以按一定的缠绕顺序保存三角形的顶点，然后您只能进行三个叉积。