Return to Question

Input: a list P of points in the plane.

 

• Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

 
• Initialize U and L as empty lists. The lists will hold the vertices of upper and lower hulls respectively.

 
• for i = 1, 2, ..., n:

while L contains at least two points and the sequence of last two points of L and the point P[i] does not make a counter-clockwise turn:
remove the last point from L
append P[i] to L

• for i = n, n-1, ..., 1:

while U contains at least two points and the sequence of last two points of U and the point P[i] does not make a counter-clockwise turn:
remove the last point from U
append P[i] to U

• Remove the last point of each list (it's the same as the first point of the other list).
• Concatenate L and U to obtain the convex hull of P. Points in the result will be listed in counter-clockwise order.

Input: a list P of points in the plane.

• Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

• Initialize U and L as empty lists. The lists will hold the vertices of upper and lower hulls respectively.

• for i = 1, 2, ..., n:

  while L contains at least two points and the sequence of last two points of L and the point P[i] does not make a counter-clockwise turn:
  remove the last point from L
  append P[i] to L

• for i = n, n-1, ..., 1:

  while U contains at least two points and the sequence of last two points of U and the point P[i] does not make a counter-clockwise turn:
  remove the last point from U
  append P[i] to U

• Remove the last point of each list (it's the same as the first point of the other list).

• Concatenate L and U to obtain the convex hull of P. Points in the result will be listed in counter-clockwise order.

When I first started learning about rule-based programming with Mathematica, I tried to translate this algorithm for computing the convex hull of a set of 2-D points in O(n Log(n)), to use rule-based replacement. For convenience, I'll paste the pseudocode of the algorithm below:

Input: a list P of points in the plane.

Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

Initialize U and L as empty lists. The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n: while L contains at least two points and the sequence of last two points of L and the point P[i] does not make a counter-clockwise turn: remove the last point from L append P[i] to L

for i = n, n-1, ..., 1: while U contains at least two points and the sequence of last two points of U and the point P[i] does not make a counter-clockwise turn: remove the last point from U append P[i] to U

Remove the last point of each list (it's the same as the first point of the other list). Concatenate L and U to obtain the convex hull of P. Points in the result will be listed in counter-clockwise order.

convexHullPM[pts_] := 
 Module[{li, isRightTurn}, 
  isRightTurn[p1_, p2_, p3_] := 
   Sign[Det@MapThread[Prepend, {{p1, p2, p3}, {1, 1, 1}}]] == -1;
  li = Sort[pts];
  li = Join[li, Reverse@Most@li];
  li //. {pre___, a_List, b_List, c_List, 
     post___} :> {pre, a, c, post} /; Not[isRightTurn[a, b, c]]]

However it's slow (referring to its time complexity, as the input size increases); timings with increasingly larger sets of input points seem to indicate O(n^2) complexity, which seems about right - because the way I constructed the rule in Mathematica, it starts matching from the start every time a replacement is made. Whereas the listed algorithm has the notion of a current point, and points are removed from the set (if need be) from the most recent points.

When I first started learning about rule-based programming with Mathematica, I tried to translate this algorithm for computing the convex hull of a set of 2-D points in $O(n \log(n))$ time, to use rule-based replacement. For convenience, I'll paste the pseudocode of the algorithm below:

Input: a list P of points in the plane.

 

• Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

• Initialize U and L as empty lists. The lists will hold the vertices of upper and lower hulls respectively.

• for i = 1, 2, ..., n:

while L contains at least two points and the sequence of last two points of L and the point P[i] does not make a counter-clockwise turn: 
remove the last point from L 
append P[i] to L

• for i = n, n-1, ..., 1:

while U contains at least two points and the sequence of last two points of U and the point P[i] does not make a counter-clockwise turn: 
remove the last point from U 
append P[i] to U

 

• Remove the last point of each list (it's the same as the first point of the other list).
• Concatenate L and U to obtain the convex hull of P. Points in the result will be listed in counter-clockwise order.

convexHullPM[pts_] := Module[{li, isRightTurn}, 
  isRightTurn[p1_, p2_, p3_] := 
     Sign[Det@MapThread[Prepend, {{p1, p2, p3}, {1, 1, 1}}]] == -1;
  li = Sort[pts];
  li = Join[li, Reverse@Most@li];
  li //. {pre___, a_List, b_List, c_List, post___} :>
         {pre, a, c, post} /; Not[isRightTurn[a, b, c]]]

However it's slow (referring to its time complexity, as the input size increases); timings with increasingly larger sets of input points seem to indicate $O(n^2)$ complexity, which seems about right - because the way I constructed the rule in Mathematica, it starts matching from the start every time a replacement is made. Whereas the listed algorithm has the notion of a current point, and points are removed from the set (if need be) from the most recent points.