如何判断一个物体是否在连接的path上移动了CW或CCW?

可以说我们有一个锯齿状的形状:

shape0

沿着它移动的两个生物是轮廓。

然后,我们通过拉出角落,完全平滑的形状。

我们得到这个:

光滑

现在很容易看到橙色正在顺时针和绿色CCW。 我怎么能告诉他们正在移动的方向,而不是平滑的形状?

新图片

在这里输入图像描述

画一条线到无穷远,并计算你穿过形状的次数(偶数或奇数),不包括生物所在的部分。 然后检查该生物是在该行的左边还是右边。

例

在这个例子中,我们穿过两次(甚至是)的形状,我们走到左边。 结果是立即从这个表:

# Crosses | even | odd Direction | | -------------+-------+------ left | CCW | CW right | CW | CCW 

在伪代码中:

 x, y = position of creature vx, vy = direction of creature movement crossings = 0 for each x1, y1, x2, y2 in shape segments: if (x1 < x and x <= x2) or (x2 < x and x <= x1): if y - y1 > (x - x1) * (y2 - y1) / (x2 - x1): ++crossings if (crossings & 1) == (vx < 0): return CW else return CCW 

它取决于你从形状数据结构中得到的信息,但是沿着形状的轮廓移动的生物总是在其右侧具有形状的内部,并且正向移动的生物将具有形状的内部它的左边。

  1. 计算你的形状的中心点。
  2. 从中心挑选最偏远的边缘。
    • (select最远的边缘确保不会从形状的倒凹部分开始,这会导致整个形状向后/逆时针确定)
  3. 确定沿着该边的哪个方向是顺时针的
    • (一个简单的实现将涉及比较从形状的中心到选定边缘的每一端的角度,角度之间的差异的符号将告诉你顺时针方向与逆时针方向)
  4. 迭代形状的所有边,从步骤2中select的边开始,构建边的列表。 对于每个边,按顺时针顺序存储它的两个顶点。
    • (如果你的形状没有随着时间的推移而改变,那么你可以存储这个边界列表供以后使用,所以你不必每一帧都做前四个步骤)
    • (你可能已经有了一个边界列表,如果是这样的话,你可以把这个顺时针的顶点顺序存储在同一个列表中)。
  5. 要确定一个实体是顺时针还是逆时针移动:
    • 确定实体沿着哪条边移动。
    • 根据步骤4中确定的该边的顺时针开始 – >结束顶点,对实体的运动方向进行点积运算。
    • 如果点积的结果是一个大于零的值,则实体正在顺时针移动。 小于零意味着逆时针。

您需要知道多边形定义的方向,顶点绕其旋转的方式。

如果你不知道这个,你可以通过计算多边形的面积来解决这个问题:

 float Polygon::area() { float result = 0.0f; for(int a = 0; a < vertexCount; a ++) { int b = (a+1) % vertexCount; result += vertices[a].x * vertices[b].y; result -= vertices[a].y * vertices[b].x; } return result * .5f; } 

结果的标志 (正面或负面)会告诉你是顺时针还是逆时针。 你需要尝试这个来看看你的方向,因为它取决于你的坐标系。

如果形状是顺时针的:

  • 一个正在前进的生物正在顺时针旋转
  • 一个逆转的生物正在逆时针旋转

如果形状是逆时针的:

  • 一个正在前进的生物正在逆时针旋转
  • 一个逆转的生物正在顺时针旋转

Trevor似乎已经解决了这个问题,但这是我的解决scheme:

  1. 计算你的形状覆盖的面积,意义

     area = 0 foreach (edge in shape) area += edge.begin.x * edge.end.y - edge.begin.y * edge.end.x 
  2. 使用上面计算的面积,可以很容易地判断形状本身是否是顺时针的。 只有在面积小于零的情况下才是顺时针的。

  3. 检查对象是否以顶点顺序或相反方向移动。