This is apparently a variation on Andrew's variant of Graham's scan.
/* * Convex Hull * The convex hull of a set of points is the smallest convex region * containing the points */ /* convex_hull(Points, ConvexHullVertices) is true if Points is a list of */ /* points in the form p(X,Y), and ConvexHullVertices are the vertices in */ /* the form p(X,Y) of the convex hull of the Points, in clockwise order, */ /* starting and ending at the smallest point (as determined by X-values, */ /* and by Y-values to resolve ties). No three vertices of the convex hull */ /* will be collinear. */ /* e.g. convex_hull([p(0,6),p(3,7),p(4,6),p(4,5),p(3,4),p(2,4),p(5,0)], */ /* [p(0,6),p(3,7),p(4,6),p(5,0),p(0,6)]). */ convex_hull(Points, ConvexHullVertices):- sort(Points, Points1), % Duplicated points are discarded convex_hull_1(Points1, ConvexHullVertices). convex_hull_1([P1], [P1,P1]):-!. convex_hull_1([P1,P2|Points], ConvexHullVertices):- convex_hull_2(Points, P2, [P1], UpperHull, [P1], LowerHull), join(UpperHull, LowerHull, ConvexHullVertices). /* convex_hull_2(Ps, P, Upper0, Upper, Lower0, Lower) is true if [P|Upper0] */ /* are the vertices of the current upper convex hull, [P|Lower0] are the */ /* vertices of the current lower convex hull, Upper are the vertices of */ /* the new upper convex hull and Lower are the vertices of the new lower */ /* convex hull after adding the points Ps. */ convex_hull_2([], P1, Upper, [P1|Upper], Lower, Lower). convex_hull_2([P2|Ps], P1, Upper0, Upper, Lower0, Lower):- update_upper_hull(Upper0, P1, P2, Upper1), update_lower_hull(Lower0, P1, P2, Lower1), convex_hull_2(Ps, P2, Upper1, Upper, Lower1, Lower). /* update_upper_hull(Ps, P1, P2, Qs) is true if [P1|Ps] are the vertices of */ /* the current upper convex hull, and [P2|Qs] are the vertices of the new */ /* upper convex hull after adding P2. */ /* (Go back along the vertices, discarding all up to but not including those */ /* of the last encountered edge which is not visible from the outside by */ /* the point P2.) */ update_upper_hull([P|Ps], P1, P2, Qs):- to_left_or_collinear(P1, P2, P), !, update_upper_hull(Ps, P, P2, Qs). update_upper_hull(Ps, P, _, [P|Ps]). /* update_lower_hull(Ps, P1, P2, Qs) is true if [P1|Ps] are the vertices of */ /* the current lower convex hull, and [P2|Qs] are the vertices of the new */ /* lower convex hull after adding P2. */ /* (Go back along the vertices, discarding all up to but not including those */ /* of the last encountered edge which is not visible from the outside by */ /* the point P2.) */ update_lower_hull([P|Ps], P1, P2, Qs):- to_right_or_collinear(P1, P2, P), !, update_lower_hull(Ps, P, P2, Qs). update_lower_hull(Ps, P, _, [P|Ps]). join([], ConvexHull, ConvexHull). join([Vertex|UpperHull], LowerHull, ConvexHull):- join(UpperHull, [Vertex|LowerHull], ConvexHull). /* to_left_or_collinear(Pa, Pb, Pc) is true if Pa is to the left of, or on, */ /* the directed line from Pb to Pc. */ to_left_or_collinear(p(Xa,Ya), p(Xb,Yb), p(Xc,Yc)):- (Xb-Xa) * (Yc-Ya) - (Xc-Xa) * (Yb-Ya) >= 0.0. /* to_right_or_collinear(Pa, Pb, Pc) is true if Pa is to the right of, or on,*/ /* the directed line from Pa to Pb. */ to_right_or_collinear(p(Xa,Ya), p(Xb,Yb), p(Xc,Yc)):- (Xb-Xa) * (Yc-Ya) - (Xc-Xa) * (Yb-Ya) =< 0.0.