PyMEL
# Compute the convex hull of a set of 2D points using the "Monotone chain convex hull" -algorithm
def createConvexHull(uvSel):
""" Takes list of UVs, calculates the convex hull and creates a Polygon2d object of the hull.
Example: hull = createConvexHull(selUVs)
Returns: The hull represented as a Polygon2D object """
# 2D cross product of OA and OB vectors.
# Returns positive for CCW, negative for CW and 0 if collinear
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
# Create uvCoordList - tuples with the U and V values
uvCoordList = []
for uv in uvSel:
point = pm.polyEditUV(uv, query=True)
uvCoordList.append((point[0], point[1]))
# Sort the points and remove duplicates
points = sorted(set(uvCoordList))
# Create points in lower hull
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
# Create points in upper hull
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
# Combine hulls and remove the last points of each list
hullPoints = lower[:-1] + upper[:-1]
print("hullPoints are %s")%hullPoints
# Create list of points (Point2d)
pointList = []
for pair in hullPoints:
## NOTE: Rounding the coords might give better results?
pointList.append(Point2d(pair[0], pair[1]))
print("pointList constructed, it is:")
print pointList
# Create list of lines (Line2d)
lineList = []
counter = 0
while counter <= len(pointList)-1:
if counter != len(pointList)-1:
print("pointList[counter] is")
print pointList[counter]
line = Line2d(pointList[counter], pointList[counter+1]) ## WARN: NOT CREATING LINES CORRECTLY
else: # Final line (last to first point)
line = Line2d(pointList[counter], pointList[0])
print("created line %s")%line
lineList.append(line)
counter += 1
# Create polygon object (Polygon2d) for the convex hull, and return it
print("lineList is %s")%lineList
return Polygon2d(lineList) ## WARN: NOT CREATING POLYS CORRECTLY
This is my function for creating a 2d convex hull -object from a set of selected UV’s. The class objects (Point2d, Line2, Polygon2d) have been omitted.
For some reason the created convex hull gets all scrambled. Example:
Input UV coords:
(0.1, 0.0)
(0.0, 1.0)
(0.5, 0.8)
(0.6, 0.8)
(0.6, 0.7)
Hull output:
Line2d(Point2d(0.0, 0.0), Point2d(0.1, 0.0))
Line2d(Point2d(0.1, 0.1), Point2d(0.6, 0.7))
Line2d(Point2d(0.6, 0.6), Point2d(0.6, 0.8))
Line2d(Point2d(0.6, 0.6), Point2d(0.5, 0.8))
Line2d(Point2d(0.5, 0.5), Point2d(0.0, 0.1))
EDIT:
Tested the algorithm and it appears the problem is with creating the Polygon2d object, so I’m adding my classes below:
# 2D Point
class Point2d(object):
def __init__(self, u, v):
""" Create a Point2d object using UV coords
Example: p = Point2d(1,-2) """
self.u = u
self.v = v
# 2D Line
class Line2d(object):
def __init__(self, pointA, pointB):
""" Create a Line2d object using two Point2d objects
Example: l = Line2d(pointA, pointB) """
self.pointA = pointA
self.pointB = pointB
# 2D polygon
class Polygon2d(object):
def __init__(self, lineList):
""" Create a Polygon2D object using a list of Line2d objects
Example: l = Polygon2D(list) """
self.lineList = [Line2d(*line) for line in lineList]
self.pos = len(lineList)
Classes were constructed with the help of others, in this thread: