3

给定一组折线，我发现检测角度类型（无论是内部还是外部轴的原点）存在问题。我发现了几十个非常相似的问题，但没有一个能解决我的问题，所以我把它放在这里，希望能有结果。

角度分类

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

对于每条折线，我将顶点 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 个向量上的 2 个邻居之间的线。但我需要尽可能优化它。

4

3 回答 3

4

简短版本：

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

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

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

说明：

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

在这里，分两步解决。

1. 角度是否指向原点而不是指向原点？

如果您通过对两个角度向量求和来定义“角度指向的方向”，则角度指向的 方向多于远离方向。

请注意，如果 和 的各个长度 a 不同 b ，对于非常宽的角度，您可能会得到一些不正确的边缘情况。规范化 a 并将 b 解决该问题。

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

2. 向量a和b指向原点的对边吗？

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

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

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

于 2012-09-13T00:59:57.550 回答
3

要检测角度 abc 是否在内部，您必须检查向量 b0（从 b 到原点）是否是向量 ba 和 bc 的凸组合。

如果向量 px + qy 是向量 p1x + q1y 和 p2x + q2y 的凸组合，则存在正常数 r 和 s 使得 r * (p1, q1) + s *(p2, q2) = (p, q) . 如果我们以代数方式求解 r 和 s，我们得到 r = (pq2 - p2q)/(p1q2 - q1p2) 和 s = (p1q - pq1)/(p1q2 - q1p2)。如果 r 和 s 都是正数，则 abc 是内部的。

于 2012-09-13T01:06:43.483 回答
0

就个人而言，我只会使用点积。具体来说（如果a表示从您的顶点到原点的向量，并且b和c是指向顶点外的边向量），那么如果两者a dot b和a dot c都是正数，则角度是外部的。否则是内在的。

但我对你对“内在”和“外在”的真正定义有点困惑......

于 2012-09-13T00:30:19.520 回答