如何使用 Half Space 测试确定一个点是在线段前面还是后面？

Question

半 space 测试如何确定一个点是否在一条线的前面？我尝试了以下内容。它在 大多数 的时间有效，但在其他时间失败。在某些情况下它不起作用吗？例如，只有当所有点都在某些象限内时它才有效吗？如果不是，我做错了什么？

我试过：

bool PointInFrontOfLine(Point testPoint, Point v1, Point v2)
{
    // Compute line normal
    double dx = v2.x - v1.x;
    double dy = v2.y - v1.y;
    double nx = -dy;
    double ny = dx;
    double length = sqrt(dx * dx + dy * dy);
    nx /= length;
    ny /= length;
    glm::vec3 normal(nx, 0, ny);

    glm::vec3 vec(testPoint.x - v1.x, 0, testPoint.y - v1.y);

    double distance = glm::dot(vecTemp, normal);

    if (distance > 0)
        return true;
    else
        return false;
}

Answer 1

你实际做的是计算由点 v1 和 v2:

定义的线的（左转）法向量

double dx = v2.x - v1.x;
double dy = v2.y - v1.y;
double nx = -dy;
double ny = dx;
double length = sqrt(dx * dx + dy * dy);
nx /= length;
ny /= length;
glm::vec3 normal(nx, 0, ny);

这可以简化：

glm::vec3 normal(v1.y - v2.y, 0, v2.x - v1.x);
normal = glm::normalize(normal);

注意，对于算法你甚至可以跳过归一化，那么你不会得到正确的正常distance，但distance的符号仍然是正确的。这对你来说就足够了，因为你只检查 distance > 0:

glm::vec3 normal(v1.y - v2.y, 0, v2.x - v1.x);

然后你检查normal向量与从v1到testPoint的向量之间的角度是否大于-90度且小于+90度：

glm::vec3 vec(testPoint.x - v1.x, 0, testPoint.y - v1.y);
double distance = glm::dot(vecTemp, normal);

这行得通，因为通常 2 个向量的点乘积等于 2 个向量之间夹角的余弦乘以两个向量的大小（长度）。如果一个角度的 cosine >= 0，则该角度在 [-90°, 90°] 范围内。

dot( A, B ) == length( A ) * length( B ) * cos( angle_A_B )

但该算法只有在v2.x < v1.x（下图中x轴从左到右，y轴从下到上）的情况下才有效：

如果交换 2 个点 (v2.x > v1.x)，那么您将得到相反的结果：

最后代码可以这样表达：

glm::dot(glm::vec2(testPoint.x-v1.x, testPoint.y-v1.y),
         glm::vec2(v1.y-v2.y, v2.x-v1.x)) * glm::sign(v1.x-v2.x) > 0

当然，结果还取决于 "in front of" 是什么意思。在我的假设中，这意味着 testPoint 的 y 坐标小于线 v1 到 v2 与通过 y 轴的平行线的交点的 y 坐标testPoint。这意味着如果此算法始终计算 "in front" 或 "in back".

，则取决于您的程序逻辑和坐标系

如何使用 Half Space 测试确定一个点是在线段前面还是后面？

How do you determine if a point is in front or behind a line segment using the Half Space test?

c++

opengl

point

line

glm-math