给定一组折线,我发现角度类型的检测存在问题(无论是 内部 还是 外部 与轴的原点)。
我发现了几十个非常相似的问题,但没有一个能解决我的问题,所以我把它放在这里,希望有什么结果。
我所拥有的只是一组折线。我需要找到角度(具有接近矩形的给定公差),并将它们分类为内部或外部。
对于每条折线,我将顶点乘以 3 乘以 3,并且我能够识别中心点是否为角度,并将其值测量为 0 到 180 度之间的数字。
现在我需要给这个角度一个方向(比方说一个符号,如果锐角远离原点则为负,如果它指向中心则为正),我想我会用下面的两种方法之一来实现它,但他们都没有工作。
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 个邻居之间的线相比,检查顶点是否在原点的同一侧。但我需要尽可能地优化它。
最佳答案
简短版本:
将来自中心点的两个角度 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`
当且仅当这些都为真时,您的角度才被定义为“内部”。
关于c++ - 检查由 3 个点定义的角度是内角还是外角,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/12397564/