Tonsgaard.net - 2008.03.18 Convex Hull Algorithm

Den convekse polygon er en klassisk problematik i computergenereret geometri. Som et led i min stræben efter at blive klog har jeg skrevet en algorithme til at løse dette problem.
Udfra en tilfældig punktsky vil algorithmen til enhver tid tegne en konveks outline gennem de nødvendige punkter. Hvis punktskyen ændres opdateres outlinen således at konveksiteten bevares.

Løsningen er her en variation af "Grahams Scan". Punktskyen sorteres efter x-værdier, og algorothmen bevæger sin trinvist fra venstre til højre i toppen, og fra højre til venstre i bunden. For hvert nyt tilføjet punkt undersøges om det forrige punkt ligger på højre eller venstre side af det sidste og tredjesidste punkt. Hvis det ligger til højre, så slettes det, men det beholdes hvis det ligger til venstre.

/* This function creates the upper hull from the random point set*/

Point L_upper = {};// Creates empty point list called L_upper
double LastThreeList = {};

for (int i = 1; i < P1.Count; i++)
{
if (i==1) // when i reaches 1, the two first points in the SortedPointCollection is added to the empty list, and acts as a starting point for the incremental list function.

{
L_upper = {P1[0], P1[1]}; // ad two first points
// Print ("For i =", i, "L_upper GraphVariable = ",L_upper);// print pointlist to console
}

else if (i>1) // This function starts adding points incrementally to the list, and removes ones not one the upper hull

{
L_upper = Add(L_upper, P1[i]); // add point i
for (int j = 0; j < i; j++)
{
LastThreeList = Sublist(L_upper, L_upper.Count-3 , 3 ); // creates a temporary list containing the last three points of list.
CoordinateSystem CoordOrientation = new CoordinateSystem().ByOriginXPoint(LastThreeList[0], LastThreeList[2]); // creates a coordinatesystem with an x axis in the direction of the first and the last of the previous three points
Point PointOrientation = new Point().ReportPointPositionInAnotherCoordinateSystem(CoordOrientation, LastThreeList[1]); // creates a test point at the second last point, in the newly created coordinatesystem.
//Print ("PointOrientation,",LastThreeList[1], " ,Y-value =",PointOrientation.YTranslation); // returns Y value of testpoint in new coordinatesystem. -Y = right side of x axis, +Y = left side of X axis.
if (PointOrientation.YTranslation < 0 && L_upper.Count > 2) // Tjecks for right or left side
     {
     L_upper = RemoveAt(L_upper, L_upper.Count-2); // removes the point if right.
     }
else
     {
      break; // stops loop if point is to the left.
     }
}
}