Python中检测任意形状内部和外部角度的最佳算法

Question

我一直在Python3.2.5中开发一个二维对象创建程序，该程序处理任意形状的操作并计算它们之间的碰撞检测。这个程序允许你输入一个形状的坐标，从那里它可以做任何你想让它做的事情（把这个形状画到屏幕上，扩展边框，操作各个坐标，使它对称，等等）。在

但是我在计算任意多边形的内角时遇到了一个问题。虽然我用这个算法计算角度，技术上输出正确的角度，但我无法判断程序是否显示出内角或外角（因为用户输入的任意形状可能有凹面顶点）。在

在纸上，这看起来像是小菜一碟，因为你可以形象化的形状，你可以解释哪个角度是内部和外部的自动。但是由于程序只存储坐标值，实际上并没有可视化地创建对象来外推数据，所以这个问题变得有点棘手。在

所以我的问题是：

我应该用什么方法来计算两条直线之间的夹角？我应该如何用它来确定内角和外角之间的差异？在

例如，如果我有一个有坐标的形状（（30,50），（35,47），（40,50），（37,43），（35,35），（33,43））（它看起来有点像一个底凹的倒立尖顶），我可以很容易地计算线之间的角度，但我计算的角度是个谜。在

Answer 1

正如Jesse建议的那样，首先需要按某种顺序保存顶点列表。我建议逆时针方向。用点积求出十字积的角度和符号，告诉你它是哪一边的。按逆时针顺序存储时，内角为正

# Its a square with the top edge poked in
points = [
    ( 1.0,  1.0),
    ( 0.0,  0.0),
    (-1.0,  1.0),
    (-1.0, -1.0),
    ( 1.0, -1.0)]


def angle(x1, y1, x2, y2):
    # Use dotproduct to find angle between vectors
    # This always returns an angle between 0, pi
    numer = (x1 * x2 + y1 * y2)
    denom = sqrt((x1 ** 2 + y1 ** 2) * (x2 ** 2 + y2 ** 2))
    return acos(numer / denom) 


def cross_sign(x1, y1, x2, y2):
    # True if cross is positive
    # False if negative or zero
    return x1 * y2 > x2 * y1

for i in range(len(points)):
    p1 = points[i]
    ref = points[i - 1]
    p2 = points[i - 2]
    x1, y1 = p1[0] - ref[0], p1[1] - ref[1]
    x2, y2 = p2[0] - ref[0], p2[1] - ref[1]

    print('Points', p1, ref, p2)
    print('Angle', angle(x1, y1, x2, y2))
    if cross_sign(x1, y1, x2, y2):
        print('Inner Angle')
    else:
        print('Outer Angle')
    print('')

Answer 2

找到两个向量之间有符号角的黄金标准是atan2(cross(a,b)), dot(a,b))。在所有角度都具有高精度和鲁棒性。（在2D中，cross是垂直点积，ax*by-ay*bx。在三维空间中，使用十字积的长度；它的方向是旋转轴。）

有些事情不能做：

• 任何涉及acos的东西。反余弦是一种代码气味。它受限制的范围，不会给你的迹象，需要手动参数夹紧，并在其极端精度差。如果你发现自己在用它，试试别的办法。在
• 任何涉及直线坡度的东西。精度很差，当然对于垂直矢量是没有定义的。在
• 根据额外的测试手动选择角度范围。这很可能导致轴线附近出现不连续性。在

Answer 3

我不知道你尝试过什么算法，但通常这个问题是通过以相同的顺序（比如顺时针）存储点列表来解决的，这样每次按顺序对三个点进行角度计算时，你总是得到形状的同一侧（比如内角）。在