计算列表中每三个连续点的叉积，检查所有叉积是否有相同的符号

Question

我使用“点”类和“多边形”类创建了多边形顶点列表。。现在，检查多边形的类型，确定它是否为“凹面”；或者“凸”多边形，我想计算顶点列表中每三个连续点的叉积。作为一个例子，考虑一个列表：<强>顶点= [P1，P2，P3，P4，P5，P6] < /强>。考虑到这个列表，序列应该是p1，p2，p3…p2，p3，p4…p3，p4，p5…p4，p5，p6…和p5，p6，p1。我的意思是，最后一个叉积将在列表的最后2个元素和第一个元素之间，因为多边形是一个闭合图形。 然后在计算之后，程序应该检查所有的叉积是-ive（负）还是+ive（正），因为这些是多边形凸的条件

class Polygon:
    def __init__(self,*vertices):
        self.vertices=[Polygon.Point(v[0],v[1]) for v in vertices]

    def CrossProduct(self, A, B, C):
        return (B.x - A.x) * (C.y - B.y) -(B.y - A.y) * (C.x - B.x)

    @property
    def shape(self):    #Method for determining the type of polygon i.e. Convex or concave
        # if (all cross product >=0 or all cross products <=0):
            #return 'Convex'
        # return 'Concave'

    class Point:
        def __init__(self,x,y):
            self.x = x
            self.y = y

### MAIN PROGRAM ###
poly1 = Polygon((3,4), (5,11), (12,8), (9,5), (5,6))  #Concave Polygon
poly2 = Polygon((5.09,5.80), (1.68,4.90), (1.48,1.38), (4.76,0.10), (7.00,2.83))  #Convex Polygon
print(poly1.shape)
print(poly2.shape)

Answer 1

在隔离了一点问题之后，我想到了类似的事情：

pp = [(3,4), (5,11), (12,8), (9,5), (5,6)]

pp = pp + pp[:(len(pp) % 3 - 1)]

print(pp)

c = list(zip(pp, pp[1:], pp[2:]))

def cross_product(p):
    print(p)
    pass

for pt in c:
    cross_product(pt)

这将产生：

[(3, 4), (5, 11), (12, 8), (9, 5), (5, 6), (3, 4)]
((3, 4), (5, 11), (12, 8))
((5, 11), (12, 8), (9, 5))
((12, 8), (9, 5), (5, 6))
((9, 5), (5, 6), (3, 4))

因此，首先，你必须稍微“填充”初始列表，使其正确包装-长度必须可以被3整除，这样我们就可以将其打包成3个点的组

之后，只需在3个连续元素之间进行简单的压缩，然后进行叉积计算

Answer 2

使用zip（..）创建所有需要的3元组，并使用all（..）进行检查：

class Polygon:
    def __init__(self,*vertices):
        self.vertices=[Polygon.Point(v[0],v[1]) for v in vertices]

    def CrossProduct(self, A, B, C):
        return (B.x - A.x) * (C.y - B.y) -(B.y - A.y) * (C.x - B.x)

    @property
    def shape(self):  #Method for determining the type of polygon i.e. Convex or concave
        p0 = self.vertices[0:1]
        # debugging printout of points that are going to be checked
        points = list(zip(self.vertices, self.vertices[1:], self.vertices[2:] + p0))
        print(*points)
        print ([self.CrossProduct(*p) for p in points])

        if all(self.CrossProduct(*p) >= 0 for p in points) or all(
            self.CrossProduct(*p) < 0 for p in points):
            return "Convex"
        return "Concave"

    class Point:
        def __init__(self,x,y):
            self.x = x
            self.y = y

        def __str__(self):
            return f"({self.x}, {self.y})"

        def __repr__(self):
            return str(self)

poly1 = Polygon((3,4), (5,11), (12,8), (9,5), (5,6))  # Concave 
poly2 = Polygon((5.09,5.80), (1.68,4.90), (1.48,1.38), (4.76,0.10), (7.00,2.83))  
print(poly1.shape) # Concave 
print(poly2.shape) # Convex 

输出：

((3, 4), (5, 11), (12, 8)) ((5, 11), (12, 8), (9, 5)) ((12, 8), (9, 5), (5, 6)) ((9, 5), (5, 6), (3, 4))
[-55, -30, -15, 10]
Concave

((5.09, 5.8), (1.68, 4.9), (1.48, 1.38)) ((1.68, 4.9), (1.48, 1.38), (4.76, 0.1)) ((1.48, 1.38), (4.76, 0.1), (7.0, 2.83)) ((4.76, 0.1), (7.0, 2.83), (5.09, 5.8))
[11.823200000000002, 11.8016, 11.8216, 11.8671]
Convex