I’m running a monotone chain algorithm to find the convex hull of a set of points (in 2D):
https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
I tried converting this to MEL (need it due to Maya LT) but for some reason it fails with certain type of data and I’m not really sure why - I’ve stared at this code for too long that I can’t seem to spot the problem.
Some problems with converting to MEL includes:
- No negative indices
- Using non-existent array indices in a conditional (in this case: while loop) is not possible. MEL will complain when you attempt to run the script. This is my reason for running if (
size($stuff)
>= 2) - No way of sorting an array of floats. My hack around this is to convert the floats to strings and use MEL’s sort(). Either way, below I have a set of hardcoded points not processed by my sorting function - which is why it’s a bit bloated with stringArrayToString and stringToStringArray -commands.
Python:
def convex_hull(points):
"""Computes the convex hull of a set of 2D points.
Input: an iterable sequence of (x, y) pairs representing the points.
Output: a list of vertices of the convex hull in counter-clockwise order,
starting from the vertex with the lexicographically smallest coordinates.
Implements Andrew's monotone chain algorithm. O(n log n) complexity.
"""
# Test Case A
# points = [(0, 0), (9, 0), (9, 9), (0, 9)]
# Test Case B
points = [(0.1, 0.9), (0.4, 0.3), (0.7, 0.6), (1.0, 0.0)]
# 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
# Returns a positive value, if OAB makes a counter-clockwise turn,
# negative for clockwise turn, and zero if the points are collinear.
def cross(o, a, b):
value = (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
print("Is ccw: %s") % value
return value
print("
-------- LOWER --------")
# Build lower hull
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
print("entered while - popping")
lower.pop()
lower.append(p)
print("lower is now:")
for i in lower: print(i)
print("
")
print("-------- UPPER --------")
# Build upper hull
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
print("entered while - popping")
upper.pop()
upper.append(p)
print("upper is now:")
for i in upper: print(i)
print("
")
# Concatenation of the lower and upper hulls gives the convex hull.
# Last point of each list is omitted because it is repeated at the beginning of the other list.
result = lower[:-1] + upper[:-1]
print("-------- CONVEX HULL IS: --------");
for i in result: print(i)
return
# Run it
import pymel.core as pm
sel = pm.ls(sl=1, fl=1)
pointList = [(0, 0), (9, 0), (9, 9), (0, 9)]
convex_hull(pointList)
Test case A and B run fine
MEL:
// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
// Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
global proc int isCCW(float $O[], float $A[], float $B[]){
float $value = ($A[0] - $O[0]) * ($B[1] - $O[1]) - ($A[1] - $O[1]) * ($B[0] - $O[0]);
print("
Is ccw: " + $value);
return $value;
}
global proc convexHullTest()
{
// Test Case A
//$pointList = {"0:0", "9:0", "9:9", "0:9"};
//$pointListReversed = {"0:9", "9:9", "9:0", "0:0"};
// Test Case B
$pointList = {"0.1:0.9", "0.4:0.3", "0.7:0.6", "1.0:0.0"};
$pointListReversed = {"1.0:0.0", "0.7:0.6", "0.4:0.3", "0.1:0.9"};
// Create points in lower hull
print("
-------- LOWER --------");
float $pointCount = `size($pointList)`;
float $pointA[], $pointB[], $pointO[];
string $lower[], $upper[], $pointAString, $pointBString, $pointOString, $point[];
for ($i = 0; $i < $pointCount; $i++)
{
if (`size($lower)` >= 2){
// Break out the values from each point and convert to float arrays
$pointOString = $lower[`size($lower)`-2]; // 0.25:0.55 - confirmed
$pointAString = $lower[`size($lower)`-1];
$pointBString = $pointList[$i];
$pointOArray = stringToStringArray($pointOString, ":"); // 0.25 0.55
$pointO[0] = (float)$pointOArray[0]; // 0.25 0.55 as floats
$pointO[1] = (float)$pointOArray[1];
$pointAArray = stringToStringArray($pointAString, ":");
$pointA[0] = (float)$pointAArray[0];
$pointA[1] = (float)$pointAArray[1];
$pointBArray = stringToStringArray($pointBString, "%"); // 0.25:0.55 pPlane1.map[10] as strings
$pointBArray = stringToStringArray($pointBArray[0], ":"); // 0.25 0.55 as strings
$pointB[0] = (float)$pointBArray[0];
$pointB[1] = (float)$pointBArray[1];
while (`size($lower)` >= 2 && isCCW($pointO, $pointA, $pointB) <= 0){
print("
entered while - popping");
// Remove last entry
stringArrayRemoveAtIndex((`size($lower)` - 1), $lower);
}
}
$point = stringToStringArray($pointList[$i], "%");
// Insert as last entry
stringArrayInsertAtIndex(`size($lower)`, $lower, $point[0]);
print("
$lower is now:
");
print($lower);
}
// Create points in upper hull
print("
-------- UPPER --------");
for ($i = 0; $i < $pointCount; $i++)
{
if (`size($upper)` >= 2){
// Break out the values from each point and convert to float arrays
$pointOString = $upper[`size($upper)`-2]; // 0.25:0.55 - confirmed
$pointAString = $upper[`size($upper)`-1];
$pointBString = $pointListReversed[$i];
$pointOArray = stringToStringArray($pointOString, ":"); // 0.25 0.55
$pointO[0] = (float)$pointOArray[0]; // 0.25 0.55 as floats
$pointO[1] = (float)$pointOArray[1];
$pointAArray = stringToStringArray($pointAString, ":");
$pointA[0] = (float)$pointAArray[0];
$pointA[1] = (float)$pointAArray[1];
$pointBArray = stringToStringArray($pointBString, "%"); // 0.25:0.55 pPlane1.map[10] as strings
$pointBArray = stringToStringArray($pointBArray[0], ":"); // 0.25 0.55 as strings
$pointB[0] = (float)$pointBArray[0];
$pointB[1] = (float)$pointBArray[1];
while (`size($upper)` >= 2 && isCCW($pointO, $pointA, $pointB) <= 0){
print("
entered while - popping");
stringArrayRemoveAtIndex((`size($upper)` - 1), $upper); // Remove last
}
}
$point = stringToStringArray($pointListReversed[$i], "%");
// Insert as last entry
stringArrayInsertAtIndex(`size($upper)`, $upper, $point[0]);
print("
$upper is now:
");
print($upper);
}
// Remove the last points of each list and combine the hull lists
stringArrayRemoveAtIndex( (`size($lower)` - 1), $lower );
stringArrayRemoveAtIndex( (`size($upper)` - 1), $upper );
string $hullPoints[] = stringArrayCatenate($lower, $upper);
// Find the UVs in the convex hull that are furthest away from each other
print("
-------- CONVEX HULL IS: --------
");
print($hullPoints);
}
convexHullTest;
Case A runs fine but Case B breaks.
Note that both pieces of code can be run in the ScriptEditor!
What am I doing wrong here with the MEL version of the script?