Ironpython中的凸壳

Question

我试图从点列表中得到凸包，这是基于格雷厄姆扫描法

points = []
for element in elements:
    #getpoints function returns four corners of element bounding box with z overwritten to 0 so that we are working in 2D coordinates.
    for p in getPoints(element):
        points.append(p)
p0 = None
points.sort(key=lambda x: x.X)
points.sort(key=lambda x: x.Y)
#isolate lower left point
p0 = points.pop(0)
#sort by angle to x axis
points.sort(key=lambda x: DB.XYZ.BasisX.AngleTo(x-p0))
# We know the second point is correct, we are starting by checking the third point.
stack = [p0, points.pop(0), points.pop(1)]
while len(points) > 0:
    vector1 = stack[-2] - stack[-1]
    vector2 = points[0] - stack[-1]
    angle1 = math.atan2(vector1.X, vector1.Y)
    angle2 = math.atan2(vector2.X, vector2.Y)
    angleDiff = angle1 - angle2
    if angleDiff >= 0:
        stack.pop(-1)
        ######stack.append(points.pop(0))  I don't think this is needed, but it doesn't solve my problem when removed.
    else:
        stack.append(points.pop(0))
curves = []
for i, point in enumerate(stack):
    curves.append(DB.Line.CreateBound(point, stack[i-1]))

“凸包”的输出明显不正确：

编辑以澄清：

以最左端为最低点。 按与x轴的角度排列所有其他点。 将前三个点添加到堆栈中。 环 如果下一个排序点将创建顺时针旋转，请移除堆栈顶部。 否则，如果创建逆时针旋转，则将候选排序点添加到堆栈顶部

我将致力于建立一个可复制的案例

YouTube链接到带有图形的解释

Convex Hull Algorithm

期望输出：

Answer 1

我用python重新构建了它，并使它开始工作。我认为问题在于我如何计算angleDiff，在这里可以更容易地看到叉积z值的符号

谢谢jason，stack = [p0, points.pop(0), points.pop(1)]确实会跳过一个值

在最初的示例中，我还向后看了vector1。它应该是stack[-1] - stack[-2]，而不是stack[-2] - stack[-1]

import math
import matplotlib.pyplot as plt
from random import randint


class XYZ:
    @property 
    def X(self):
        return self._X
    @X.setter
    def X(self, X):
        self._X = X
    @property 
    def Y(self):
        return self._Y
    @Y.setter
    def Y(self, Y):
        self._X = Y

    def __init__(self,x,y):
        self._X = x
        self._Y = y

    def __add__(self, other):
        x = self.X + other.X
        y = self.Y + other.Y
        return XYZ(x, y)
    
    def __sub__(self, other):
        x = self.X - other.X
        y = self.Y - other.Y
        return XYZ(x, y)
    
    def ccw(self, other):
        return (self.X*other.Y - self.Y*other.X) > 0

### Rand Points
points = []
for i in range(100):
    points.append(XYZ(randint(0,100), randint(0,100)))
### Static Points
# points.append(XYZ(0,0))
# points.append(XYZ(0,1))
# points.append(XYZ(15,0))
# points.append(XYZ(0,6))
# points.append(XYZ(2,2))
# points.append(XYZ(0,8))
# points.append(XYZ(12,16))
# points.append(XYZ(12,2))
# points.append(XYZ(8,1))

for i, point in enumerate(points):
    plt.scatter([point.X], [point.Y])

points.sort(key=lambda x: x.X)
points.sort(key=lambda x: x.Y)
p0 = points.pop(0)
points.sort(key=lambda x: math.atan2((x-p0).Y, (x-p0).X))
stack = [p0]
stack.append(points.pop(0))
stack.append(points.pop(0))
while len(points) > 0:
    vector1 = stack[-1] - stack[-2]
    vector2 = points[0] - stack[-1]
    if not vector1.ccw(vector2):
        stack.pop(-1)
    else:
        stack.append(points.pop(0))

for i, point in enumerate(stack):
    plt.plot([point.X, stack[i-1].X], [point.Y, stack[i-1].Y])

plt.show()