python - 在python中检测任意形状的内角和外角的最佳算法

Question

我一直在 python 3.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('')