c++ - 线段相交算法

Question

我正在按照“算法简介”一书来实现线段相交，但我对算法得到的结果感到困惑。我一定是在算法中遗漏了一些东西，我需要一些帮助才能找到它。检查以下代码片段:

glm::i16vec2 contourLineStart(1057,1762);
glm::i16vec2 contourLineEnd(1057,0);

glm::i16vec2 hilbertLineStart(-1762,-2466);
glm::i16vec2 hilbertLineEnd(-1734,-2466);

如您所见，两条线是用上面定义的坐标制定的，您还可以想象 contourLine 由 contourLineStart 和 contourLineEnd 制定，而 hilbertLine 可以由 hilbertLineStart 和 hilbertLineEnd 制定。而且这两条线不可能相交。不幸的是，算法告诉我有一个交叉点，这让我很困惑。剩下的代码如下:

glm::i32 direction(const glm::i16vec2& pi,
                   const glm::i16vec2& pj,
                   const glm::i16vec2& pk)
{
    return ((pk.x - pi.x)*(pj.y - pi.y)) - ((pj.x - pi.x)*(pk.y - pi.y));
}

int main()
{
   glm::i16vec2 contourLineStart(1057,1762);
   glm::i16vec2 contourLineEnd(1057,0);

   glm::i16vec2 hilbertLineStart(-1762,-2466);
   glm::i16vec2 hilbertLineEnd(-1734,-2466);

   glm::i16 d1 = direction(contourLineStart,contourLineEnd,hilbertLineStart);
   glm::i16 d2 = direction(contourLineStart,contourLineEnd,hilbertLineEnd);
   glm::i16 d3 = direction(hilbertLineStart,hilbertLineEnd,contourLineStart);
   glm::i16 d4 = direction(hilbertLineStart,hilbertLineEnd,contourLineEnd);


   if((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0) &&
      (d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))
   {
    std::cout << "There is a intersection" << std::endl;
   }
   else
   {
    std::cout << "There is no intersection" << std::endl;
   }

return 0;
}

我在这个过程中有什么遗漏吗？

谢谢

Answer 1

这里:

if((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0) &&
  (d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))

添加一些括号以避免(a || b && c || d)的歧义:

if(((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
  ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))