Convex hull in Ironpython

Question

I'm trying to get the convex hull from a list of points, this is based off of the Graham Scan method.

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

Output of "Convex Hull" which is clearly incorrect:

Edit for clarification:

Get the lowest point favoring leftmost. Order all other points by their angle to the x axis. Add the first three points to the stack. Loop, If the next sorted point would create an clockwise rotation, remove the top of the stack. Else if it creates a counter clockwise rotation, add the candidate sorted point to the top of the stack.

I'll work on putting together a reproducible case.

YouTube link to explanation with graphic.

Convex Hull Algorithm

Desired Output:

Answer 1

I rebuilt it in python and got it to work. I think the problem was in how I was calculating angleDiff where it would be easier to look at the sign of the cross product z value.

The stack = [p0, points.pop(0), points.pop(1)] would indeed skip a value, thanks jason.

I also have vector1 backwards in the initial example. It should be stack[-1] - stack[-2], not 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()