c++ - 检查由 3 个点定义的角是内角还是外角

Question

在给定一组折线的情况下，我发现角度类型检测(无论是内部还是外部 wrt 轴的原点)存在问题。我发现了很多非常相似的问题，但没有一个能解决我的问题，所以我把它放在这里希望能有所收获。

我只有一组折线。我需要找到角度(具有接近矩形的给定公差)，并将它们分类为内部或外部。

对于每条折线，我将顶点 3 乘 3，我能够识别中心的折线是否是角，并将其值测量为 0 到 180 度之间的数字。

现在我需要给这个角度一个方向(比方说一个符号，如果锐角指向远离原点则为负，如果指向中心则为正)，我想我会用其中一个来实现它以下 2 种方法，但均无效。

1) 只是“二维叉积的符号”(我知道这不是数学上正确的术语):

//given 3 contiguous vertices a,b,c
//check if b is a inner (+1) or outer (-1) vertex (0 in other cases)

double cross = ((b.x - a.x)*(c.y - a.y)) - ((b.y - a.y)*(c.x - a.x));

if(cross > 0){
  return 1;
} else if (cross < 0) {
  return -1;
}
return 0;

但它似乎只在左下象限有效，在右上象限以相反的方式工作，而它在其他象限中起作用，我不明白为什么。

2)比较顶点的范数

if b.norm() < a.norm() && b.norm() < c.norm 
then return +1
else return -1

这仅适用于基本情况，并且总体上没有多段线穿过轴(包含原点)。我可以检查所有情况，但我宁愿避免这种情况。

显然，有更安全的方法，例如检查顶点是否在原点的同一侧，而不是通过位于 2 个 vector 上的 2 个邻居之间的线。但我需要尽可能优化它.

Answer 1

简短版:

将来自中心点的两个角 vector 描述为a 和b。并将从您的中心点到原点的 vector 描述为 center。

如果出现以下情况，该角度将被描述为“内部”:

dot( a + b, center ) > 0.0 && dot( cross( a, center ), cross( b, center ) ) < 0.0

解释:

这可以通过同时使用叉积和点积来解决。 (幸运的是，根本没有角度。这完全可以通过加法、乘法和比较来解决。)

在这里，分两步解决。

<强>1。角度是否更多指向原点而不是远离原点？

如果您通过对两个角度 vector 求和来定义“角度指向的方向”，则角度更指向而不是远离。

注意，如果 a 和 b 各自的长度不同，可以得到非常广角的一些不正确的边缘情况。规范化 a 和 b 将解决这个问题。

`dot( a + b, center ) > 0.0`

<强>2。 vector a 和 b 是否指向原点的相对侧？

如果 vector a 和 b 的叉积指向相反的方向，则它们指向原点的相反侧。

`dot( cross( a, center ), cross( b, center ) ) < 0.0`

当且仅当这些都为真时，您的角度才被定义为“内部”。