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

Question

我使用 'Point' class 和 'Polygon' class 创建了一个多边形的顶点列表。现在，要检查多边形的类型，那是否是一个'凹;或 'convex' 多边形，我想计算顶点列表中存在的 每三个连续点 的叉积。例如，考虑一个列表：vertices = [p1, p2, p3, p4, p5, p6]。考虑到这个列表，序列应该是 p1,p2,p3...p2,p3,p4...p3,p4,p5...p4,p5,p6...和 p5,p6,p1。我的意思是，最后一个叉积将在列表的最后 2 个元素和第一个元素之间，因为多边形是一个闭合图形。然后在计算之后，程序应该检查是否所有叉积都是-ive（负）或所有+ive（正），因为这些是多边形凸.[=的条件。 11=]

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

使用 zip(..) 创建所有需要的三元组并使用 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

Answer 2

稍微分析一下问题后，我想到了类似的事情：

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))

所以，首先你必须 'pad' 初始列表，以便它正确包装 - 长度必须能被 3 整除，这样我们才能将它打包成 3 个点的组。

之后，这是 3 个连续元素之间的简单压缩和 cross-product 计算的问题。

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

Calculate cross-product of every three consecutive points in a list and check whether all cross products have same signs or not

python

list

polygon

python-3.x